Composition Tableaux

AUTHORS:

  • Chris Berg, Jeff Ferreira (2012-9): Initial version
class sage.combinat.composition_tableau.CompositionTableau(parent, t)

Bases: sage.combinat.combinat.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([])
[]
descent_composition()

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]
descent_set()

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]
is_standard()

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
pp()

Return a pretty print string of self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).pp()
1
3  2
4  4
shape_composition()

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]
shape_partition()

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]
size()

Return the number of boxes in self.

EXAMPLES:

sage: CompositionTableau([[1],[3,2],[4,4]]).size()
5
weight()

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]
class sage.combinat.composition_tableau.CompositionTableaux(**kwds)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.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 maximun 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 maximun 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)
[[]]
Element

alias of CompositionTableau

class sage.combinat.composition_tableau.CompositionTableauxBacktracker(shape, max_entry=None)

Bases: sage.combinat.backtrack.GenericBacktracker

A backtracker class for generating sets of composition tableaux.

get_next_pos(ii, jj)

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)
class sage.combinat.composition_tableau.CompositionTableaux_all(max_entry=None)

Bases: sage.combinat.composition_tableau.CompositionTableaux, sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets

All composition tableaux.

an_element()

Return a particular element of self.

EXAMPLES:

sage: CT = CompositionTableaux()
sage: CT.an_element()
[[1, 1], [2]]
class sage.combinat.composition_tableau.CompositionTableaux_shape(comp, max_entry=None)

Bases: sage.combinat.composition_tableau.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()

Return a particular element of CompositionTableaux_shape.

EXAMPLES:

sage: CT = CompositionTableaux([1,2,1])
sage: CT.an_element()
[[1], [2, 2], [3]]
class sage.combinat.composition_tableau.CompositionTableaux_size(n, max_entry=None)

Bases: sage.combinat.composition_tableau.CompositionTableaux

Composition tableaux of a fixed size n.

INPUT:

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

OUTUT:

  • The class of composition tableaux of size n.