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[23]:=
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[2]:=
 | PermutationIndex |
»
{4,7,6,8,1,9,5,2,3}
Out[2]=
149543
Get the permutation:
In[3]:=
| PermutationFromIndex |
Out[3]=
{4,7,6,8,1,9,5,2,3}
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]:=
Dataset[AssociationMap["n"ModifiedCentralBinomialCoefficient[#]&][Range[0,21]]]
Out[958]=
| |||||||||||||||||||||||||||||||||||||||||||||
This matches our output.
If we start at 1, we will get all True instead of a False at 0.
For some reason, I can't use GeneratingFunction.
Derangements
Sets
Sets
Derangements of a set
Derangements of a set
Let's analyze the derangements. A derangement is where no element remains in its original position. If an element remains in its original position, you call that a fixed point. So a derangement is a permutation with 0 fixed points.
We can count this.
We can also compute this.
This is the subfactorial of the length.
Partial derangements of a set
Partial derangements of a set
We can also compute partial derangements. Let's say we have 2 fixed points. That means 2 elements do not move.
Now let's count them.
Multisets
Multisets
Here is a multiset with repeated elements.
Computing derangements of multisets is harder, but the function can do it.
Derangements
Derangements
Let's do a smaller example. This time, let's list all the elements of the set.
Let's find all the multiset partial derangements.
The length:
Here is the count.
Count the derangements of the whole set.
This is the same as having 0 fixed points.
Partial Derangements
Partial Derangements
List all the partial derangements with 3 fixed points one by one.
The length:
The computed length:
Count partial derangements of the whole set with 3 fixed points.
If we compute partials derangements with 3 fixed points, we will get 24 elements.
I will limit the output to 20 this time.
Multichoose and 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.
Another way of entering it is like this. This is infix notation.
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.
If we want to count orderless combinations, we can use multichoose.
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 for larger inputs.
Ferrers diagrams
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:
Selecting permutations
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:
Selecting subsets
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:
Selecting tuples
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:
Eulerian Numbers
Eulerian Numbers
Eulerian Numbers
The table of Eulerian numbers up to 10:
The combinatorial interpretation of Eulerian numbers is they give the number of permutations of the numbers 1 to n in which exactly k elements are greater than the previous element (permutations with k "ascents").
Let's manually verify some of the triangle.
We have to change the number by 1.
Let's compare the two again.
The function is using a different convention.
The first 9 rows of the triangle of Eulerian numbers of the second kind:
A list:
The function works on lists.
Make a list of digits.
The Stirling permutations are related to the Eulerian number of the second kind. Here we can compute the length of the Stirling permutations.
We can compare this to the row totals in the Eulerian number of the second kind triangle.
Here is another way.
To get the list I can use Normal.
All of these are equal.
Eulerian Catalan Numbers
Eulerian Catalan Numbers
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.
Let's compute the list with the definition.
Let's verify this for small cases by counting.
Here's how we can count the number of ascents of a permutation.
Now let's generate the permutations. There are too many permutations to display for n=3.
Now, let's select the permutations with n ascents.
Now let's count them.
Now let's multiply this number by 2.
This is what we would get with EulerianCatalanNumber
Let's verify this for a larger set of numbers.
I could also use SelectPermutations.
Let's see how much memory our calculation took.
Now let's use SelectPermutations. Here's an example of how we could use it.
Let's do it with Table.
How does this compare to the normal method?
We used less memory.
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:
Now let's look at Lucas numbers.
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.