[Previous] [Next] [Contents]

combinat::partitions -- partitions of an integer

Introduction

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

Details

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

Method count: number of partitions

Method generator: generator for partitions

Method list: list of the partitions

Method first: first partition

Method Next: next partition

Method printPretty: graphic representation of a partition

Method printCompact: graphic representation of a partition

Method conjugate: conjugate of a partition

Method hooklengths: hooklengths of a partition

Method toExp: exponential notation of a partition

Method fromExp: partition from its exponential notation

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

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

Method corners: corners of a partition

Method printPrettyCorners: graphic representation of the corners of a partition

Method printCompactCorners: graphic representation of the corners of a partition

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

Changes

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package