Partition symmetry
Let p(M, N, n) be the number of partitions of the integer n into at most M parts, each containing integers at most N. Then
p(M, N, n) = p(N, M, n).
That is, you can swap the size of the partition multisets and the upper bound on the elements in the multisets.
For example, lets look at the partitions of 6 into multisets with at most 3 elements. The Mathematica command
IntegerPartitions[6, 3]
returns
- {6}
- {5, 1}
- {4, 2}
- {4, 1, 1}
- {3, 3}
- {3, 2, 1}
- {2, 2, 2}
Now let's look at the partitions of 6 into sets with any number of elements, but with no elements greater than 3. The Mathematica command
IntegerPartitions[6, All, {1, 2, 3}]returns
- {3, 3}
- {3, 2, 1}
- {3, 1, 1, 1}
- {2, 2, 2}
- {2, 2, 1, 1}
- {2, 1, 1, 1, 1}
- {1, 1, 1, 1, 1, 1}}
Both return a list of 7 multisets because
p(3, 6, 6) = p(6, 3, 6) = 7.
As another example, let's look at partitions of 11. First we look at partitions with at most 3 elements, with each element less than or equal to 5. We list these with
IntegerPartitions[11, 3, Range[5]]
which gives
- {5, 5, 1}
- {5, 4, 2}
- {5, 3, 3}
- {4, 4, 3}
Now let's look at partitions of 11 into multisets with at most 5 elements, each less than or equal to 3 using
IntegerPartitions[11, 5, Range[3]]
This gives us
- {5, 5, 1}
- {5, 4, 2}
- {5, 3, 3}
- {4, 4, 3}
Not only do both lists have the same number of partitions, which we would expect because
p(3, 5, 11) = p(5, 3, 11),
in this case they actually give the same list of partitions.
The symmetry relation here follows from the symmetry of the q-binomial coefficient because p(M, N, n) equals the coefficient of qn in the q-binomial
It's not immediately obvious from the definition that the rational function defining q-binomial coefficient is in fact a polynomial, but it is.
More partition postsThe post Partition symmetry first appeared on John D. Cook.