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?
Subfactorial
Subfactorial
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:
Orderless combinations of plain indistinguishable unmarked unlabeled elements
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.
Monotonic function
and weakly decreasing
and weakly decreasing
In calculus, a function f defined on a subset of the real numbers (here we define subset as being allowed to be the whole set, that is the real numbers) with real values is called monotonic if and only if it is either entirely non-increasing, or entirely non-decreasing. That is, as per Figure 1, a function that increases monotonically does not exclusively have to increase, it simply must not decrease.
Figure 1: A monotonically non-decreasing function.
A function is called monotonically increasing (also increasing or non-decreasing) if for all x and y such that x ≤ y one has f(x) ≤ f(y), so f preserves the order (see Figure 1). Likewise, a function is called monotonically decreasing (also decreasing or non-increasing) if, whenever x ≤ y one has f(x) ≥ f(y), so that it reverses the order (see Figure 2).
Figure 2. A monotonically non-increasing function
To avoid ambiguity, the terms weakly monotone, weakly increasing, and weakly decreasing are often used to refer to non-strict monotonicity.
The terms "non-decreasing" and "non-increasing" should not be confused with the (much weaker) negative qualifications "not decreasing" and "not increasing". For example, the non-monotonic function shown in figure 3 first falls, then rises, then falls again. It is therefore not decreasing and not increasing, but it is neither non-decreasing nor non-increasing.
Figure 3: A function that is not monotonic
Here are some useful functions for this.
x is weakly increasing:
-x is weakly decreasing:
x is strictly increasing:
-x is strictly decreasing:
To say {5,4,2,2} is weakly decreasing means that every element to the right of every element is less than or equal to it. For example, 4, 2, and 2 are all less than or equal to 5. 2 and 2 are less than or equal to 2. 2 is less than or equal to 2. If we specify strictly decreasing, equality is not allowed. We used equality with 2 and 2 here, so the sequence {5,4,2,2} is not strictly decreasing. {6,5,3,2} is strictly decreasing. The same logic applies to the terms weakly increasing and strictly increasing.
Integer Partitions
In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways:
The only partition of zero is the empty sum, having no parts.
The order-dependent composition 1+3 is the same partition as 3+1, and the two distinct compositions 1+2+1 and 1+1+2 represent the same partition as 2+1+1.
Partitions can be graphically represented with Young diagrams or Ferrers diagrams. They occur in a number of branches of mathematics and physics, including the study of symmetric polynomials and of the symmetric group and in group representation theory in general.
Examples
Examples
The seven partitions of 5 are.
We can also use a list.
I have a function for this now.
Write a partition in plus notation.
Make a column of integer partitions for 5.
There is now a function for superscript notation too now.
Write {2,2,1} in partition plus notation.
Go back to {2,2,1}:
List@@ would also work here:
There is one time when List@@ will not work. That time is for a single integer.
We wanted to return {5}, the way IntegerPartitions[5] does.
We can use FromPartitionPlusNotation for this edge case.
This is the inverse of PartitionPlusNotation.
Here are the integer partitions of 5:
Here is a list of integer partitions in superscript notation:
Go back to the integer partitions of 5:
This is the inverse of PartitionSuperscriptNotation.
Diagrammatic representations of partitions
Diagrammatic representations of partitions
There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after Norman Macleod Ferrers, and as Young diagrams, named after Alfred Young. Both have several possible conventions, here we use English notation, with diagrams aligned in the upper-left corner.
Ferrers diagram.
Ferrers diagram.
The partition 6+4+3+1 of the number 14 can be represented by the following diagram:
The 14 circles are lined up in 4 rows, each having the size of a part of the partition. The diagrams for the 5 partitions of the number 4 are shown below:
Young diagram
Young diagram
An alternative visual representation of an integer partition is its Young diagram (often also called a Ferrers diagram). Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses boxes or squares. Thus, the Young diagram for the partition 5+4+1 is
while the Ferrers diagram for the same partition is
Make a Young diagram for the integer partition of 10 5+4+1:
While this seemingly trivial variation does not appear worthy of separate mention, Young diagrams turn out to be extremely useful in the study of symmetric functions and group representation theory: filling the boxes of Young diagrams with numbers (or sometimes more complicated objects) obeying various rules leads to a family of objects called Young tableaux, and these tableaux have combinatorial and representation-theoretic significance. As a type of shape made by adjacent squares joined together, Young diagrams are a special kind of polyomino.
Partition function
Partition function
The partition function p(n) counts the partitions of a non-negative integer n. For instance, p(4)=5 because the integer 4 has the five partitions 1+1+1+1, 1+1+2, 1+3, 2+2, and 4. The values of this function for n=0, 1, 2, … are:
The generating function of p is
No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly. It grows an exponential function of the square root of its argument, as follows.
The multiplicative inverse of its generating function is the Euler function; by Euler's pentagonal number theory this function is an alternating sum of pentagonal powers of its argument.
Consider the partition {5,4,2,2}.
Check if this is a weakly decreasing list of positive integers.
An integer partition is a multiset of positive integers and so not ordered. Therefore, any order can be used to represent it. Typically, the order chosen is weakly decreasing, as here; some people choose weakly increasing.
Here are the integer partitions of 13.
These are all the partitions:
Between 1 and 4 parts—at most 4 parts:
Exactly 4 parts:
Between 1 and 4 parts:
Using only 5, 4, or 2:
I'm curious if this returns the same as above.
No it doesn't. We must use DeleteDuplicates.
Its not free of duplicates.
Delete the duplicates.
We can also limit the result to the a certain number of partitions.
Get the first 20 partitions.
We can compute the number of partitions with PartitionsP.
Here's a table.
Here's the asymptotic behavior:
Strict partitions
A partition in which no part occurs more than once is called strict, or is said to be a partition into distinct parts. The function q(n) gives the number of these strict partitions of the given sum n.
Partitions of even length only:
Partitions of odd length:
Partitions with only odd elements:
There is a bijection between the partitions of a strictly positive integer into odd numbers and the partitions of a number into distinct parts.
Find the strict integer partitions of 16. List the partitions of 16 into distinct parts.
A strict integer partition has no duplicate parts. For example, {5,3,1,1} has a duplicated 1. Therefore, {5,3,1,1} is not a strict integer partition. {6,4,2,1} has all unique parts so it is a strict integer partition.
The number of strict integer partitions is given by the partition function q(n).
The function can generate large numbers of partitions quickly and efficiently:
Test this for the first 80 numbers:
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:
Select 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:
Select 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:
Select 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 and permutations and ascents and runs
Permutation Ascents
Permutation Ascents
Eulerian Numbers
Eulerian Numbers
The table of Eulerian numbers up to 10:
Therefore, the Eulerian numbers represent a sort of generalization of the binomial coefficients where the defining recurrence relation weights the sum of neighbors by their row and column numbers, respectively.
Computation
Computation
For larger values of n, A(n,k) can be calculated using the recursive formula A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k).
Identities
Identities
For any property partitioning a finite set into finitely many smaller sets, the sum of the cardinalities of the smaller sets equals the cardinality of the bigger set. The Eulerian numbers partition the permutations of n elements, so their sum equals the factorial n!.
Formulas involving alternating sums
Eulerian numbers of the second order
Eulerian numbers of the second order
The Eulerian numbers of the second order satisfy the recurrence relation, that follows directly from the above definition:
with the initial condition for n=0, expressed in Iverson bracket notation:
The following table displays the first few second-order Eulerian numbers:
Indexing the second-order Eulerian numbers comes in three flavors:
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 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.