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:

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 appropriate Parent 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 tableaux
  • shape – the shape of the tableaux
  • eval – 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 tableaux
  • max_entry – positive integer or infinity (oo); the maximum entry for the tableaux; if size or shape are specified, max_entry defaults to be size or the size of shape

Positional arguments:

  • the first argument is interpreted as either size or shape 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 of eval or weight, 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 partition
  • max_entry – the max entry; defaults to the size of p
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 appropriate Parent 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 size n
  • 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]]]
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 tableaux
  • shape – The shape of the tableaux
  • eval – The weight (also called content or evaluation) of the tableaux
  • max_entry – A maximum entry for the tableaux. This can be a positive integer or infinity (oo). If size or shape are specified, max_entry defaults to be size or the size of shape.

Positional arguments:

  • The first argument is interpreted as either size or shape 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 partition
  • max_entry – the max entry; defaults to the size of p
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 size n
  • 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]]]
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 size n. 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 partition
  • w – a word whose length equals that of the partition
  • convention – a string which can take values "French" or "English"; the default is "French"

OUTPUT:

A tableau, whose shape is shape and whose reading word is w. If the convention 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 the convention 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])