Tableaux¶
AUTHORS:
- Mike Hansen (2007): initial version
- Jason Bandlow (2011): updated to use Parent/Element model, and many minor fixes
- Andrew Mathas (2012-13): completed the transition to the parent/element model begun by Jason Bandlow
- Travis Scrimshaw (11-22-2012): Added tuple options, changed
*katabolism*
to*catabolism*
. Cleaned up documentation. - Andrew Mathas (2016-08-11): Row standard tableaux added
- Oliver Pechenik (2018): Added increasing tableaux.
This file consists of the following major classes:
Element classes:
Factory classes:
Parent classes:
Tableaux_all
Tableaux_size
SemistandardTableaux_all
(facade class)SemistandardTableaux_size
SemistandardTableaux_size_inf
SemistandardTableaux_size_weight
SemistandardTableaux_shape
SemistandardTableaux_shape_inf
SemistandardTableaux_shape_weight
StandardTableaux_all
(facade class)StandardTableaux_size
StandardTableaux_shape
IncreasingTableaux_all
(facade class)IncreasingTableaux_size
IncreasingTableaux_size_inf
IncreasingTableaux_size_weight
IncreasingTableaux_shape
IncreasingTableaux_shape_inf
IncreasingTableaux_shape_weight
RowStandardTableaux_all
(facade class)RowStandardTableaux_size
RowStandardTableaux_shape
For display options, see Tableaux.options()
.
Todo
- Move methods that only apply to semistandard tableaux from tableau to semistandard tableau
- Copy/move functionality to skew tableaux
- Add a class for tableaux of a given shape (eg Tableaux_shape)
-
sage.combinat.tableau.
IncreasingTableau
¶ A class to model an increasing tableau.
INPUT:
t
– a tableau, a list of iterables, or an empty list
An increasing tableau is a tableau whose entries are positive integers that are strictly increasing across rows and strictly increasing down columns.
EXAMPLES:
sage: t = IncreasingTableau([[1,2,3],[2,3]]); t [[1, 2, 3], [2, 3]] sage: t.shape() [3, 2] sage: t.pp() # pretty printing 1 2 3 2 3 sage: t = Tableau([[1,2],[2]]) sage: s = IncreasingTableau(t); s [[1, 2], [2]] sage: IncreasingTableau([]) # The empty tableau []
You can also construct an
IncreasingTableau
from the appropriateParent
object:sage: IT = IncreasingTableaux() sage: IT([[1, 2, 3], [4, 5]]) [[1, 2, 3], [4, 5]]
-
sage.combinat.tableau.
IncreasingTableaux
¶ A factory class for the various classes of increasing tableaux.
An increasing tableau is a tableau whose entries are positive integers that are strictly increasing across rows and strictly increasing down columns. Note that Sage uses the English convention for partitions and tableaux; the longer rows are displayed on top.
INPUT:
Keyword arguments:
size
– the size of the tableauxshape
– the shape of the tableauxeval
– the weight (also called binary content) of the tableaux, where values can be either \(0\) or \(1\) with position \(i\) being \(1\) if and only if \(i\) can appear in the tableauxmax_entry
– positive integer or infinity (oo
); the maximum entry for the tableaux; ifsize
orshape
are specified,max_entry
defaults to besize
or the size ofshape
Positional arguments:
- the first argument is interpreted as either
size
orshape
according to whether it is an integer or a partition - the second keyword argument will always be interpreted as
eval
Warning
The
eval
is not the usual notion ofeval
orweight
, where the \(i\)-th entry counts how many \(i\)‘s appear in the tableau.EXAMPLES:
sage: IT = IncreasingTableaux([2,1]); IT Increasing tableaux of shape [2, 1] and maximum entry 3 sage: IT.list() [[[1, 3], [2]], [[1, 2], [3]], [[1, 2], [2]], [[1, 3], [3]], [[2, 3], [3]]] sage: IT = IncreasingTableaux(3); IT Increasing tableaux of size 3 and maximum entry 3 sage: IT.list() [[[1, 2, 3]], [[1, 3], [2]], [[1, 2], [3]], [[1, 2], [2]], [[1, 3], [3]], [[2, 3], [3]], [[1], [2], [3]]] sage: IT = IncreasingTableaux(3, max_entry=2); IT Increasing tableaux of size 3 and maximum entry 2 sage: IT.list() [[[1, 2], [2]]] sage: IT = IncreasingTableaux(3, max_entry=4); IT Increasing tableaux of size 3 and maximum entry 4 sage: IT.list() [[[1, 2, 3]], [[1, 2, 4]], [[1, 3, 4]], [[2, 3, 4]], [[1, 3], [2]], [[1, 2], [3]], [[1, 4], [2]], [[1, 2], [4]], [[1, 2], [2]], [[1, 4], [3]], [[1, 3], [4]], [[1, 3], [3]], [[1, 4], [4]], [[2, 4], [3]], [[2, 3], [4]], [[2, 3], [3]], [[2, 4], [4]], [[3, 4], [4]], [[1], [2], [3]], [[1], [2], [4]], [[1], [3], [4]], [[2], [3], [4]]] sage: IT = IncreasingTableaux(3, max_entry=oo); IT Increasing tableaux of size 3 sage: IT[123] [[5, 7], [6]] sage: IT = IncreasingTableaux(max_entry=2) sage: list(IT) [[], [[1]], [[2]], [[1, 2]], [[1], [2]]] sage: IT[4] [[1], [2]] sage: IncreasingTableaux()[0] []
-
sage.combinat.tableau.
IncreasingTableaux_all
¶ All increasing tableaux.
EXAMPLES:
sage: T = IncreasingTableaux() sage: T.cardinality() +Infinity sage: T = IncreasingTableaux(max_entry=3) sage: list(T) [[], [[1]], [[2]], [[3]], [[1, 2]], [[1, 3]], [[2, 3]], [[1], [2]], [[1], [3]], [[2], [3]], [[1, 2, 3]], [[1, 3], [2]], [[1, 2], [3]], [[1, 2], [2]], [[1, 3], [3]], [[2, 3], [3]], [[1], [2], [3]]]
-
sage.combinat.tableau.
IncreasingTableaux_shape
¶ Increasing tableaux of fixed shape \(p\) with a given max entry.
An increasing tableau with max entry \(i\) is required to have all its entries less or equal to \(i\). It is not required to actually contain an entry \(i\).
INPUT:
p
– a partitionmax_entry
– the max entry; defaults to the size ofp
-
sage.combinat.tableau.
IncreasingTableaux_shape_inf
¶ Increasing tableaux of fixed shape \(p\) and no maximum entry.
-
sage.combinat.tableau.
IncreasingTableaux_shape_weight
¶ Increasing tableaux of fixed shape \(p\) and binary weight \(wt\).
-
sage.combinat.tableau.
IncreasingTableaux_size
¶ Increasing tableaux of fixed size \(n\).
-
sage.combinat.tableau.
IncreasingTableaux_size_inf
¶ Increasing tableaux of fixed size \(n\) with no maximum entry.
-
sage.combinat.tableau.
IncreasingTableaux_size_weight
¶ Increasing tableaux of fixed size \(n\) and weight \(wt\).
-
sage.combinat.tableau.
RowStandardTableau
¶ A class to model a row standard tableau.
A row standard tableau is a tableau whose entries are positive integers from 1 to \(m\) that increase along rows.
INPUT:
t
– a Tableau, a list of iterables, or an empty list
EXAMPLES:
sage: t = RowStandardTableau([[3,4,5],[1,2]]); t [[3, 4, 5], [1, 2]] sage: t.shape() [3, 2] sage: t.pp() # pretty printing 3 4 5 1 2 sage: t.is_standard() False sage: RowStandardTableau([]) # The empty tableau [] sage: RowStandardTableau([[3,4,5],[1,2]]) in StandardTableaux() False sage: RowStandardTableau([[1,2,5],[3,4]]) in StandardTableaux() True
When using code that will generate a lot of tableaux, it is more efficient to construct a
RowStandardTableau
from the appropriateParent
object:sage: ST = RowStandardTableaux() sage: ST([[3, 4, 5], [1, 2]]) [[3, 4, 5], [1, 2]]
-
sage.combinat.tableau.
RowStandardTableaux
¶ A factory for the various classes of row standard tableaux.
INPUT:
- either a non-negative integer (possibly specified with the keyword
n
) or a partition
OUTPUT:
- with no argument, the class of all standard tableaux
- with a non-negative integer argument,
n
, the class of all standard tableaux of sizen
- with a partition argument, the class of all standard tableaux of that shape
A row standard tableau is a tableau that contains each of the entries from \(1\) to \(n\) exactly once and is increasing along rows.
All classes of row standard tableaux are iterable.
EXAMPLES:
sage: ST = RowStandardTableaux(3); ST Row standard tableaux of size 3 sage: ST.first() [[1, 2, 3]] sage: ST.last() [[3], [1], [2]] sage: ST.cardinality() 10 sage: ST.list() [[[1, 2, 3]], [[2, 3], [1]], [[1, 2], [3]], [[1, 3], [2]], [[3], [2], [1]], [[2], [3], [1]], [[1], [3], [2]], [[1], [2], [3]], [[2], [1], [3]], [[3], [1], [2]]]
- either a non-negative integer (possibly specified with the keyword
-
sage.combinat.tableau.
RowStandardTableaux_all
¶ All row standard tableaux.
-
sage.combinat.tableau.
RowStandardTableaux_shape
¶ Row Standard tableaux of a fixed shape \(p\).
-
sage.combinat.tableau.
RowStandardTableaux_size
¶ Row standard tableaux of fixed size \(n\).
EXAMPLES:
sage: [ t for t in RowStandardTableaux(1) ] [[[1]]] sage: [ t for t in RowStandardTableaux(2) ] [[[1, 2]], [[2], [1]], [[1], [2]]] sage: list(RowStandardTableaux(3)) [[[1, 2, 3]], [[2, 3], [1]], [[1, 2], [3]], [[1, 3], [2]], [[3], [2], [1]], [[2], [3], [1]], [[1], [3], [2]], [[1], [2], [3]], [[2], [1], [3]], [[3], [1], [2]]]
-
sage.combinat.tableau.
SemistandardTableau
¶ A class to model a semistandard tableau.
INPUT:
t
– a tableau, a list of iterables, or an empty list
OUTPUT:
- A SemistandardTableau object constructed from
t
.
A semistandard tableau is a tableau whose entries are positive integers, which are weakly increasing in rows and strictly increasing down columns.
EXAMPLES:
sage: t = SemistandardTableau([[1,2,3],[2,3]]); t [[1, 2, 3], [2, 3]] sage: t.shape() [3, 2] sage: t.pp() # pretty printing 1 2 3 2 3 sage: t = Tableau([[1,2],[2]]) sage: s = SemistandardTableau(t); s [[1, 2], [2]] sage: SemistandardTableau([]) # The empty tableau []
When using code that will generate a lot of tableaux, it is slightly more efficient to construct a SemistandardTableau from the appropriate
Parent
object:sage: SST = SemistandardTableaux() sage: SST([[1, 2, 3], [4, 5]]) [[1, 2, 3], [4, 5]]
-
sage.combinat.tableau.
SemistandardTableaux
¶ A factory class for the various classes of semistandard tableaux.
INPUT:
Keyword arguments:
size
– The size of the tableauxshape
– The shape of the tableauxeval
– The weight (also called content or evaluation) of the tableauxmax_entry
– A maximum entry for the tableaux. This can be a positive integer or infinity (oo
). Ifsize
orshape
are specified,max_entry
defaults to besize
or the size ofshape
.
Positional arguments:
- The first argument is interpreted as either
size
orshape
according to whether it is an integer or a partition - The second keyword argument will always be interpreted as
eval
OUTPUT:
- The appropriate class, after checking basic consistency tests. (For
example, specifying
eval
implies a value for \(max_entry\)).
A semistandard tableau is a tableau whose entries are positive integers, which are weakly increasing in rows and strictly increasing down columns. Note that Sage uses the English convention for partitions and tableaux; the longer rows are displayed on top.
Classes of semistandard tableaux can be iterated over if and only if there is some restriction.
EXAMPLES:
sage: SST = SemistandardTableaux([2,1]); SST Semistandard tableaux of shape [2, 1] and maximum entry 3 sage: SST.list() [[[1, 1], [2]], [[1, 1], [3]], [[1, 2], [2]], [[1, 2], [3]], [[1, 3], [2]], [[1, 3], [3]], [[2, 2], [3]], [[2, 3], [3]]] sage: SST = SemistandardTableaux(3); SST Semistandard tableaux of size 3 and maximum entry 3 sage: SST.list() [[[1, 1, 1]], [[1, 1, 2]], [[1, 1, 3]], [[1, 2, 2]], [[1, 2, 3]], [[1, 3, 3]], [[2, 2, 2]], [[2, 2, 3]], [[2, 3, 3]], [[3, 3, 3]], [[1, 1], [2]], [[1, 1], [3]], [[1, 2], [2]], [[1, 2], [3]], [[1, 3], [2]], [[1, 3], [3]], [[2, 2], [3]], [[2, 3], [3]], [[1], [2], [3]]] sage: SST = SemistandardTableaux(3, max_entry=2); SST Semistandard tableaux of size 3 and maximum entry 2 sage: SST.list() [[[1, 1, 1]], [[1, 1, 2]], [[1, 2, 2]], [[2, 2, 2]], [[1, 1], [2]], [[1, 2], [2]]] sage: SST = SemistandardTableaux(3, max_entry=oo); SST Semistandard tableaux of size 3 sage: SST[123] [[3, 4], [6]] sage: SemistandardTableaux(max_entry=2)[11] [[1, 1], [2]] sage: SemistandardTableaux()[0] []
-
sage.combinat.tableau.
SemistandardTableaux_all
¶ All semistandard tableaux.
-
sage.combinat.tableau.
SemistandardTableaux_shape
¶ Semistandard tableaux of fixed shape \(p\) with a given max entry.
A semistandard tableau with max entry \(i\) is required to have all its entries less or equal to \(i\). It is not required to actually contain an entry \(i\).
INPUT:
p
– a partitionmax_entry
– the max entry; defaults to the size ofp
-
sage.combinat.tableau.
SemistandardTableaux_shape_inf
¶ Semistandard tableaux of fixed shape \(p\) and no maximum entry.
-
sage.combinat.tableau.
SemistandardTableaux_shape_weight
¶ Semistandard tableaux of fixed shape \(p\) and weight \(\mu\).
-
sage.combinat.tableau.
SemistandardTableaux_size
¶ Semistandard tableaux of fixed size \(n\).
-
sage.combinat.tableau.
SemistandardTableaux_size_inf
¶ Semistandard tableaux of fixed size \(n\) with no maximum entry.
-
sage.combinat.tableau.
SemistandardTableaux_size_weight
¶ Semistandard tableaux of fixed size \(n\) and weight \(\mu\).
-
sage.combinat.tableau.
StandardTableau
¶ A class to model a standard tableau.
INPUT:
t
– a Tableau, a list of iterables, or an empty list
A standard tableau is a semistandard tableau whose entries are exactly the positive integers from 1 to \(n\), where \(n\) is the size of the tableau.
EXAMPLES:
sage: t = StandardTableau([[1,2,3],[4,5]]); t [[1, 2, 3], [4, 5]] sage: t.shape() [3, 2] sage: t.pp() # pretty printing 1 2 3 4 5 sage: t.is_standard() True sage: StandardTableau([]) # The empty tableau [] sage: StandardTableau([[1,2,3],[4,5]]) in RowStandardTableaux() True
When using code that will generate a lot of tableaux, it is more efficient to construct a StandardTableau from the appropriate
Parent
object:sage: ST = StandardTableaux() sage: ST([[1, 2, 3], [4, 5]]) [[1, 2, 3], [4, 5]]
-
sage.combinat.tableau.
StandardTableaux
¶ A factory for the various classes of standard tableaux.
INPUT:
- Either a non-negative integer (possibly specified with the keyword
n
) or a partition.
OUTPUT:
- With no argument, the class of all standard tableaux
- With a non-negative integer argument,
n
, the class of all standard tableaux of sizen
- With a partition argument, the class of all standard tableaux of that shape.
A standard tableau is a semistandard tableaux which contains each of the entries from 1 to
n
exactly once.All classes of standard tableaux are iterable.
EXAMPLES:
sage: ST = StandardTableaux(3); ST Standard tableaux of size 3 sage: ST.first() [[1, 2, 3]] sage: ST.last() [[1], [2], [3]] sage: ST.cardinality() 4 sage: ST.list() [[[1, 2, 3]], [[1, 3], [2]], [[1, 2], [3]], [[1], [2], [3]]]
- Either a non-negative integer (possibly specified with the keyword
-
sage.combinat.tableau.
StandardTableaux_all
¶ All standard tableaux.
-
sage.combinat.tableau.
StandardTableaux_shape
¶ Semistandard tableaux of a fixed shape \(p\).
-
sage.combinat.tableau.
StandardTableaux_size
¶ Standard tableaux of fixed size \(n\).
EXAMPLES:
sage: [ t for t in StandardTableaux(1) ] [[[1]]] sage: [ t for t in StandardTableaux(2) ] [[[1, 2]], [[1], [2]]] sage: [ t for t in StandardTableaux(3) ] [[[1, 2, 3]], [[1, 3], [2]], [[1, 2], [3]], [[1], [2], [3]]] sage: StandardTableaux(4)[:] [[[1, 2, 3, 4]], [[1, 3, 4], [2]], [[1, 2, 4], [3]], [[1, 2, 3], [4]], [[1, 3], [2, 4]], [[1, 2], [3, 4]], [[1, 4], [2], [3]], [[1, 3], [2], [4]], [[1, 2], [3], [4]], [[1], [2], [3], [4]]]
-
sage.combinat.tableau.
Tableau
¶ A class to model a tableau.
INPUT:
t
– a Tableau, a list of iterables, or an empty list
OUTPUT:
- A Tableau object constructed from
t
.
A tableau is abstractly a mapping from the cells in a partition to arbitrary objects (called entries). It is often represented as a finite list of nonempty lists (or, more generally an iterator of iterables) of weakly decreasing lengths. This list, in particular, can be empty, representing the empty tableau.
Note that Sage uses the English convention for partitions and tableaux; the longer rows are displayed on top.
EXAMPLES:
sage: t = Tableau([[1,2,3],[4,5]]); t [[1, 2, 3], [4, 5]] sage: t.shape() [3, 2] sage: t.pp() # pretty printing 1 2 3 4 5 sage: t.is_standard() True sage: Tableau([['a','c','b'],[[],(2,1)]]) [['a', 'c', 'b'], [[], (2, 1)]] sage: Tableau([]) # The empty tableau []
When using code that will generate a lot of tableaux, it is slightly more efficient to construct a Tableau from the appropriate Parent object:
sage: T = Tableaux() sage: T([[1, 2, 3], [4, 5]]) [[1, 2, 3], [4, 5]]
-
sage.combinat.tableau.
Tableau_class
¶ This exists solely for unpickling
Tableau_class
objects.
-
sage.combinat.tableau.
Tableaux
¶ A factory class for the various classes of tableaux.
INPUT:
n
(optional) – a non-negative integer
OUTPUT:
- If
n
is specified, the class of tableaux of sizen
. Otherwise, the class of all tableaux.
A tableau in Sage is a finite list of lists, whose lengths are weakly decreasing, or an empty list, representing the empty tableau. The entries of a tableau can be any Sage objects. Because of this, no enumeration through the set of Tableaux is possible.
EXAMPLES:
sage: T = Tableaux(); T Tableaux sage: T3 = Tableaux(3); T3 Tableaux of size 3 sage: [['a','b']] in T True sage: [['a','b']] in T3 False sage: t = T3([[1,1,1]]); t [[1, 1, 1]] sage: t in T True sage: t.parent() Tableaux of size 3 sage: T([]) # the empty tableau [] sage: T.category() Category of sets
-
class
sage.combinat.tableau.
Tableaux_all
¶ Bases:
sage.combinat.tableau.Tableaux
Initializes the class of all tableaux
-
an_element
()¶ Returns a particular element of the class.
-
-
sage.combinat.tableau.
Tableaux_size
¶ Tableaux of a fixed size \(n\).
-
sage.combinat.tableau.
from_chain
(chain)¶ Returns a semistandard tableau from a chain of partitions.
EXAMPLES:
sage: from sage.combinat.tableau import from_chain sage: from_chain([[], [2], [2, 1], [3, 2, 1]]) [[1, 1, 3], [2, 3], [3]]
-
sage.combinat.tableau.
from_shape_and_word
(shape, w, convention='French')¶ Returns a tableau from a shape and word.
INPUT:
shape
– a partitionw
– a word whose length equals that of the partitionconvention
– a string which can take values"French"
or"English"
; the default is"French"
OUTPUT:
A tableau, whose shape is
shape
and whose reading word isw
. If theconvention
is specified as"French"
, the reading word is to be read starting from the top row in French convention (= the bottom row in English convention). If theconvention
is specified as"English"
, the reading word is to be read starting with the top row in English convention.EXAMPLES:
sage: from sage.combinat.tableau import from_shape_and_word sage: t = Tableau([[1, 3], [2], [4]]) sage: shape = t.shape(); shape [2, 1, 1] sage: word = t.to_word(); word word: 4213 sage: from_shape_and_word(shape, word) [[1, 3], [2], [4]] sage: word = Word(flatten(t)) sage: from_shape_and_word(shape, word, convention = "English") [[1, 3], [2], [4]]
-
sage.combinat.tableau.
symmetric_group_action_on_values
(word, perm)¶ EXAMPLES:
sage: from sage.combinat.tableau import symmetric_group_action_on_values sage: symmetric_group_action_on_values([1,1,1],[1,3,2]) [1, 1, 1] sage: symmetric_group_action_on_values([1,1,1],[2,1,3]) [2, 2, 2] sage: symmetric_group_action_on_values([1,2,1],[2,1,3]) [2, 2, 1] sage: symmetric_group_action_on_values([2,2,2],[2,1,3]) [1, 1, 1] sage: symmetric_group_action_on_values([2,1,2],[2,1,3]) [2, 1, 1] sage: symmetric_group_action_on_values([2,2,3,1,1,2,2,3],[1,3,2]) [2, 3, 3, 1, 1, 2, 3, 3] sage: symmetric_group_action_on_values([2,1,1],[2,1]) [2, 1, 2] sage: symmetric_group_action_on_values([2,2,1],[2,1]) [1, 2, 1] sage: symmetric_group_action_on_values([1,2,1],[2,1]) [2, 2, 1]
-
sage.combinat.tableau.
unmatched_places
(w, open, close)¶ EXAMPLES:
sage: from sage.combinat.tableau import unmatched_places sage: unmatched_places([2,2,2,1,1,1],2,1) ([], []) sage: unmatched_places([1,1,1,2,2,2],2,1) ([0, 1, 2], [3, 4, 5]) sage: unmatched_places([], 2, 1) ([], []) sage: unmatched_places([1,2,4,6,2,1,5,3],2,1) ([0], [1]) sage: unmatched_places([2,2,1,2,4,6,2,1,5,3], 2, 1) ([], [0, 3]) sage: unmatched_places([3,1,1,1,2,1,2], 2, 1) ([1, 2, 3], [6])