# Composition Tableaux#

AUTHORS:

• Chris Berg, Jeff Ferreira (2012-9): Initial version

class sage.combinat.composition_tableau.CompositionTableau(parent, t)[source]#

Bases: CombinatorialElement

A composition tableau.

A composition tableau $$t$$ of shape $$I = (I_1, \ldots, I_{\ell})$$ is an array of boxes in rows, $$I_i$$ boxes in row $$i$$, filled with positive integers such that:

1. the entries in the rows of $$t$$ weakly decrease from left to right,

2. the left-most column of $$t$$ strictly increase from top to bottom.

3. Add zero entries to the rows of $$t$$ until the resulting array is rectangular of shape $$\ell \times m$$. For $$1 \leq i < j \leq \ell, 2 \leq k \leq m$$ and $$(t(j,k) \neq 0$$, and also if $$t(j,k) \geq t(i,k))$$ implies $$t(j,k) > t(i,k-1).$$

INPUT:

• t – A list of lists

EXAMPLES:

sage: CompositionTableau([[1],[2,2]])
[[1], [2, 2]]
sage: CompositionTableau([[1],[3,2],[4,4]])
[[1], [3, 2], [4, 4]]
sage: CompositionTableau([])
[]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(2),Integer(2)]])
[[1], [2, 2]]
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]])
[[1], [3, 2], [4, 4]]
>>> CompositionTableau([])
[]
descent_composition()[source]#

Return the composition corresponding to the set of all $$i$$ that do not have $$i+1$$ appearing strictly to the left of $$i$$ in self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).descent_composition()
[1, 2, 2]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]]).descent_composition()
[1, 2, 2]
descent_set()[source]#

Return the set of all $$i$$ that do not have $$i+1$$ appearing strictly to the left of $$i$$ in self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).descent_set()
[1, 3]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]]).descent_set()
[1, 3]
is_standard()[source]#

Return True if self is a standard composition tableau and False otherwise.

EXAMPLES:

sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).is_standard()
False
sage: CompositionTableau([[2,1],[3],[4]]).is_standard()
True
>>> from sage.all import *
>>> CompositionTableau([[Integer(1),Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4),Integer(3)]]).is_standard()
False
>>> CompositionTableau([[Integer(2),Integer(1)],[Integer(3)],[Integer(4)]]).is_standard()
True
pp()[source]#

Return a pretty print string of self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).pp()
1
3  2
4  4
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]]).pp()
1
3  2
4  4
shape_composition()[source]#

Return a Composition object which is the shape of self.

EXAMPLES:

sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).shape_composition()
[2, 2, 3]
sage: CompositionTableau([[2,1],[3],[4]]).shape_composition()
[2, 1, 1]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1),Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4),Integer(3)]]).shape_composition()
[2, 2, 3]
>>> CompositionTableau([[Integer(2),Integer(1)],[Integer(3)],[Integer(4)]]).shape_composition()
[2, 1, 1]
shape_partition()[source]#

Return a partition which is the shape of self sorted into weakly decreasing order.

EXAMPLES:

sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).shape_partition()
[3, 2, 2]
sage: CompositionTableau([[2,1],[3],[4]]).shape_partition()
[2, 1, 1]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1),Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4),Integer(3)]]).shape_partition()
[3, 2, 2]
>>> CompositionTableau([[Integer(2),Integer(1)],[Integer(3)],[Integer(4)]]).shape_partition()
[2, 1, 1]
size()[source]#

Return the number of boxes in self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).size()
5
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]]).size()
5
weight()[source]#

Return a composition where entry $$i$$ is the number of times that $$i$$ appears in self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).weight()
[1, 1, 1, 2, 0]
>>> from sage.all import *
>>> CompositionTableau([[Integer(1)],[Integer(3),Integer(2)],[Integer(4),Integer(4)]]).weight()
[1, 1, 1, 2, 0]
class sage.combinat.composition_tableau.CompositionTableaux(**kwds)[source]#

Bases: UniqueRepresentation, Parent

Composition tableaux.

INPUT:

Keyword arguments:

• size – the size of the composition tableaux

• shape – the shape of the composition tableaux

• max_entry – the maximum entry for the composition tableaux

Positional arguments:

• The first argument is interpreted as size or shape depending on whether it is an integer or a composition.

EXAMPLES:

sage: CT = CompositionTableaux(3); CT
Composition Tableaux of size 3 and maximum entry 3
sage: list(CT)
[[[1], [2], [3]],
[[1], [2, 2]],
[[1], [3, 2]],
[[1], [3, 3]],
[[2], [3, 3]],
[[1, 1], [2]],
[[1, 1], [3]],
[[2, 1], [3]],
[[2, 2], [3]],
[[1, 1, 1]],
[[2, 1, 1]],
[[2, 2, 1]],
[[2, 2, 2]],
[[3, 1, 1]],
[[3, 2, 1]],
[[3, 2, 2]],
[[3, 3, 1]],
[[3, 3, 2]],
[[3, 3, 3]]]

sage: CT = CompositionTableaux([1,2,1]); CT
Composition tableaux of shape [1, 2, 1] and maximum entry 4
sage: list(CT)
[[[1], [2, 2], [3]],
[[1], [2, 2], [4]],
[[1], [3, 2], [4]],
[[1], [3, 3], [4]],
[[2], [3, 3], [4]]]

sage: CT = CompositionTableaux(shape=[1,2,1],max_entry=3); CT
Composition tableaux of shape [1, 2, 1] and maximum entry 3
sage: list(CT)
[[[1], [2, 2], [3]]]

sage: CT = CompositionTableaux(2,max_entry=3); CT
Composition Tableaux of size 2 and maximum entry 3
sage: list(CT)
[[[1], [2]],
[[1], [3]],
[[2], [3]],
[[1, 1]],
[[2, 1]],
[[2, 2]],
[[3, 1]],
[[3, 2]],
[[3, 3]]]

sage: CT = CompositionTableaux(0); CT
Composition Tableaux of size 0 and maximum entry 0
sage: list(CT)
[[]]
>>> from sage.all import *
>>> CT = CompositionTableaux(Integer(3)); CT
Composition Tableaux of size 3 and maximum entry 3
>>> list(CT)
[[[1], [2], [3]],
[[1], [2, 2]],
[[1], [3, 2]],
[[1], [3, 3]],
[[2], [3, 3]],
[[1, 1], [2]],
[[1, 1], [3]],
[[2, 1], [3]],
[[2, 2], [3]],
[[1, 1, 1]],
[[2, 1, 1]],
[[2, 2, 1]],
[[2, 2, 2]],
[[3, 1, 1]],
[[3, 2, 1]],
[[3, 2, 2]],
[[3, 3, 1]],
[[3, 3, 2]],
[[3, 3, 3]]]

>>> CT = CompositionTableaux([Integer(1),Integer(2),Integer(1)]); CT
Composition tableaux of shape [1, 2, 1] and maximum entry 4
>>> list(CT)
[[[1], [2, 2], [3]],
[[1], [2, 2], [4]],
[[1], [3, 2], [4]],
[[1], [3, 3], [4]],
[[2], [3, 3], [4]]]

>>> CT = CompositionTableaux(shape=[Integer(1),Integer(2),Integer(1)],max_entry=Integer(3)); CT
Composition tableaux of shape [1, 2, 1] and maximum entry 3
>>> list(CT)
[[[1], [2, 2], [3]]]

>>> CT = CompositionTableaux(Integer(2),max_entry=Integer(3)); CT
Composition Tableaux of size 2 and maximum entry 3
>>> list(CT)
[[[1], [2]],
[[1], [3]],
[[2], [3]],
[[1, 1]],
[[2, 1]],
[[2, 2]],
[[3, 1]],
[[3, 2]],
[[3, 3]]]

>>> CT = CompositionTableaux(Integer(0)); CT
Composition Tableaux of size 0 and maximum entry 0
>>> list(CT)
[[]]
Element[source]#

alias of CompositionTableau

class sage.combinat.composition_tableau.CompositionTableauxBacktracker(shape, max_entry=None)[source]#

Bases: GenericBacktracker

A backtracker class for generating sets of composition tableaux.

get_next_pos(ii, jj)[source]#

EXAMPLES:

sage: from sage.combinat.composition_tableau import CompositionTableauxBacktracker
sage: T = CompositionTableau([[2,1],[5,4,3,2],[6],[7,7,6]])
sage: n = CompositionTableauxBacktracker(T.shape_composition())
sage: n.get_next_pos(1,1)
(1, 2)
>>> from sage.all import *
>>> from sage.combinat.composition_tableau import CompositionTableauxBacktracker
>>> T = CompositionTableau([[Integer(2),Integer(1)],[Integer(5),Integer(4),Integer(3),Integer(2)],[Integer(6)],[Integer(7),Integer(7),Integer(6)]])
>>> n = CompositionTableauxBacktracker(T.shape_composition())
>>> n.get_next_pos(Integer(1),Integer(1))
(1, 2)
class sage.combinat.composition_tableau.CompositionTableaux_all(max_entry=None)[source]#

All composition tableaux.

an_element()[source]#

Return a particular element of self.

EXAMPLES:

sage: CT = CompositionTableaux()
sage: CT.an_element()
[[1, 1], [2]]
>>> from sage.all import *
>>> CT = CompositionTableaux()
>>> CT.an_element()
[[1, 1], [2]]
class sage.combinat.composition_tableau.CompositionTableaux_shape(comp, max_entry=None)[source]#

Bases: CompositionTableaux

Composition tableaux of a fixed shape comp with a given max entry.

INPUT:

• comp – a composition.

• max_entry – a nonnegative integer. This keyword argument defaults to the size of comp.

an_element()[source]#

Return a particular element of CompositionTableaux_shape.

EXAMPLES:

sage: CT = CompositionTableaux([1,2,1])
sage: CT.an_element()
[[1], [2, 2], [3]]
>>> from sage.all import *
>>> CT = CompositionTableaux([Integer(1),Integer(2),Integer(1)])
>>> CT.an_element()
[[1], [2, 2], [3]]
class sage.combinat.composition_tableau.CompositionTableaux_size(n, max_entry=None)[source]#

Bases: CompositionTableaux

Composition tableaux of a fixed size $$n$$.

INPUT:

• n – a nonnegative integer.

• max_entry – a nonnegative integer. This keyword argument defaults to n.

OUTPUT:

• The class of composition tableaux of size n.