combinat::partitions

combinat::partitions – partitions of an integer

The library combinat::partitions provides functions for counting, generating, and manipulating partitions.

→ Examples

Superdomain

Dom::BaseDomain

See also combinat::partitions::toExp .

centralizerSize – size of the centralizer of a permutation

combinat::partitions::centralizerSize(partition p)

Returns the size of the centralizer of any permutation with cycle-type p (see combinat::permutations::cycleType ).

This is math, where math denotes the number of parts math in the partition math (see combinat::partitions::toExp ).

Those numbers math play an important role in the theory of symmetric functions (see examples::SymmetricFunctions ).

z – MacDonald's z numbers

combinat::partitions::z(partition p)

See combinat::partitions::centralizerSize .

conjugacyClassSize – size of a conjugacy class of the symmetric group

combinat::partitions::conjugacyClassSize(partition p)

Returns the size of the conjugacy class of the symmetric group indexed by the partition math, that is the number of permutations with cycle type math (see combinat::permutations::cycleType ).

This number is given by the formula math (see combinat::partitions::centralizerSize ).

Reference: A. Kerber, "Algebraic Combinatoric Via Finite Group Action", 1.3 p. 24.

corners – corners of a partition

combinat::partitions::corners(partition p)

Returns a list of coordinates of the corner boxes of the partition.

printPrettyCorners – graphic representation of the corners of a partition

combinat::partitions::printPrettyCorners(partition p)

Returns a graphic representation of the partition as rows of boxes where the corners are marked with *.

printCompactCorners – graphic representation of the corners of a partition

combinat::partitions::printCompactCorners(partition p)

Same as above, but in a more compact way, where each box is represented by # and corners are marked with *.

rCore – the r-core of a partition

combinat::partitions::rCore(partition part, nonnegative integer math)

Returns the r-core of a partition, ie the partition we obtain by retiring all ribbons from the partition. The set of all the r-core is a set strictly smaller than the set of all the partitions.

rQuotient – the r-quotient of a partition

combinat::partitions::rQuotient (partition part, nonnegative integer r)

Returns the r-quotient of a partition, ie a r-uplet of partitions.

fromCoreAndQuotient – partition from its core and its quotient

combinat::partitions::fromCoreAndQuotient(partition core, list of partitions lp)

Rebuilding the partition between its r-core and its r-quotient.

addVerticalRibbonStrip – Adding some ribbons to a partition

combinat::partitions::addVerticalRibbonStrip(partition part, list of nonnegative integers pos)

This function adds a ribbon to the partition math for each non-zero entries of the vector math. The length of the added ribbon is given by the value of the corresponding entry. By convention the first entry corresponds to the first line of the partition. This function returns the shape of the new partition and also the cumulative spin of the added ribbons.

removeVerticalRibbonStrip – Removing some ribbons in a partition

combinat::partitions::removeVerticalRibbonStrip(partition part, list of nonnegative integers pos)

This function removes a ribbon to the partition math for each non-zero entries of the vector math. The length of the removed ribbon is given by the value of the corresponding entry. By convention the first entry corresponds to the first line of the partition. This function returns the shape of the new partition and also the cumulative spin of the removed ribbons.

jacobiTrudy – Jacoby-Trudi formula

combinat::partitions::jacobiTrudy(partition math, <function f>, <domain coeffRing>)

This function computes the Jacobi-Trudy matrix associated to the partition part. Its determinant express the Schur polynomial associated to part on the basis of homogenous complete symmetric polynomials (see Macdonald I.-G., (1995), "Symmetric Functions and Hall Polynomials", Oxford Science Publication). By default the function argument is i -> h[i] and coeffRing is Dom::ExpressionField(). These two options allow to obtain matrix entries as true symmetric functions.

contains – tests if one partition contains another

combinat::partitions::contains(partition math, partition part2)

This function returns TRUE if both part1 and part2 are both partitions and part2 is contained in part1 (that is, each part of part2 is weakly smaller than the corresponding part of part1).

lequalYoungLattice – equivalent to the function contains

Example 1:

There are math partitions of math:

combinat::partitions::count(4)

math

Here is the list:

combinat::partitions::list(4)

math

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)

math

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])

math

combinat::partitions::Next returns FAIL when the input is the last partition:

combinat::partitions::Next([1, 1, 1, 1])

math

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()

math

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]

Example 2:

The options Length, MinLength, and MaxLength can be used to set length constraints. This is the list of the partitions of math of length math:

combinat::partitions::list(4, Length=2)

math

This is the list of the partitions of math of length at least math:

combinat::partitions::list(4, MinLength=2)

math

This is the list of the partitions of math of length at most math:

combinat::partitions::list(4, MaxLength=2)

math

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 math of length math:

combinat::partitions::list(4, MinLength=2, MaxLength=2)

math

Example 3:

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 math with all parts at most math:

combinat::partitions::list(4, MaxPart=2)

math

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 math with all parts at least math:

combinat::partitions::list(4, MinPart=2)

math

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 math with math nonnegative parts:

combinat::partitions::list(4, Length=3, MinPart=0)

math

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 math with at least math nonnegative parts:

combinat::partitions::list(4, MinLength=3, MinPart=0)

math

Example 4:

The options Inner, and Outer can be used to set part-by-part inclusion constraints. This is the list of the partitions of math with [3, 1, 1] as an outer bound:

combinat::partitions::list(4, Outer=[3, 1, 1])

math

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 math of length at most math such that that the second and third part are math when they exists:

combinat::partitions::list(4, Outer=[infinity, 1, 1])

math

This is the list of the partitions of math with [1, 1, 1] as an inner bound:

combinat::partitions::list(4, Inner=[1, 1, 1])

math

Example 5:

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 math:

combinat::partitions::list(4, MaxSlope=-1)

math

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)

math

This is the list of the partitions of math such that the difference between two consecutive parts is at least math:

combinat::partitions::list(4, MinSlope=-1)

math

This is the list of increasing partitions of math:

combinat::partitions::list(4, MaxSlope=infinity, MinSlope=0)

math

Example 6:

The constraints can be combined together in all reasonable ways. This is the list of the partitions of math of length between math and math such that the difference between two consecutive parts is between math and math:

combinat::partitions::list(11,

MaxSlope=-1, MinSlope=-3,

MinLength=2, MaxLength=4)

math

Idem with an Outer constraint:

combinat::partitions::list(11,

MaxSlope=-1, MinSlope=-3,

MinLength=2, MaxLength=4,

Outer=[6,5,2])

math

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)

math

Example 7:

This is the conjugate of the partition [4, 1]:

combinat::partitions::conjugate([4, 1])

math

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])

math

Example 8:

We describe how to generate math-regular partitions. Recall that a partition p is math-regular if no part is repeated more than math times, or, equivalently, if the difference between any two consecutive parts of the conjugate partition pc is at most math. Here is a first (buggy) attempt to get the math-regular partitions of math:

map(combinat::partitions::list(7, MinSlope=-2),

combinat::partitions::conjugate)

math

This is not quite correct: in [2,2,2,1], the first part is repeated math times. Here is what happened: this math 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 math regular partitions of math:

map(combinat::partitions::list(7, MinSlope=-2, MinPart=0,

Length=7+1), combinat::partitions::conjugate)

math

This trick is efficient, and can be refined further to generate regular partitions with length, part, or inclusion constraints.

Example 9:

This is the exponential notation of the partition [4, 1]:

combinat::partitions::toExp([6,4,4,2,1])

math

It can be converted back to the original partition:

combinat::partitions::fromExp([1, 1, 0, 2, 0, 1])

math

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);

math

In any cases, converting back yields the original partition:

combinat::partitions::fromExp([1, 1, 0, 2, 0, 1, 0, 0, 0]);

math

Example 10:

This example shows how to compute the corners of a partition.

combinat::partitions::corners([4, 3, 1])

math

The corners can be represented graphically:

combinat::partitions::printPrettyCorners([4, 3, 1])

+---+

| * |

+---+---+---+

| | | * |

+---+---+---+---+

| | | | * |

+---+---+---+---+

Here is a more compact representation:

combinat::partitions::printCompactCorners([4, 3, 1])

##*

###*

Example 11:

Example of computation of a r-core and r-quotient of a partition:

combinat::partitions::rCore([6,3,2,2],3);

combinat::partitions::rQuotient([7,7,5,3,3,3,1],3)

math

Rebuilding a partition from its r-core and its r-quotient:

combinat::partitions::fromCoreAndQuotient([2,1],[[2,1],[3],[1,1,1]]);

math

Example 12:

These are two example of adding and removing a vertical ribbon strip to a partition

combinat::partitions::addVerticalRibbonStrip([4, 3, 1], [2, 0, 0, 0, 2])

[画像:math]

combinat::partitions::removeVerticalRibbonStrip([4, 3, 1], [0, 2, 0])

math

Example 13:

combinat::partitions::jacobiTrudy([4, 3, 1])

[画像:math]

combinat::partitions::jacobiTrudy([4, 3, 1], T)

[画像:math]

Background:

Partitions are naturally ordered lexicographically. The functions for counting and generating are directly inherited from Cat::IntegerListsLexClass with, by default, MaxSlope=0, and MinPart=1. The complexity of the generation algorithm is constant time amortized for each partition generated.
Without optional constraints, counting is done efficiently with Euler's pentagonal formula for small values of math and Hardy-Ramanujan-Rademacher's formula otherwise.

In all other cases, counting is done by brute force generation.

Changes in MuPAD 3.1

combinat::partitions(n) is now an alias for combinat::partitions::list (n), as in the other combinatorial classes.