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.

OUTPUT:

  • The class of composition tableaux of size n.