combinat::partitions
--
partitions of an integer
The library combinat::partitions
provides functions for counting,
generating, and manipulating partitions.
p
of a nonnegative integer n
is
a non-increasing list of positive integers (the parts of the
partition) with total sum n
.[5,3,1]
:
+---+ | | +---+---+---+ | | | | +---+---+---+---+---+ | | | | | | +---+---+---+---+---+
Applying a reflection w.r.t. the main diagonal to this diagram
yields the diagram of the conjugate partition, here
[3,2,2,1,1]
:
+---+ | | +---+ | | +---+---+ | | | +---+---+ | | | +---+---+---+ | | | | +---+---+---+See
combinat::partitions::conjugate
.Cat::IntegerListsLexClass
combinat::compositions
, combinat::tableaux
The MuPAD domain used to represent partitions: DOM_LIST
isA(any type part <, nonnegative integer n <, constraints>>)
part
is a partition.n
is present, returns whether part
is a
partition of n
.part
is a partition
satisfying constraints
.
count(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
generator(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
list(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
first(nonnegative integer n <, constraints>)
n
satisfying
constraints
or FAIL
if there is none.
Next(partition p <, constraints>)
p
satisfying
constraints
or FAIL
if there is none.
printPretty(partition p)
printCompact(partition p)
#
.
conjugate(partition p)
p
. Geometrically, this operation amounts to a reflection of
the diagram of the partition with respect to the main diagonal.
hooklengths(partition p)
p
.p
. The formula was first discovered by Frame, Robinson,
and Thrall in 1954.
toExp(partition p)
p
.
This is a vector v
of nonnegative integers such that
v[i]
counts the number of occurrences of i
as part of
p
. By default, the length of the vector is the size of the
maximal part of p
.toExp(partition p, nonnegative integer k)
p
,
padded with zeroes to ensure a length at least k
.combinat::partitions::fromExp
.
fromExp(list l)
p
from its exponential notation l
.combinat::partitions::toExp
.
centralizerSize(partition p)
p
.
conjugacyClassSize(partition p)
p
.
corners(partition p)
printPrettyCorners(partition p)
*
.
printCompactCorners(partition p)
#
and corners are marked with *
.There are 5 partitions of 4:
>> combinat::partitions::count(4)
5
Here is the list:
>> combinat::partitions::list(4)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
And here is the graphic representation of these partitions:
>> map(combinat::partitions::list(4), combinat::partitions::printPretty)
-- | | +---+ | | | | +---+ +---+---+ +---+ | | | | | | | | | +---+---+---+---+ +---+---+---+ +---+---+ +---+---+ | | | | | |, | | | |, | | |, | | |, -- +---+---+---+---+ +---+---+---+ +---+---+ +---+---+ +---+ -- | | | +---+ | | | | +---+ | | | | +---+ | | | | +---+ --
Or in a more compact way:
>> map(combinat::partitions::list(4), combinat::partitions::printCompact)
-- # -- | # ## # # | | ####, ###, ##, # , # | -- ## # --
You can use the function combinat::partitions::first
to get
the ``first'' partition of a number:
>> combinat::partitions::first(4)
[4]
Using combinat::partitions::Next
, you can calculate the
``next'' partition. This function takes as argument the partition
relative to which you want the next one:
>> combinat::partitions::Next([4])
[3, 1]
combinat::partitions::Next
returns FAIL
when the
input is the last partition:
>> combinat::partitions::Next([1, 1, 1, 1])
FAIL
When you want to run through the partitions of a number, you can generate them one by one to save memory:
>> g := combinat::partitions::generator(4):
g(); g(); g(); g(); g(); g()
[4] [3, 1] [2, 2] [2, 1, 1] [1, 1, 1, 1] FAIL
Typically, this would be used as follows:
>> g := combinat::partitions::generator(4):
while (p := g()) <> FAIL do print(p): end:
[4] [3, 1] [2, 2] [2, 1, 1] [1, 1, 1, 1]
The options Length, MinLength, and MaxLength can be used to set length constraints. This is the list of the partitions of 4 of length 2:
>> combinat::partitions::list(4, Length=2)
[[3, 1], [2, 2]]
This is the list of the partitions of 4 of length at least 2:
>> combinat::partitions::list(4, MinLength=2)
[[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
This is the list of the partitions of 4 of length at most 2:
>> combinat::partitions::list(4, MaxLength=2)
[[4], [3, 1], [2, 2]]
Setting both MinLength and MaxLength to the same value is equivalent to setting Length to this value. This is again the list of the partitions of 4 of length 2:
>> combinat::partitions::list(4, MinLength=2, MaxLength=2)
[[3, 1], [2, 2]]
The options MinPart and MaxPart can be used to set constraints on the sizes of all parts. Using MaxPart, you can select partitions having only small entries. This is the list of the partitions of 4 with all parts at most 2:
>> combinat::partitions::list(4, MaxPart=2)
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]
MinPart is complementary to MaxPart and selects partitions having only large parts (it takes a non-negative value). This is the list of the partitions of 4 with all parts at least 2:
>> combinat::partitions::list(4, MinPart=2)
[[4], [2, 2]]
By default, the parts of a partition have to be positive. This can be changed using the option MinPart. In the following example, the options Length and MinPart are combined together to obtain the list of the partitions of 4 with 3 nonnegative parts:
>> combinat::partitions::list(4, Length=3, MinPart=0)
[[4, 0, 0], [3, 1, 0], [2, 2, 0], [2, 1, 1]]
Two partitions are considered equivalent whenever they differ only by trailing zeroes. Whenever two equivalent partitions satisfy the constraints, only the shortest one is considered. Hence, this is the list of partitions of 4 with at least 3 nonnegative parts:
>> combinat::partitions::list(4, MinLength=3, MinPart=0)
[[4, 0, 0], [3, 1, 0], [2, 2, 0], [2, 1, 1], [1, 1, 1, 1]]
The options Inner, and Outer can be used to set part-by-part
inclusion constraints. This is the list of the partitions of 4
with [3, 1, 1]
as an outer bound:
>> combinat::partitions::list(4, Outer=[3, 1, 1])
[[3, 1], [2, 1, 1]]
Outer sets MaxLength to the length of its argument. Moreover, the parts of Outer may be infinite to clear the constraint on specific parts. This is the list of the partitions of 4 of length at most 3 such that that the second and third part are 1 when they exists:
>> combinat::partitions::list(4, Outer=[infinity, 1, 1])
[[4], [3, 1], [2, 1, 1]]
This is the list of the partitions of 4 with [1, 1, 1]
as an inner bound:
>> combinat::partitions::list(4, Inner=[1, 1, 1])
[[2, 1, 1], [1, 1, 1, 1]]
The options MinSlope and MaxSlope can be used to set
constraints on the slope, that is on the difference
p[i+1]-p[i]
of two consecutive parts. This is the list of
the strictly decreasing partitions of 4:
>> combinat::partitions::list(4, MaxSlope=-1)
[[4], [3, 1]]
The default value for MaxSlope is zero to force the parts to be non-increasing. If MaxSlope is explicitly set to a positive number, the resulting lists are not necessarily partitions anymore since the parts may increase:
>> combinat::partitions::list(4, MaxSlope=1)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
This is the list of the partitions of 4 such that the difference between two consecutive parts is at least -1:
>> combinat::partitions::list(4, MinSlope=-1)
[[4], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
This is the list of increasing partitions of 4:
>> combinat::partitions::list(4, MaxSlope=infinity, MinSlope=0)
[[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]
The constraints can be combined together in all reasonable ways. This is the list of the partitions of 11 of length between 2 and 4 such that the difference between two consecutive parts is between -3 and -1:
>> combinat::partitions::list(11,
MaxSlope=-1, MinSlope=-3,
MinLength=2, MaxLength=4)
[[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]]
Idem with an Outer constraint:
>> combinat::partitions::list(11,
MaxSlope=-1, MinSlope=-3,
MinLength=2, MaxLength=4,
Outer=[6,5,2])
[[6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2]]
However, providing incoherent constraints may yield strange results. It is up to the user to ensure that the Inner and Outer partitions themselves satisfy the part and slope constraints:
>> combinat::partitions::list(5, Inner=[2, 1], MinPart=2)
[[4, 1], [3, 2], [2, 1, 2]]
This is the conjugate of the partition [4, 1]
:
>> combinat::partitions::conjugate([4, 1])
[2, 1, 1, 1]
Geometrically, we just applied a reflection with respect to the main diagonal on the diagram of the partition. Of course, this operation is an involution:
>> combinat::partitions::conjugate([2, 1, 1, 1])
[4, 1]
We describe how to generate k-regular partitions. Recall that
a partition p
is k-regular if no part is repeated
more than k-1 times, or, equivalently, if the difference between
any two consecutive parts of the conjugate partition pc
is
at most n-1. Here is a first (buggy) attempt to get the
3-regular partitions of 7:
>> map(combinat::partitions::list(7, MinSlope=-2),
combinat::partitions::conjugate)
[[1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 1], [3, 2, 1, 1], [3, 2, 2], [3, 3, 1], [4, 2, 1], [5, 1, 1], [4, 3], [5, 2], [6, 1], [7] ]This is not quite correct: in
[2,2,2,1]
, the first part is repeated
3 times. Here is what happened: this 3 is the last part of the conjugate
partition [4,3]
, and we did not check the slope condition between this
last part and the consecutive implicit zeroes. We ensure that the conjugate
partition is padded with zeroes by setting Length=7+1
. Note that
combinat::partitions::conjugate
allows partitions with padded zeroes.
Now, here is the correct list of 3 regular partitions of 7:
>> map(combinat::partitions::list(7, MinSlope=-2, MinPart=0,
Length=7+1), combinat::partitions::conjugate)
[[3, 2, 1, 1], [3, 2, 2], [3, 3, 1], [4, 2, 1], [5, 1, 1], [4, 3], [5, 2], [6, 1], [7]]
This trick is efficient, and can be refined further to generate regular partitions with length, part, or inclusion constraints.
This is the exponential notation of the partition [4, 1]
:
>> combinat::partitions::toExp([6,4,4,2,1])
[1, 1, 0, 2, 0, 1]
It can be converted back to the original partition:
>> combinat::partitions::fromExp([1, 1, 0, 2, 0, 1])
[6, 4, 4, 2, 1]
The exponential notation can be padded with extra zeroes:
>> combinat::partitions::toExp([6,4,4,2,1], 5);
combinat::partitions::toExp([6,4,4,2,1], 7);
combinat::partitions::toExp([6,4,4,2,1], 10);
[1, 1, 0, 2, 0, 1] [1, 1, 0, 2, 0, 1, 0] [1, 1, 0, 2, 0, 1, 0, 0, 0, 0]
In any cases, converting back yields the original partition:
>> combinat::partitions::fromExp([1, 1, 0, 2, 0, 1, 0, 0, 0]);
[6, 4, 4, 2, 1]
This example shows how to compute the corners of a partition.
>> combinat::partitions::corners([4, 3, 1])
[[1, 4], [2, 3], [3, 1]]
The corners can be represented graphically:
>> combinat::partitions::printPrettyCorners([4, 3, 1])
+---+ | * | +---+---+---+ | | | * | +---+---+---+---+ | | | | * | +---+---+---+---+
Here is a more compact representation:
>> combinat::partitions::printCompactCorners([4, 3, 1])
* ##* ###*
Cat::IntegerListsLexClass
with, by default,
MaxSlope=0
, and MinPart=1
. The complexity of the
generation algorithm is constant time amortized for each partition
generated.In all other cases, counting is done by brute force generation.
combinat::partitions(n)
to compute the number of partitions
of n
is strongly deprecated, and will not work anymore
starting from the next minor release of MuPAD; please use
combinat::partitions::count(n)
instead. The emission of a
warning can be controlled with
combinat::warnDeprecated(FALSE)
or
combinat::warnDeprecated(TRUE)
.Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package