18.9 Compositions

Module: sage.combinat.composition

Compositions

A composition c of a nonnegative integer n is a list of positive integers with total sum n.

There are 8 compositions of 4.

sage: Compositions(4).count()
8

Here is the list of them:

sage: Compositions(4).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1],
[4]]

You can use the .first() method to get the 'first' composition of a number.

sage: Compositions(4).first()
[1, 1, 1, 1]

You can also calculate the 'next' composition given the current one.

sage: Compositions(4).next([1,1,2])
[1, 2, 1]

The following examples shows how to test whether or not an object is a composition.

sage: [3,4] in Compositions()
True
sage: [3,4] in Compositions(7)
True
sage: [3,4] in Compositions(5)
False

Similarly, one can check whether or not an object is a composition which satisfies further constraints.

sage: [4,2] in Compositions(6, inner=[2,2], min_part=2)
True
sage: [4,2] in Compositions(6, inner=[2,2], min_part=2)
True
sage: [4,2] in Compositions(6, inner=[2,2], min_part=3)
False

Note that the given constraints should compatible.

sage: [4,1] in Compositions(5, inner=[2,1], min_part=1)
True

The options length, min_length, and max_length can be used to set length constraints on the compositions. For example, the compositions of 4 of length equal to, at least, and at most 2 are given by:

sage: Compositions(4, length=2).list()
[[1, 3], [2, 2], [3, 1]]
sage: Compositions(4, min_length=2).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]
sage: Compositions(4, max_length=2).list()
[[1, 3], [2, 2], [3, 1], [4]]

Setting both min_length and max_length to the same value is equaivalent to setting length to this value.

sage: Compositions(4, min_length=2, max_length=2).list()
[[1, 3], [2, 2], [3, 1]]

The options inner and outer can be used to set part-by-part containment constaints. The list of compositions of 4 bounded above by [3,1,2] is given by:

sage: Compositions(4, outer=[3,1,2]).list()
[[1, 1, 2], [2, 1, 1], [3, 1]]

Outer sets max_length 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:

sage: Compositions(4, outer=[1,oo,1]).list()
[[1, 2, 1], [1, 3]]

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

sage: Compositions(4, inner=[1,1,1]).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1]]

The options min_slope and max_slope can be used to set constraints on the slope, that is the difference p[i+1]-p[i] of two consecutive parts. The following is the list of weakly increasing compositions of 4.

sage: Compositions(4, min_slope=0).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

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

sage: Compositions(4, min_slope=-1, max_slope=1).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2], [4]]

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

sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4).list()
[[1, 1, 1, 2],
 [1, 1, 2, 1],
 [1, 2, 1, 1],
 [1, 2, 2],
 [2, 1, 1, 1],
 [2, 1, 2],
 [2, 2, 1],
 [2, 3],
 [3, 1, 1],
 [3, 2]]

We can do the same thing with an outer constraint:

sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4, outer=[2,5,2]).list()
[[1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 3]]

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.

Author: -Mike Hansen -MuPAD-Combinat developers (for algorithms and design inspiration)

Module-level Functions

Composition( [co=None], [descents=None], [code=None])

Returns a composition object.

The standard way to create a composition is by specifying it as a list.

sage: Composition([3,1,2])
[3, 1, 2]

You can create a composition from a list of its descents.

sage: Composition([1, 1, 3, 4, 3]).descents()
[0, 1, 4, 8, 11]
sage: Composition(descents=[1,0,4,8,11])
[1, 1, 3, 4, 3]

You can also create a composition from its code.

sage: Composition([4,1,2,3,5]).to_code()
[1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
sage: Composition(code=_)          
[4, 1, 2, 3, 5]
sage: Composition([3,1,2,3,5]).to_code()
[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
sage: Composition(code=_)
[3, 1, 2, 3, 5]

Compositions( [n=None])

Returns the combinatorial class of compositions.

If n is not specificied, it returns the combinatorial class of all (non-negative) integer compositions.

sage: Compositions()
Compositions of non-negative integers
sage: [] in Compositions()
True
sage: [2,3,1] in Compositions()
True
sage: [-2,3,1] in Compositions()
False

If n is specified, it returns the class of compositions of n.

sage: Compositions(3)
Compositions of 3
sage: Compositions(3).list()
[[1, 1, 1], [1, 2], [2, 1], [3]]
sage: Compositions(3).count()
4

In addition, the following constaints can be put on the compositions: length, min_part, max_part, min_length, max_length, min_slope, max_slope, inner, and outer. For example,

sage: Compositions(3, length=2).list()
[[1, 2], [2, 1]]
sage: Compositions(4, max_slope=0).list()
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]

from_code( code)

Return the composition from its code.The code of a composition is a list of length self.size() of 1s and 0s such that there is a 1 wherever a new part starts.

sage: import sage.combinat.composition as composition
sage: Composition([4,1,2,3,5]).to_code()
[1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
sage: composition.from_code(_)          
[4, 1, 2, 3, 5]
sage: Composition([3,1,2,3,5]).to_code()
[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
sage: composition.from_code(_)          
[3, 1, 2, 3, 5]

from_descents( descents, [nps=None])

Returns a composition from the list of descents.

sage: Composition([1, 1, 3, 4, 3]).descents()
[0, 1, 4, 8, 11]
sage: sage.combinat.composition.from_descents([1,0,4,8],12)
[1, 1, 3, 4, 3]
sage: sage.combinat.composition.from_descents([1,0,4,8,11])
[1, 1, 3, 4, 3]

Class: Composition_class

class Composition_class

Functions: complement,$ \,$ conjugate,$ \,$ descents,$ \,$ is_finer,$ \,$ major_index,$ \,$ peaks,$ \,$ refinement,$ \,$ to_code,$ \,$ to_skew_partition

complement( self)

Returns the complement of the composition co. The complement is the reverse of co's conjugate composition.

sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate()
[1, 1, 3, 3, 1, 3]
sage: Composition([1, 1, 3, 1, 2, 1, 3]).complement()
[3, 1, 3, 3, 1, 1]

conjugate( self)

Returns the conjugate of the composition comp.

Algorithm from mupad-combinat.

sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate()  
[1, 1, 3, 3, 1, 3]

descents( self, [final_descent=False])

Returns the list of descents of the composition co.

sage: Composition([1, 1, 3, 1, 2, 1, 3]).descents()
[0, 1, 4, 5, 7, 8, 11]

is_finer( self, co2)

Returns True if the composition self is finer than the composition co2; otherwise, it returns False.

sage: Composition([4,1,2]).is_finer([3,1,3])
False
sage: Composition([3,1,3]).is_finer([4,1,2])
False
sage: Composition([1,2,2,1,1,2]).is_finer([5,1,3])
True
sage: Composition([2,2,2]).is_finer([4,2])
True

major_index( self)

Returns the major index of the composition co. The major index is defined as the sum of the descents.

sage: Composition([1, 1, 3, 1, 2, 1, 3]).major_index()
31

peaks( self)

Returns a list of the peaks of the composition self.

The peaks are the positions i in the compositions such that self[i-1] < self[i] > self[i+1]. Note that len(self)-1 is never a peak.

sage: Composition([1, 1, 3, 1, 2, 1, 3]).peaks()
[2, 4]

refinement( self, co2)

Returns the refinement composition of self and co2.

sage: Composition([1,2,2,1,1,2]).refinement([5,1,3])
[3, 1, 2]

to_code( self)

Returns the code of the composition self. The code of a composition is a list of length self.size() of 1s and 0s such that there is a 1 wherever a new part starts.

sage: Composition([4,1,2,3,5]).to_code()
[1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]

to_skew_partition( self, [overlap=1])

Returns the skew partition obtained from the composition co. The parameter overlap indicates the number of boxes that are covered by boxes of the previous line.

sage: Composition([3,4,1]).to_skew_partition()
[[6, 6, 3], [5, 2]]
sage: Composition([3,4,1]).to_skew_partition(overlap=0)
[[8, 7, 3], [7, 3]]

Class: Compositions_all

class Compositions_all
Compositions_all( self)

TESTS:

sage: C = Compositions()
sage: C == loads(dumps(C))
True

Functions: list

list( self)

TESTS:

sage: Compositions().list()
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: [2,1,3] in Compositions()
True
sage: [] in Compositions()
True
sage: [-2,-1] in Compositions()
False
sage: [0,0] in Compositions()
True

__repr__( self)

TESTS:

sage: repr(Compositions())
'Compositions of non-negative integers'

Class: Compositions_constraints

class Compositions_constraints
Compositions_constraints( self, n)

sage: C = Compositions(4, length=2)
sage: C == loads(dumps(C))
True

Functions: count,$ \,$ list

count( self)

sage: Compositions(4, length=2).count()
3
sage: Compositions(4, min_length=2).count()
7
sage: Compositions(4, max_length=2).count()
4
sage: Compositions(4, max_part=2).count()
5
sage: Compositions(4, min_part=2).count()
2
sage: Compositions(4, outer=[3,1,2]).count()
3

list( self)

Returns a list of all the compositions of n.

sage: Compositions(4, length=2).list()
[[1, 3], [2, 2], [3, 1]]
sage: Compositions(4, min_length=2).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]
sage: Compositions(4, max_length=2).list()
[[1, 3], [2, 2], [3, 1], [4]]
sage: Compositions(4, max_part=2).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
sage: Compositions(4, min_part=2).list()
[[2, 2], [4]]
sage: Compositions(4, outer=[3,1,2]).list()
[[1, 1, 2], [2, 1, 1], [3, 1]]
sage: Compositions(4, outer=[1,'inf',1]).list()
[[1, 2, 1], [1, 3]]
sage: Compositions(4, inner=[1,1,1]).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1]]
sage: Compositions(4, min_slope=0).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
sage: Compositions(4, min_slope=-1, max_slope=1).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2], [4]]
sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4).list()
[[1, 1, 1, 2],
 [1, 1, 2, 1],
 [1, 2, 1, 1],
 [1, 2, 2],
 [2, 1, 1, 1],
 [2, 1, 2],
 [2, 2, 1],
 [2, 3],
 [3, 1, 1],
 [3, 2]]
sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4, outer=[2,5,2]).list()
[[1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 3]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: [2, 1] in Compositions(3, length=2)
True
sage: [2,1,2] in Compositions(5, min_part=1)
True
sage: [2,1,2] in Compositions(5, min_part=2)
False

__repr__( self)

TESTS:

sage: repr(Compositions(6, min_part=2, length=3))
'Compositions of 6 with constraints length=3, min_part=2'

Class: Compositions_n

class Compositions_n
Compositions_n( self, n)

TESTS:

sage: C = Compositions(3)
sage: C == loads(dumps(C))
True

Functions: count,$ \,$ list

count( self)

TESTS:

sage: Compositions(3).count()
4
sage: Compositions(0).count()
1

list( self)

TESTS:

sage: Compositions(4).list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1],
[4]]
sage: Compositions(0).list()
[[]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: [2,1,3] in Compositions(6)
True
sage: [2,1,2] in Compositions(6)
False
sage: [] in Compositions(0)
True
sage: [0] in Compositions(0)
True

__repr__( self)

TESTS:

sage: repr(Compositions(3))
'Compositions of 3'

See About this document... for information on suggesting changes.