[Previous] [Next] [Contents]

## `combinat::partitions` -- partitions of an integer

#### Introduction

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

#### Details

- A partition `p` of a nonnegative integer `n` is a non-increasing list of positive integers (the parts of the partition) with total sum `n`.

- All functions for counting and generating accept the following optional constraints on the partitions: MinLength, MaxLength, Length, MinPart, MaxPart, Inner, Outer, MinSlope, and MaxSlope. Cf. examples 2, 3, 4, 5, 6, and 8.

- A partition can be depicted by a diagram made of rows of boxes, where the number of boxes in the i-th row starting from the bottom is the i-th part of the partition. For example, this is the diagram of the partition `[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`.

#### Categories

`Cat::IntegerListsLexClass`

#### Related Domains

`combinat::compositions`, `combinat::tableaux`

#### Entries

domtype

The MuPAD domain used to represent partitions: `DOM_LIST`

#### Method isA: test if an object is a partition

- `isA(any type part <, nonnegative integer n <, constraints>>)`

- Returns whether `part` is a partition.
- If the optional argument `n` is present, returns whether `part` is a partition of `n`.
- If constraints are given, returns whether `part` is a partition satisfying `constraints`.

#### Method count: number of partitions

- `count(nonnegative integer n <, constraints>)`

- Returns the number of partitions of `n` satisfying `constraints`.

#### Method generator: generator for partitions

- `generator(nonnegative integer n <, constraints>)`

- Returns a generator for the partitions of `n` satisfying `constraints`.

#### Method list: list of the partitions

- `list(nonnegative integer n <, constraints>)`

- Returns the list of the partitions of `n` satisfying `constraints`.

#### Method first: first partition

- `first(nonnegative integer n <, constraints>)`

- Returns the first partition of `n` satisfying `constraints` or `FAIL` if there is none.

#### Method Next: next partition

- `Next(partition p <, constraints>)`

- Returns the partition following `p` satisfying `constraints` or `FAIL` if there is none.

#### Method printPretty: graphic representation of a partition

- `printPretty(partition p)`

- Returns a graphic representation of the partition as rows of boxes.

#### Method printCompact: graphic representation of a partition

- `printCompact(partition p)`

- Same as above, but in a more compact way, where each box is represented by `#`.

#### Method conjugate: conjugate of a partition

- `conjugate(partition p)`

- Returns the conjugate (or transposed) of the partition `p`. Geometrically, this operation amounts to a reflection of the diagram of the partition with respect to the main diagonal.

#### Method hooklengths: hooklengths of a partition

- `hooklengths(partition p)`

- Returns the list of the hook-lengths of the partition `p`.
- These lengths allow to enumerate standard Young tableaux of shape `p`. The formula was first discovered by Frame, Robinson, and Thrall in 1954.

#### Method toExp: exponential notation of a partition

- `toExp(partition p)`

- Returns the exponential notation of the partition `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)`

- Returns the exponential notation of the partition `p`, padded with zeroes to ensure a length at least `k`.
- See also `combinat::partitions::fromExp`.

#### Method fromExp: partition from its exponential notation

- `fromExp(list l)`

- Returns the partition `p` from its exponential notation `l`.
- See also `combinat::partitions::toExp`.

#### Method centralizerSize: size of the centralizer of a conjugacy class of the symmetric group

- `centralizerSize(partition p)`

- Returns the size of the centralizer of the conjugacy class of the symmetric group indexed by the partition `p`.

#### Method conjugacyClassSize: size of a conjugacy class of the symmetric group

- `conjugacyClassSize(partition p)`

- Returns the size of the conjugacy class of the symmetric group indexed by the partition `p`.
- Reference: A. Kerber, Älgebraic Combinatoric Via Finite Group Action", 1.3 p. 24.

#### Method corners: corners of a partition

- `corners(partition p)`

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

#### Method printPrettyCorners: graphic representation of the corners of a partition

- `printPrettyCorners(partition p)`

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

#### Method printCompactCorners: graphic representation of the corners of a partition

- `printCompactCorners(partition p)`

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

#### Example 1

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]

#### Example 2

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

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

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

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

#### Example 6

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

#### Example 7

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]

#### Example 8

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.

#### Example 9

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]

#### Example 10

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

                                       *
                                       ##*
                                       ###*

#### 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 n and Hardy-Ramanujan-Rademacher's formula otherwise.

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

#### Changes

- Calling `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)`.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package