combinat::compositions – compositions of an integer
The library combinat::compositions provides functions for counting, generating, and manipulating compositions.
Superdomain
Categories
Axioms
Related Domains:
combinat::partitions , combinat::words
Details:
A compositionc of a nonnegative integer n is a list of positive integers with total sum n.
All functions for counting and generating accept the following optional constraints on the compositions: MinLength, MaxLength, Length, MinPart, MaxPart, Inner, Outer, MinSlope, and MaxSlope. Cf. examples 3 , 4 , 5 , 6 , and 7 .
Generally, compositions of math are used to encode subsets of math through the bijection: math. The set math is called the descents set of the composition math. The converse bijection is given by
math.
In MuPAD the descents set can be stored as a set or as a list.
The inclusion of descents sets gives rise to a partial order on compositions:
math.
This order is called the refinement order; the composition math is said to be finer than math, while math is said to be fatter than math. This order can be interpreted on compositions as follows: math is finer than math if math can be obtained from math by summing up together some consecutive parts of math:
[画像:math];
the composition math is called the refinement composition of the pair math.
Entries
"domtype"
The MuPAD domain of compositions: DOM_LIST
isA – test if an object is a composition
combinat::compositions::isA(any type co, <nonnegative integer n, <constraints>>)
Returns whether co is a composition.
If the optional argument n is present, returns whether co is a composition of n.
If constraints are given, returns whether co is a composition satisfying constraints.
count – number of compositions
combinat::compositions::count(nonnegative integer math, <constraints>)
Returns the number of compositions of n satisfying constraints.
generator – generator for compositions
combinat::compositions::generator(nonnegative integer math, <constraints>)
Returns a generator for the compositions of n satisfying constraints.
list – list of the compositions
combinat::compositions::list(nonnegative integer math, <constraints>)
Returns the list of the compositions of n satisfying constraints.
first – first composition
combinat::compositions::first(nonnegative integer math, <constraints>)
Returns the first composition of n satisfying constraints or FAIL if there is none.
Next – next composition
combinat::compositions::Next(composition math, <constraints>)
Returns the composition following c satisfying constraints or FAIL if there is none.
descents – descents of a composition
combinat::compositions::descents(composition c)
Returns the list of descents of the composition c
descentsSet – descents of a composition
combinat::compositions::descentsSet(composition c)
Returns the set of descents of the composition c
fromDescents – composition of given descents
combinat::compositions::fromDescents(descent set s)
combinat::compositions::fromDescents(descent list l)
Returns the composition c whose descents set is s or l
majorIndex – major index of a composition
combinat::compositions::majorIndex(composition c)
Returns the major index composition c, defined as the sum of the descents.
isFiner – compare two compositions for the refinement order
combinat::compositions::isFiner(composition c1, composition c2)
Returns whether the composition c1 is finer than the composition c2.
finer – compositions finer than a composition
combinat::compositions::finer(composition c)
Returns the compositions finer than c. Note that compositons::finer is a full combinatorial class that implement the standard methods compositions::finer::count and compositions::finer::generators.
refinement – refinement compositions of a pair of compositions
combinat::compositions::refinement(composition c, composition d)
Returns the refinement compositions of the pair c,d. If c is not finer than d then returns FAIL .
fatter – compositions fatter than a composition
combinat::compositions::fatter(composition c)
Returns the compositions fatter than c. Note that compositons::fatter is a combinatorial class that implement the standard methods compositions::fatter::count and compositions::fatter::generators.
toSkewPartition – skew partition corresponding to a composition
combinat::compositions::toSkewPartition(composition math, <nonnegative integer cover>)
Returns the skew partition corresponding to c. To a composition we can associate a skew partition where the length of the i-th line is the i-th part of the composition and the first cover cells are under the cells of the previous line. The default value for cover is 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);
math
math
math
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);
math
math
Please note that given constraints should be compatible:
combinat::compositions::isA([4,1], 5, Inner=[2, 1], MinPart=2);
math
See further examples for other constraints.
There are math compositions of math:
combinat::compositions::count(4)
math
Here is the list:
combinat::compositions::list(4)
math
You can use the function combinat::compositions::first to get the "first" composition of a number:
combinat::compositions::first(4)
math
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])
math
combinat::compositions::Next returns FAIL when the input is the last composition:
combinat::compositions::Next([1, 1, 1, 1])
math
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();
math
math
math
math
math
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]
The options Length, MinLength, and MaxLength can be used to set length constraints. This is the list of the compositions of math of length math:
combinat::compositions::list(4, Length=2)
math
This is the list of the compositions of math of length at least math:
combinat::compositions::list(4, MinLength=2)
math
This is the list of the compositions of math of length at most math:
combinat::compositions::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 compositions of math of length math:
combinat::compositions::list(4, MinLength=2, MaxLength=2)
math
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 math with all parts at most math:
combinat::compositions::list(4, MaxPart=2)
math
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 math with all parts at least math:
combinat::compositions::list(4, MinPart=2)
math
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 math with math nonnegative parts:
combinat::compositions::list(4, Length=3, MinPart=0)
math
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 math with math or math nonnegative parts:
combinat::compositions::list(4, MinLength=2, MaxLength=3, MinPart=0)
math
The options Inner, and Outer can be used to set part-by-part containment constraints. This is the list of the compositions of math bounded above by [3, 1, 2]:
combinat::compositions::list(4, Outer=[3, 1, 2])
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 compositions of math of length at most math such that the first and third parts are at most math:
combinat::compositions::list(4, Outer=[1, infinity, 1])
math
This is the list of compositions of math bounded below by [1, 1, 1]:
combinat::compositions::list(4, Inner=[1, 1, 1])
math
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 math:
combinat::compositions::list(4, MinSlope=0)
math
This is the list of compositions of math such that two consecutive parts differ by at most one unit:
combinat::compositions::list(4, MinSlope=-1, MaxSlope=1)
math
The constraints can be combined together in all reasonable ways. This is the list of compositions of math of length between math and math such that the difference between two consecutive parts is between math and math:
combinat::compositions::list(5,
MaxSlope=1, MinSlope=-2,
MinLength=2, MaxLength=4)
math
Idem with an Outer constraint:
combinat::compositions::list(5,
MaxSlope=1, MinSlope=-2,
MinLength=2, MaxLength=4,
Outer=[2,5,2])
math
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)
math
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])
math
math
To get the list of compositions finer than [4,1,2], you can use:
combinat::compositions::finer::list([4,1,2]);
math
The composition [1, 2, 2, 1, 1, 2] is finer than the composition [5,1,3]:
combinat::compositions::isFiner([1, 2, 2, 1, 1, 2], [5, 1, 3])
math
The reason is that [1, 2, 2] is a composition of 5, [1] is a composition of 1 and [1, 2] is a composition of 3. The lengths [3, 1, 2] of [1, 2, 2], [1], [1, 2] is the refinement composition and is computed by MuPAD by the command:
combinat::compositions::isFiner([1, 2, 3, 1, 2], [5, 1, 3]);
combinat::compositions::refinement([1, 2, 2, 1, 1, 2], [5, 1, 3])
math
math
To get the list of compositions fatter than [4,1,2], you can use:
combinat::compositions::fatter::list([4,1,2]);
math
If you only want their number, you can ask:
combinat::compositions::fatter::count([4,1,2]);
math
Conversion from compositions to skew partitions with two values for the covering parameter.
combinat::skewPartitions::printPretty(combinat::compositions::toSkewPartition([3, 4, 1]))
+---+---+---+
| | | |
+---+---+---+---+---+---+
| | | | |
+---+---+---+---+
| |
+---+
combinat::skewPartitions::printPretty(combinat::compositions::toSkewPartition([3, 4, 1], 0))
+---+---+---+
| | | |
+---+---+---+---+---+---+---+
| | | | |
+---+---+---+---+---+
| |
+---+
An equivalent way to have the same output is to call combinat::compositions::printPretty with the composition and the optional covering paramater.
Background:
Compositions are naturally ordered lexicographically. The functions for counting and generating are directly inherited from Cat::IntegerListsLexClass with, by default, MinPart=1. The complexity of the generation algorithm is constant time amortized for each composition generated.
Except for the trivial cases, counting is done by brute force generation.
