Semistandard Tableaux#

This is an implementation of the abstract base class sage.combinat.path_tableaux.path_tableau.PathTableau.

This implementation is for semistandard tableaux, represented as a chain of partitions (essentially, the Gelfand-Tsetlin pattern). This generalises the jeu de taquin operations of rectification, promotion, evacuation from standard tableaux to semistandard tableaux. The local rule is the Bender-Knuth involution.

EXAMPLES:

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [3,2], [3,3,1],
....:                                             [3,3,2,1], [4,3,3,1,0]])
sage: pt.promotion()
[(), (2,), (3, 1), (3, 2, 1), (4, 3, 1, 0), (4, 3, 3, 1, 0)]
sage: pt.evacuation()
[(), (2,), (4, 0), (4, 2, 0), (4, 3, 1, 0), (4, 3, 3, 1, 0)]

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [3,2], [3,3,1],
....:                                             [3,3,2,1], [9/2,3,3,1,0]])
sage: pt.promotion()
[(), (2,), (3, 1), (3, 2, 1), (9/2, 3, 1, 0), (9/2, 3, 3, 1, 0)]
sage: pt.evacuation()
[(), (5/2,), (9/2, 0), (9/2, 2, 0), (9/2, 3, 1, 0), (9/2, 3, 3, 1, 0)]

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [4,2], [5,4,1]])
sage: path_tableaux.CylindricalDiagram(pt)
[       (),      (3,),    (4, 2), (5, 4, 1)]
[         ,        (),      (3,),    (5, 2), (5, 4, 1)]
[         ,          ,        (),      (4,),    (4, 3), (5, 4, 1)]
[         ,          ,          ,        (),      (3,),    (5, 1), (5, 4, 1)]

sage: pt2 = path_tableaux.SemistandardPathTableau([[3,2], [3,3,1],
....:                                              [3,3,2,1], [4,3,3,1,0]])
sage: pt1 = path_tableaux.SemistandardPathTableau([[], [3], [3,2]])
sage: pt1.commutor(pt2)
([(), (2,), (2, 2), (4, 2, 0)], [(4, 2, 0), (4, 3, 2, 0), (4, 3, 3, 1, 0)])
sage: pt1.commutor(pt2,verbose=True)
[(3, 2), (3, 3, 1), (3, 3, 2, 1), (4, 3, 3, 1, 0)]
[(3,), (3, 2), (3, 2, 2), (4, 3, 2, 0)]
[(), (2,), (2, 2), (4, 2, 0)]
([(), (2,), (2, 2), (4, 2, 0)], [(4, 2, 0), (4, 3, 2, 0), (4, 3, 3, 1, 0)])

sage: st = SkewTableau([[None, None, None, 4, 4, 5, 6, 7], [None, 2, 4, 6, 7, 7, 7],
....:                   [None, 4, 5, 8, 8, 9], [None, 6, 7, 10], [None, 8, 8, 11],
....:                   [None], [4]])
sage: pt = path_tableaux.SemistandardPathTableau(st)
sage: bk = [SkewTableau(st.bender_knuth_involution(i+1)) for i in range(10)]
sage: lr = [pt.local_rule(i+1) for i in range(10)]
sage: [r.to_tableau() for r in lr] == bk
True

>>> from sage.all import *
>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)],
...                                             [Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(4),Integer(3),Integer(3),Integer(1),Integer(0)]])
>>> pt.promotion()
[(), (2,), (3, 1), (3, 2, 1), (4, 3, 1, 0), (4, 3, 3, 1, 0)]
>>> pt.evacuation()
[(), (2,), (4, 0), (4, 2, 0), (4, 3, 1, 0), (4, 3, 3, 1, 0)]

>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)],
...                                             [Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(9)/Integer(2),Integer(3),Integer(3),Integer(1),Integer(0)]])
>>> pt.promotion()
[(), (2,), (3, 1), (3, 2, 1), (9/2, 3, 1, 0), (9/2, 3, 3, 1, 0)]
>>> pt.evacuation()
[(), (5/2,), (9/2, 0), (9/2, 2, 0), (9/2, 3, 1, 0), (9/2, 3, 3, 1, 0)]

>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(4),Integer(2)], [Integer(5),Integer(4),Integer(1)]])
>>> path_tableaux.CylindricalDiagram(pt)
[       (),      (3,),    (4, 2), (5, 4, 1)]
[         ,        (),      (3,),    (5, 2), (5, 4, 1)]
[         ,          ,        (),      (4,),    (4, 3), (5, 4, 1)]
[         ,          ,          ,        (),      (3,),    (5, 1), (5, 4, 1)]

>>> pt2 = path_tableaux.SemistandardPathTableau([[Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)],
...                                              [Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(4),Integer(3),Integer(3),Integer(1),Integer(0)]])
>>> pt1 = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)]])
>>> pt1.commutor(pt2)
([(), (2,), (2, 2), (4, 2, 0)], [(4, 2, 0), (4, 3, 2, 0), (4, 3, 3, 1, 0)])
>>> pt1.commutor(pt2,verbose=True)
[(3, 2), (3, 3, 1), (3, 3, 2, 1), (4, 3, 3, 1, 0)]
[(3,), (3, 2), (3, 2, 2), (4, 3, 2, 0)]
[(), (2,), (2, 2), (4, 2, 0)]
([(), (2,), (2, 2), (4, 2, 0)], [(4, 2, 0), (4, 3, 2, 0), (4, 3, 3, 1, 0)])

>>> st = SkewTableau([[None, None, None, Integer(4), Integer(4), Integer(5), Integer(6), Integer(7)], [None, Integer(2), Integer(4), Integer(6), Integer(7), Integer(7), Integer(7)],
...                   [None, Integer(4), Integer(5), Integer(8), Integer(8), Integer(9)], [None, Integer(6), Integer(7), Integer(10)], [None, Integer(8), Integer(8), Integer(11)],
...                   [None], [Integer(4)]])
>>> pt = path_tableaux.SemistandardPathTableau(st)
>>> bk = [SkewTableau(st.bender_knuth_involution(i+Integer(1))) for i in range(Integer(10))]
>>> lr = [pt.local_rule(i+Integer(1)) for i in range(Integer(10))]
>>> [r.to_tableau() for r in lr] == bk
True

AUTHORS:

  • Bruce Westbury (2020): initial version

class sage.combinat.path_tableaux.semistandard.SemistandardPathTableau(parent, st, check=True)[source]#

Bases: PathTableau

An instance is a sequence of lists. Usually the entries will be non-negative integers in which case this is the chain of partitions of a (skew) semistandard tableau. In general the entries are elements of an ordered abelian group; each list is weakly decreasing and successive lists are interleaved.

INPUT:

Can be any of the following

  • a sequence of partitions

  • a sequence of lists/tuples

  • a semistandard tableau

  • a semistandard skew tableau

  • a Gelfand-Tsetlin pattern

EXAMPLES:

sage: path_tableaux.SemistandardPathTableau([[], [2], [2,1]])
[(), (2,), (2, 1)]

sage: gt = GelfandTsetlinPattern([[2,1], [2]])
sage: path_tableaux.SemistandardPathTableau(gt)
[(), (2,), (2, 1)]

sage: st = SemistandardTableau([[1,1], [2]])
sage: path_tableaux.SemistandardPathTableau(st)
[(), (2,), (2, 1)]

sage: st = SkewTableau([[1,1], [2]])
sage: path_tableaux.SemistandardPathTableau(st)
[(), (2,), (2, 1)]

sage: st = SkewTableau([[None,1,1], [2]])
sage: path_tableaux.SemistandardPathTableau(st)
[(1,), (3, 0), (3, 1, 0)]

sage: path_tableaux.SemistandardPathTableau([[], [5/2], [7/2,2]])
[(), (5/2,), (7/2, 2)]

sage: path_tableaux.SemistandardPathTableau([[], [2.5], [3.5,2]])
[(), (2.50000000000000,), (3.50000000000000, 2)]

>>> from sage.all import *
>>> path_tableaux.SemistandardPathTableau([[], [Integer(2)], [Integer(2),Integer(1)]])
[(), (2,), (2, 1)]

>>> gt = GelfandTsetlinPattern([[Integer(2),Integer(1)], [Integer(2)]])
>>> path_tableaux.SemistandardPathTableau(gt)
[(), (2,), (2, 1)]

>>> st = SemistandardTableau([[Integer(1),Integer(1)], [Integer(2)]])
>>> path_tableaux.SemistandardPathTableau(st)
[(), (2,), (2, 1)]

>>> st = SkewTableau([[Integer(1),Integer(1)], [Integer(2)]])
>>> path_tableaux.SemistandardPathTableau(st)
[(), (2,), (2, 1)]

>>> st = SkewTableau([[None,Integer(1),Integer(1)], [Integer(2)]])
>>> path_tableaux.SemistandardPathTableau(st)
[(1,), (3, 0), (3, 1, 0)]

>>> path_tableaux.SemistandardPathTableau([[], [Integer(5)/Integer(2)], [Integer(7)/Integer(2),Integer(2)]])
[(), (5/2,), (7/2, 2)]

>>> path_tableaux.SemistandardPathTableau([[], [RealNumber('2.5')], [RealNumber('3.5'),Integer(2)]])
[(), (2.50000000000000,), (3.50000000000000, 2)]
check()[source]#

Check that self is a valid path.

EXAMPLES:

sage: path_tableaux.SemistandardPathTableau([[], [3], [2,2]])       # indirect doctest
Traceback (most recent call last):
...
ValueError: [(), (3,), (2, 2)] does not satisfy
the required inequalities in row 1

sage: path_tableaux.SemistandardPathTableau([[], [3/2], [2,5/2]])   # indirect doctest
Traceback (most recent call last):
...
ValueError: [(), (3/2,), (2, 5/2)] does not satisfy
the required inequalities in row 1

>>> from sage.all import *
>>> path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(2),Integer(2)]])       # indirect doctest
Traceback (most recent call last):
...
ValueError: [(), (3,), (2, 2)] does not satisfy
the required inequalities in row 1

>>> path_tableaux.SemistandardPathTableau([[], [Integer(3)/Integer(2)], [Integer(2),Integer(5)/Integer(2)]])   # indirect doctest
Traceback (most recent call last):
...
ValueError: [(), (3/2,), (2, 5/2)] does not satisfy
the required inequalities in row 1
is_integral()[source]#

Return True if all entries are non-negative integers.

EXAMPLES:

sage: path_tableaux.SemistandardPathTableau([[], [3], [3,2]]).is_integral()
True
sage: path_tableaux.SemistandardPathTableau([[], [5/2], [7/2,2]]).is_integral()
False
sage: path_tableaux.SemistandardPathTableau([[], [3], [3,-2]]).is_integral()
False

>>> from sage.all import *
>>> path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)]]).is_integral()
True
>>> path_tableaux.SemistandardPathTableau([[], [Integer(5)/Integer(2)], [Integer(7)/Integer(2),Integer(2)]]).is_integral()
False
>>> path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),-Integer(2)]]).is_integral()
False
is_skew()[source]#

Return True if self is skew.

EXAMPLES:

sage: path_tableaux.SemistandardPathTableau([[], [2]]).is_skew()
False
sage: path_tableaux.SemistandardPathTableau([[2,1]]).is_skew()
True

>>> from sage.all import *
>>> path_tableaux.SemistandardPathTableau([[], [Integer(2)]]).is_skew()
False
>>> path_tableaux.SemistandardPathTableau([[Integer(2),Integer(1)]]).is_skew()
True
local_rule(i)[source]#

This is the Bender-Knuth involution.

This is implemented by toggling the entries of the \(i\)-th list. The allowed range for i is 0 < i < len(self)-1 so any row except the first and last can be changed.

EXAMPLES:

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [3,2],
....:                                             [3,3,1], [3,3,2,1]])
sage: pt.local_rule(1)
[(), (2,), (3, 2), (3, 3, 1), (3, 3, 2, 1)]
sage: pt.local_rule(2)
[(), (3,), (3, 2), (3, 3, 1), (3, 3, 2, 1)]
sage: pt.local_rule(3)
[(), (3,), (3, 2), (3, 2, 2), (3, 3, 2, 1)]

>>> from sage.all import *
>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)],
...                                             [Integer(3),Integer(3),Integer(1)], [Integer(3),Integer(3),Integer(2),Integer(1)]])
>>> pt.local_rule(Integer(1))
[(), (2,), (3, 2), (3, 3, 1), (3, 3, 2, 1)]
>>> pt.local_rule(Integer(2))
[(), (3,), (3, 2), (3, 3, 1), (3, 3, 2, 1)]
>>> pt.local_rule(Integer(3))
[(), (3,), (3, 2), (3, 2, 2), (3, 3, 2, 1)]
rectify(inner=None, verbose=False)[source]#

Rectify self.

This gives the usual rectification of a skew standard tableau and gives a generalisation to skew semistandard tableaux. The usual construction uses jeu de taquin but here we use the Bender-Knuth involutions.

EXAMPLES:

sage: st = SkewTableau([[None, None, None, 4], [None, None, 1, 6],
....:                   [None, None, 5], [2, 3]])
sage: path_tableaux.SemistandardPathTableau(st).rectify()
[(), (1,), (1, 1), (2, 1, 0), (3, 1, 0, 0), (3, 2, 0, 0, 0), (4, 2, 0, 0, 0, 0)]
sage: path_tableaux.SemistandardPathTableau(st).rectify(verbose=True)
[[(3, 2, 2), (3, 3, 2, 0), (3, 3, 2, 1, 0), (3, 3, 2, 2, 0, 0),
  (4, 3, 2, 2, 0, 0, 0), (4, 3, 3, 2, 0, 0, 0, 0), (4, 4, 3, 2, 0, 0, 0, 0, 0)],
 [(3, 2), (3, 3, 0), (3, 3, 1, 0), (3, 3, 2, 0, 0), (4, 3, 2, 0, 0, 0),
  (4, 3, 3, 0, 0, 0, 0), (4, 4, 3, 0, 0, 0, 0, 0)],
 [(3,), (3, 1), (3, 1, 1), (3, 2, 1, 0), (4, 2, 1, 0, 0), (4, 3, 1, 0, 0, 0),
  (4, 4, 1, 0, 0, 0, 0)],
 [(), (1,), (1, 1), (2, 1, 0), (3, 1, 0, 0), (3, 2, 0, 0, 0), (4, 2, 0, 0, 0, 0)]]

>>> from sage.all import *
>>> st = SkewTableau([[None, None, None, Integer(4)], [None, None, Integer(1), Integer(6)],
...                   [None, None, Integer(5)], [Integer(2), Integer(3)]])
>>> path_tableaux.SemistandardPathTableau(st).rectify()
[(), (1,), (1, 1), (2, 1, 0), (3, 1, 0, 0), (3, 2, 0, 0, 0), (4, 2, 0, 0, 0, 0)]
>>> path_tableaux.SemistandardPathTableau(st).rectify(verbose=True)
[[(3, 2, 2), (3, 3, 2, 0), (3, 3, 2, 1, 0), (3, 3, 2, 2, 0, 0),
  (4, 3, 2, 2, 0, 0, 0), (4, 3, 3, 2, 0, 0, 0, 0), (4, 4, 3, 2, 0, 0, 0, 0, 0)],
 [(3, 2), (3, 3, 0), (3, 3, 1, 0), (3, 3, 2, 0, 0), (4, 3, 2, 0, 0, 0),
  (4, 3, 3, 0, 0, 0, 0), (4, 4, 3, 0, 0, 0, 0, 0)],
 [(3,), (3, 1), (3, 1, 1), (3, 2, 1, 0), (4, 2, 1, 0, 0), (4, 3, 1, 0, 0, 0),
  (4, 4, 1, 0, 0, 0, 0)],
 [(), (1,), (1, 1), (2, 1, 0), (3, 1, 0, 0), (3, 2, 0, 0, 0), (4, 2, 0, 0, 0, 0)]]
size()[source]#

Return the size or length of self.

EXAMPLES:

sage: path_tableaux.SemistandardPathTableau([[], [3], [3,2], [3,3,1], [3,3,2,1]]).size()
5

>>> from sage.all import *
>>> path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)], [Integer(3),Integer(3),Integer(2),Integer(1)]]).size()
5
to_pattern()[source]#

Convert self to a Gelfand-Tsetlin pattern.

EXAMPLES:

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [3,2], [3,3,1],
....:                                             [3,3,2,1], [4,3,3,1]])
sage: pt.to_pattern()
[[4, 3, 3, 1, 0], [3, 3, 2, 1], [3, 3, 1], [3, 2], [3]]

>>> from sage.all import *
>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)],
...                                             [Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(4),Integer(3),Integer(3),Integer(1)]])
>>> pt.to_pattern()
[[4, 3, 3, 1, 0], [3, 3, 2, 1], [3, 3, 1], [3, 2], [3]]
to_tableau()[source]#

Convert self to a SemistandardTableau.

The SemistandardSkewTableau is not implemented so this returns a SkewTableau

EXAMPLES:

sage: pt = path_tableaux.SemistandardPathTableau([[], [3], [3,2], [3,3,1],
....:                                             [3,3,2,1], [4,3,3,1,0]])
sage: pt.to_tableau()
[[1, 1, 1, 5], [2, 2, 3], [3, 4, 5], [4]]

>>> from sage.all import *
>>> pt = path_tableaux.SemistandardPathTableau([[], [Integer(3)], [Integer(3),Integer(2)], [Integer(3),Integer(3),Integer(1)],
...                                             [Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(4),Integer(3),Integer(3),Integer(1),Integer(0)]])
>>> pt.to_tableau()
[[1, 1, 1, 5], [2, 2, 3], [3, 4, 5], [4]]
class sage.combinat.path_tableaux.semistandard.SemistandardPathTableaux[source]#

Bases: PathTableaux

The parent class for SemistandardPathTableau.

Element[source]#

alias of SemistandardPathTableau