Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Combinatorics
This paclet is for the study of combinatorics. I am a combinatorialist. That means I study combinatorics.
The functions defined in the context provide support for finding solutions to combinatorics-related problems.
PeterBurbery`Combinatorics`
In[469]:=
Needs["PeterBurbery`Combinatorics`"]
Indexes
gives the lexicographic index of permutation perm | |
returns the permutation of length lengthInput index | |
gives the index of subset list | |
returns a subset of length len index |
Computing the index or using the index to get the thing.
Find the index of a random permutation
In[12]:=
 | PermutationIndex |
»
{2,6,9,1,4,8,3,5,7}
Out[12]=
64843
Get the permutation:
In[13]:=
| PermutationFromIndex |
Out[13]=
{2,6,9,1,4,8,3,5,7}
Here's a neat application of this function. We can use this to solve Project Euler Problem 24 Lexicographic Permutations. What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9?
In[6]:=
| PermutationFromIndex |
6
10
Out[6]=
{3,8,9,4,10,2,6,5,7,1}
Now we need to subtract 1. 10 will become 9 and 1 will become 0.
In[7]:=
 | PermutationFromIndex |
6
10
Out[7]=
{2,7,8,3,9,1,5,4,6,0}
Now we can use FromDigits.
In[8]:=
FromDigits
[1000000(*amillionis*),10(*becauseLength[{0,1,2,3,4,5,6,7,8,,9}]is10,not9*)]-1
 | PermutationFromIndex |
6
10
Out[8]=
2783915460
And that's the answer!
Find a subset's index.
In[10]:=
| SubsetIndex |
Out[10]=
29
Find the subset.
In[15]:=
| SubsetFromIndex |
Out[15]=
{2,4,6}
Central Binomial Coefficient
Compute the central binomial coefficient.
In[18]:=
| CentralBinomialCoefficient |
Out[18]=
24857784491537440929618523018320
In[19]:=
| CentralBinomialCoefficient |
Out[19]=
Binomial[2n,n]
Find the generating function.
In[20]:=
GeneratingFunction
[n],n,x
| CentralBinomialCoefficient |
Out[20]=
1
1-4x
Make a table of values.
In[22]:=
DatasetAssociationMap"n"
[#]&[Range[21]]
 | CentralBinomialCoefficient |
Out[22]=
| |||||||||||||||||||||||||||||||||||||||||||||
The digits of
for are
2 n 10 |
n 10 |
n=0,1,…
In[32]:=
DatasetAssociationMap"n"IntegerLength
[]&[Range[0,8]]
| CentralBinomialCoefficient |
#
10
Out[32]=
|
These digits are converging to the digits of 4.
log
10
In[34]:=
N[Log[10,4],40]
Out[34]=
0.6020599913279623904274777894489860535364
Modified Central Binomial Coefficient
Let's look at the modified central binomial coefficient.
In[958]:=
DatasetAssociationMap"n"
[#]&[Range[0,21]]
| ModifiedCentralBinomialCoefficient |
Out[958]=
| |||||||||||||||||||||||||||||||||||||||||||||
This matches our output.
If we start at 1, we will get all True instead of a False at 0.
Derangements
A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. For example, the derangements of {1,2,3}:
Derangements of four elements:
The have no cycles of length one.
This is one way to find derangements.
A more efficient algorithm would not generate all the permutations and then pick the derangements, but instead just generate the derangements.
Let's find all the permutations where every element has moved. If an element stays in place, we name that a fixed point. A derangement is a permutation with 0 fixed points.
What is the length?
How can we compute the length faster and more efficiently? We can compute this with the subfactorial. The subfactorial is written ! n. The subfactorial is also called the derangement number for this reason. The nth subfactorial is the number of permutations of n objects in which no object appears in its natural place (i. e., "derangements").
Here's a table:
Now we can find the number of derangements for a set with many elements.
We couldn't do this the other way.
Euler calculated the first ten terms of the subfactorial.
Here are representations of the subfactorial.
Here we use the incomplete gamma function for the subfactorial.
We can solve for the representation of the subfactorial.
There is a connection with rook polynomials and the subfactorial. The subfactorial can be considered a special case of a restricted rooks problem.
Here is an integral form.
Here is a continued fraction:
Let's look at the generating function.
Plot the sequence:
Plot over a subset of the complexes:
Series expansion at the origin:
Now that we can count a derangement, let's discuss partial derangements. We allow the number of fixed points to be a nonzero value.
Now we can find permutations with 2 fixed points. I have to apply Rasterize to build the documentation without errors.
Now let's look at pure derangements of a small multiset.
Let's count them.
To compute the number of partial derangements of a multiset, we integrate Laguerre polynomials.
Let's compute the number of partial derangements for a multiset with too many elements to list the elements one by one.
Count the derangements.
This is the same as having 0 fixed points.
Now let's see a small example of partial derangements of a multiset.
Let's find how many partial derangements with 2 fixed points there are.
Let's use Laguerre polynomials to compute this.
Let's do a calculation for partial derangements where listing all permutations is infeasible.
Count partial derangements with 3 fixed points.
Let's do a smaller example again. This time, let's list all the elements of the set.
Let's find all the multiset partial derangements.
Here is the count.
List partial derangements with 3 points, then take the length.
If we compute partials derangements with 3 fixed points, we will get 101 elements.
I will limit the output to 20 this time. This is the third argument.
Multichoose
There are four candies: gummy bears, gummy worms, chocolate bars,and marshmallows. There are three children named Peter, James, and Andrew (after the apostles from the Bible). How many ways can the four candies be distributed among the four children?
Let's list all the orderless combinations.
There are ten candies: licorice, peppermint drops, lemon drops, truffles, gummy bears, gummy worms, chocolate bars, jelly beans, peanut butter cups, and marshmallows. There are four children named Peter, James, John, and Andrew. How many ways can the ten candies be distributed among the four children?
We can compute 10 multichoose 4.
We can also generate all the combinations and count them. Since there are a lot of combinations, I am not listing them all here and then using Length. I'm just going to use Length immediately.
Get length four sets from a list of length two:
Elements need not be integers:
We could consider {"cat", "cat", "cat"} and {"dog", "dog", "dog"} as partly equal.
If we delete duplicates by CanonicalMultiset, we get fewer elements.
Here's what we would get something like.
These produce the same output.
Let's compare the performance for a large set.
The definition of the function is significantly faster and uses significantly less memory.
Make a Ferrers diagram for every partition of 5.
Rows 1 to 4 have 5, 4, 2, 2 dots:
Here is a random choice of one of the 204226 partitions of 50:
Select from the list {5,6,7,8,9} those permutations that form a prime when concatenating the digits:
Here are the numbers.
Select permutations of length 3:
Here are the numbers.
Select permutations with length 3—4:
Here are the numbers.
Select permutations for which the first two elements and the last elements add up to the same value:
Select the first ten permutations of length 4 for which the elements add up to an odd number:
Expand the polynomials.
There are really only three unique ones.
Make a graph of all of them.
Duplicated items are treated the same:
Verify that the results are identical:
Using the built-in functions is faster at the expense of 500× more memory:
Select subsets from {1,2,3,4,5} that add up to 10:
Select subsets of length 2 to 4 that sum up to a prime:
Select all subsets of length 2 that add up to 6:
Select all subsets that add up to 0:
Select all subsets of odd length that add up to a prime:
Select the first 8 subsets that add up to a prime:
Find subsets that add up to 25:
Compared to naive implementation, which requires roughly a 1000 times more memory:
Verify the result is the same:
Find subsets that add up to 0:
Visualize the lengths of the lists:
Find out for which 2-tuple the sum is a prime:
Only get the first five:
Find the first 15 three-letter palindromic lists:
Find vectors for which the norm is an integer:
Compared to naive implementation:
I got kind of confused with this.
This function uses a different index for k.
This also affects the definition of other related functions like EulerianCatalanNumber.
The table of Eulerian numbers up to 10:
The first 9 rows of the triangle of Eulerian numbers of the second kind:
The first 14 rows of the Narayana triangle read as follows:
Make a table of signed and unsigned Lah numbers.
Find the sum of even-valued Fibonacci numbers less than 4 million.
Compute the inverse Fibonacci of 4 million.
That's the answer.
Here are more examples.
For some reason, although I have a function that can compute the next permutation, I have not solved this Wolfram Challenge.
Consider the permutation:
The descents follow easily:
There is also a function for this.
A triangular table of Gauss factorials up to 7::
Make a grid with a frame:
Phitorial of 10:
Compute the answer mod 1000000007:
Product of primes up to 20:
Product of primes up to 54:
Compute a list of the first 15 primorials:
Compare with the definition:
Compare the growth rate of the primorial versus factorial:
You can also do the Pell numbers with LinearRecurrence:
Find a linear recurrence:
Generate a linear recurrence:
We can also find a Fibonacci function:
We can find a pattern:
Generate a new array:
Verify the statement up to 7:
Verify this statement:
The first 21 Lucas numbers:
Compare the function to LucasL:
Let's compare this to LucasL:
Test this statement:
Test this statement:
Evaluate the q-exponential.
Evaluate numerically:
Change q from 1 to 2.
Ask for 40 digits of precision.
Evaluate the q-multinomial.
Evaluate numerically:
Find the period of the decimal representation of a rational number.
3/2 has a period of 0.
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given.
We can use Identity@@ to get just the number.
We can use EchoPerformance to see how much memory we used.
Make a list for the first 1000 numbers.