[Previous] [Next] [Contents]

combinat::compositions -- compositions of an integer

Introduction

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

Details

Categories

Cat::IntegerListsLexClass

Related Domains

combinat::partitions, combinat::words

Entries

domtype

The MuPAD domain of compositions: DOM_LIST

Method isA: test if an object is a composition

Method count: number of compositions

Method generator: generator for compositions

Method list: list of the compositions

Method first: first composition

Method Next: next composition

Method descents: descents of a composition

Method descentsSet: descents of a composition

Method fromDescents: composition of given descents

Method majorIndex: major index of a composition

Method isFiner: compare two compositions for the refinement order

Method finer: compositions finer than a composition

Method fatter: compositions fatter than a composition

Example 1

This example shows how to test if an object is of type combinat::compositions:

>> combinat::compositions::isA([3,4]);
   combinat::compositions::isA([3,4],7);
   combinat::compositions::isA([3,4],5);
                                   TRUE
       
                                   TRUE
       
                                   FALSE

The combinat::compositions::isA function admets the same constraints than other functions in the package.

>> combinat::compositions::isA([4,2], 6, Inner=[2, 2], MinPart=2);
   combinat::compositions::isA([4,2], 6, Inner=[2, 2], MaxPart=4);
                                   TRUE
       
                                   TRUE

Please note that given constraints should be compatible:

>> combinat::compositions::isA([4,1], 5, Inner=[2, 1], MinPart=2); 
                                   TRUE

See further examples for other constraints.

Example 2

There are 8 compositions of 4:

>> combinat::compositions::count(4)
                                     8

Here is the list:

>> combinat::compositions::list(4)
      [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],
      
         [1, 1, 1, 1]]

You can use the function combinat::compositions::first to get the ``first'' composition of a number:

>> combinat::compositions::first(4)
                                    [4]

Using combinat::compositions::Next, you can calculate the ``next'' composition. This function takes as argument the composition relative to which you want the next one:

>> combinat::compositions::Next([4])
                                  [3, 1]

combinat::compositions::Next returns FAIL when the input is the last composition:

>> combinat::compositions::Next([1, 1, 1, 1])
                                   FAIL

When you want to run through the compositions of a number, you can generate them one by one to save memory:

>> g := combinat::compositions::generator(3):
   g(); g(); g(); g(); g();
                                    [3]
      
                                  [2, 1]
      
                                  [1, 2]
      
                                 [1, 1, 1]
      
                                   FAIL

Typically, this would be used as follows:

>> g := combinat::compositions::generator(3):
   while (p := g()) <> FAIL do print(p): end:
                                    [3]
      
                                  [2, 1]
      
                                  [1, 2]
      
                                 [1, 1, 1]

Example 3

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

>> combinat::compositions::list(4, Length=2)
     
                         [[3, 1], [2, 2], [1, 3]]
        

This is the list of the compositions of 4 of length at least 2:

>> combinat::compositions::list(4, MinLength=2)
     
      [[3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],
      
         [1, 1, 1, 1]]
        

This is the list of the compositions of 4 of length at most 2:

>> combinat::compositions::list(4, MaxLength=2)
     
                       [[4], [3, 1], [2, 2], [1, 3]]
        

Setting both MinLength and MaxLength to the same value is equivalent to setting Length to this value. This is again the list of the compositions of 4 of length 2:

>> combinat::compositions::list(4, MinLength=2, MaxLength=2)
     
                         [[3, 1], [2, 2], [1, 3]]
        

Example 4

The options MinPart and MaxPart can be used to set constraints on the sizes of all parts. Using MaxPart, you can select compositions having only small entries. This is the list of the compositions of 4 with all parts at most 2:

>> combinat::compositions::list(4, MaxPart=2)
     
          [[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
        

MinPart is complementary to MaxPart and selects compositions having only large parts (it takes a non-negative value). This is the list of the compositions of 4 with all parts at least 2:

>> combinat::compositions::list(4, MinPart=2)
     
                               [[4], [2, 2]]
        

By default, the parts of a composition 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 compositions of 4 with 3 nonnegative parts:

>> combinat::compositions::list(4, Length=3, MinPart=0)
     
      [[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1],
      
         [2, 0, 2], [1, 3, 0], [1, 2, 1], [1, 1, 2], [1, 0, 3],
      
         [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
        

If the list you ask for is infinite, the program will not finish, as it is be the case for combinat::compositions::list(4, MinPart=0);

Two compositions are considered equivalent whenever they differ only by trailing zeroes. Whenever two equivalent compositions satisfy the constraints, only the shortest one is considered. Hence, this is the list of compositions of 4 with 2 or 3 nonnegative parts:

>> combinat::compositions::list(4, MinLength=2, MaxLength=3, MinPart=0)
     
      [[4, 0], [3, 1], [3, 0, 1], [2, 2], [2, 1, 1], [2, 0, 2],
      
         [1, 3], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4], [0, 3, 1],
      
         [0, 2, 2], [0, 1, 3], [0, 0, 4]]
        

Example 5

The options Inner, and Outer can be used to set part-by-part containment constraints. This is the list of the compositions of 4 bounded above by [3, 1, 2]:

>> combinat::compositions::list(4, Outer=[3, 1, 2])
     
                      [[3, 1], [2, 1, 1], [1, 1, 2]]
        

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 compositions of 4 of length at most 3 such that the first and third parts are at most 1:

>> combinat::compositions::list(4, Outer=[1, infinity, 1])
     
                            [[1, 3], [1, 2, 1]]
        

This is the list of compositions of 4 bounded below by [1, 1, 1]:

>> combinat::compositions::list(4, Inner=[1, 1, 1])
     
              [[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
        

Example 6

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 increasing compositions of 4:

>> combinat::compositions::list(4, MinSlope=0)
     
              [[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]
        

This is the list of compositions of 4 such that two consecutive parts differ by at most one unit:

>> combinat::compositions::list(4, MinSlope=-1, MaxSlope=1)
     
       [[4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
        

Example 7

The constraints can be combined together in all reasonable ways. This is the list of compositions of 5 of length between 2 and 4 such that the difference between two consecutive parts is between -2 and 1:

>> combinat::compositions::list(5,
                                MaxSlope=1, MinSlope=-2,
                                MinLength=2, MaxLength=4)
     
      [[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2],
      
         [2, 1, 1, 1], [1, 2, 2], [1, 2, 1, 1], [1, 1, 2, 1],
      
         [1, 1, 1, 2]]
        

Idem with an Outer constraint:

>> combinat::compositions::list(5,
                                MaxSlope=1, MinSlope=-2,
                                MinLength=2, MaxLength=4,
                                Outer=[2,5,2])
     
                 [[2, 3], [2, 2, 1], [2, 1, 2], [1, 2, 2]]
        

However, providing incoherent constraints may yield strange results. It is up to the user to ensure that the Inner and Outer compositions themselves satisfy the parts and slope constraints:

>> combinat::compositions::list(5, Inner=[2, 1], MinPart=2)  
     
                    [[4, 1], [3, 2], [2, 3], [2, 1, 2]]
        

Example 8

One can check that those two compositions are not comparable for the refinement order:

>> combinat::compositions::isFiner([4,1,2],[3,1,3]);
   combinat::compositions::isFiner([3,1,3],[4,1,2]);
     
                                   FALSE
      
                                   FALSE
        

To get the list of compositions finer than [4,1,2], you can use:

>> combinat::compositions::finer([4,1,2]);
     
      [[4, 1, 2], [4, 1, 1, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1],
      
         [2, 2, 1, 2], [2, 2, 1, 1, 1], [2, 1, 1, 1, 2],
      
         [2, 1, 1, 1, 1, 1], [1, 3, 1, 2], [1, 3, 1, 1, 1],
      
         [1, 2, 1, 1, 2], [1, 2, 1, 1, 1, 1], [1, 1, 2, 1, 2],
      
         [1, 1, 2, 1, 1, 1], [1, 1, 1, 1, 1, 2],
      
         [1, 1, 1, 1, 1, 1, 1]]
        

To get the list of compositions fatter than [4,1,2], you can use:

>> combinat::compositions::fatter([4,1,2]);
     
                     [[7], [5, 2], [4, 3], [4, 1, 2]]
        

If you only want their number, you can ask:

>> combinat::compositions::fatter::count([4,1,2]);
     
                                     4
        

Background

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package