Quasi-ribbon tableaux

AUTHORS:

  • Daniel Chen, Lisa Johnston, Junbok Lee, Evuilynn Nguyen, Heather Ross, Anne Schilling, Chenchen Zhao (2026): initial version

This file implements quasi-ribbon tableaux and finite families of quasi-ribbon tableaux. A quasi-ribbon tableau is entered as a list of rows from top to bottom. The entries in each row are weakly increasing left to right, the entries in each column are strictly increasing top to bottom, and None entries are used to record the shifted positions in the ribbon shape.

The main functionality includes constructing quasi-ribbon tableaux, computing their associated compositions, computing column-reading words, generating finite families of fixed composition shape, and performing Krob–Thibon insertion of letters and words. For references, see [KT1997] and [Nov2000].

class sage.combinat.quasi_ribbon_tableau.QuasiRibbonTableau(parent, rows)[source]

Bases: SkewTableau

A quasi-ribbon tableau.

A quasi-ribbon shape is obtained from a composition by drawing rows of cells whose lengths are the parts of the composition, and then shifting the rows so that each lower row starts under the last cell of the row above. For the purposes of this class, a quasi-ribbon tableau is a filling of a quasi-ribbon shape with positive integers which:

  1. has at least one entry in row \(1\);

  2. weakly increases from left to right in each row; and

  3. strictly increases from top to bottom in each column.

A quasi-ribbon tableau is given by a list of the rows from top to bottom.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q
[[1, 2, 3], [None, None, 4, 5]]
sage: Q.pp()
1  2  3
      4  5
sage: Q.to_composition()
[3, 2]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q
[[1, 2, 3], [None, None, 4, 5]]
>>> Q.pp()
1  2  3
      4  5
>>> Q.to_composition()
[3, 2]

The entries labeled by None correspond to shifted positions before the first actual entry in a row. Using None is optional; the entries will be shifted accordingly:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3], [4, 5]])
sage: Q.pp()
1  2  3
      4  5
[Python] 
>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5)]])
>>> Q.pp()
1  2  3
      4  5
insert_letter(a)[source]

Insert one letter a into a quasi-ribbon tableau self.

Case 1: If no entry of self is less or equal to a, add a as a new top row.

Case 2: Otherwise, find \(x\), the rightmost and bottommost entry of self that is less or equal to \(a\). Put a immediately to the right of \(x\). Then split off the entries that were originally to the right of \(x\) and move them below.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([])
sage: Q.insert_letter(3)
[[3]]

sage: Q = QuasiRibbonTableau([[4, 5]])
sage: Q.insert_letter(3)
[[3], [4, 5]]

sage: Q = QuasiRibbonTableau([[1, 2, 3], [4, 5]])
sage: Q.insert_letter(4)
[[1, 2, 3], [None, None, 4, 4], [None, None, None, 5]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([])
>>> Q.insert_letter(Integer(3))
[[3]]

>>> Q = QuasiRibbonTableau([[Integer(4), Integer(5)]])
>>> Q.insert_letter(Integer(3))
[[3], [4, 5]]

>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5)]])
>>> Q.insert_letter(Integer(4))
[[1, 2, 3], [None, None, 4, 4], [None, None, None, 5]]
insert_word(word)[source]

Insert the letters of a word one at a time from left to right into self.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([])
sage: Q.insert_word([3])
[[3]]

sage: Q = QuasiRibbonTableau([[4, 5]])
sage: Q.insert_word([3,3,1,2])
[[1, 2], [None, 3, 3], [None, None, 4, 5]]

sage: Q = QuasiRibbonTableau([[1], [2,3]])
sage: Q.insert_word([])
[[1], [2, 3]]
sage: Q.insert_word([4,1,2])
[[1, 1], [None, 2, 2], [None, None, 3, 4]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([])
>>> Q.insert_word([Integer(3)])
[[3]]

>>> Q = QuasiRibbonTableau([[Integer(4), Integer(5)]])
>>> Q.insert_word([Integer(3),Integer(3),Integer(1),Integer(2)])
[[1, 2], [None, 3, 3], [None, None, 4, 5]]

>>> Q = QuasiRibbonTableau([[Integer(1)], [Integer(2),Integer(3)]])
>>> Q.insert_word([])
[[1], [2, 3]]
>>> Q.insert_word([Integer(4),Integer(1),Integer(2)])
[[1, 1], [None, 2, 2], [None, None, 3, 4]]
pp()[source]

Return a pretty print of self.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q.pp()
1  2  3
      4  5

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q.pp()
1  2  3
      4  5
rows()[source]

Return the quasi-ribbon rows of self.

This returns the user-facing row-list representation, including None entries.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q.rows()
[[1, 2, 3], [None, None, 4, 5]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q.rows()
[[1, 2, 3], [None, None, 4, 5]]
split(row_index, col_index)[source]

Return two quasi-ribbon tableaux split from self.

The first quasi-ribbon tableau includes all entries above or weakly left of the (row_index, col_index)-position and the second includes all entries below or strictly right of that position. col_index indicates the position among integers in a row, ignoring the None entries; both it and row_index count starting from 0.

When row_index exceeds the number of rows, the first quasi-ribbon tableau is self and the second is empty. When column_index exceeds the number of integers in self.rows()[row_index], the first quasi-ribbon contains the entirety of self.rows()[row_index] and the second starts at the row below.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3], [4, 5]])
sage: Q1, Q2 = Q.split(0, 0)
sage: Q1.rows()
[[1]]
sage: Q2.rows()
[[2, 3], [None, 4, 5]]
sage: Q3, Q4 = Q.split(1, 0)
sage: Q3.rows()
[[1, 2, 3], [None, None, 4]]
sage: Q4.rows()
[[5]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5)]])
>>> Q1, Q2 = Q.split(Integer(0), Integer(0))
>>> Q1.rows()
[[1]]
>>> Q2.rows()
[[2, 3], [None, 4, 5]]
>>> Q3, Q4 = Q.split(Integer(1), Integer(0))
>>> Q3.rows()
[[1, 2, 3], [None, None, 4]]
>>> Q4.rows()
[[5]]
to_composition()[source]

Return the composition shape of self.

The shape counts the actual entries in each row, ignoring None.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q.to_composition()
[3, 2]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q.to_composition()
[3, 2]
to_word_by_column()[source]

Return the reading word of self.

The reading convention is column by column from left to right. Within each column, read from bottom to top.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q.to_word_by_column()
word: 12435

sage: T = QuasiRibbonTableau([[1], [2, 2], [None, 3, 3], [None, None, 4]])
sage: T.to_word_by_column()
word: 213243

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q.to_word_by_column()
word: 12435

>>> T = QuasiRibbonTableau([[Integer(1)], [Integer(2), Integer(2)], [None, Integer(3), Integer(3)], [None, None, Integer(4)]])
>>> T.to_word_by_column()
word: 213243
width()[source]

Return the maximum row length of self, including None entries.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
sage: Q = QuasiRibbonTableau([[1, 2, 3],
....:                         [None, None, 4, 5]])
sage: Q.width()
4

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableau
>>> Q = QuasiRibbonTableau([[Integer(1), Integer(2), Integer(3)],
...                         [None, None, Integer(4), Integer(5)]])
>>> Q.width()
4
class sage.combinat.quasi_ribbon_tableau.QuasiRibbonTableaux(shape=None, max_entry=None, size=None, category=None)[source]

Bases: SkewTableaux

The set of quasi-ribbon tableaux.

INPUT:

  • shape – (optional) the composition shape of the rows

  • max_entry – (optional) the largest allowed entry for finite generation

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
sage: QRT = QuasiRibbonTableaux()
sage: QRT
Quasi-ribbon tableaux
sage: QRT = QuasiRibbonTableaux(shape=[2, 1])
sage: QRT
Quasi-ribbon tableaux of shape [2, 1]
sage: QRT = QuasiRibbonTableaux(shape=[2, 1], max_entry=3)
sage: list(QRT)
[[[1, 1], [None, 2]],
[[1, 1], [None, 3]],
[[1, 2], [None, 3]],
[[2, 2], [None, 3]]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
>>> QRT = QuasiRibbonTableaux()
>>> QRT
Quasi-ribbon tableaux
>>> QRT = QuasiRibbonTableaux(shape=[Integer(2), Integer(1)])
>>> QRT
Quasi-ribbon tableaux of shape [2, 1]
>>> QRT = QuasiRibbonTableaux(shape=[Integer(2), Integer(1)], max_entry=Integer(3))
>>> list(QRT)
[[[1, 1], [None, 2]],
[[1, 1], [None, 3]],
[[1, 2], [None, 3]],
[[2, 2], [None, 3]]]
Element[source]

alias of QuasiRibbonTableau

cardinality()[source]

Return the cardinality of self.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
sage: QuasiRibbonTableaux().cardinality()
+Infinity
sage: QuasiRibbonTableaux(shape=[2, 1]).cardinality()
+Infinity
sage: QuasiRibbonTableaux(shape=[2, 1], max_entry=2).cardinality()
1
sage: QuasiRibbonTableaux(1, max_entry=2).cardinality()
2

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
>>> QuasiRibbonTableaux().cardinality()
+Infinity
>>> QuasiRibbonTableaux(shape=[Integer(2), Integer(1)]).cardinality()
+Infinity
>>> QuasiRibbonTableaux(shape=[Integer(2), Integer(1)], max_entry=Integer(2)).cardinality()
1
>>> QuasiRibbonTableaux(Integer(1), max_entry=Integer(2)).cardinality()
2
insert_word(word)[source]

Insert the letters of word one at a time into self.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
sage: H = QuasiRibbonTableaux()
sage: H.insert_word([])
[]
sage: H.insert_word([3, 4])
[[3, 4]]
sage: H.insert_word([4, 3])
[[3], [4]]
sage: H.insert_word([1, 3, 2, 4, 4])
[[1, 2], [None, 3, 4, 4]]

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
>>> H = QuasiRibbonTableaux()
>>> H.insert_word([])
[]
>>> H.insert_word([Integer(3), Integer(4)])
[[3, 4]]
>>> H.insert_word([Integer(4), Integer(3)])
[[3], [4]]
>>> H.insert_word([Integer(1), Integer(3), Integer(2), Integer(4), Integer(4)])
[[1, 2], [None, 3, 4, 4]]
shape()[source]

Return the fixed composition shape of self.

Raise an error if this family does not have a fixed shape.

EXAMPLES:

sage: from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
sage: QRT = QuasiRibbonTableaux(shape=[3, 2])
sage: QRT.shape()
[3, 2]
sage: QRT = QuasiRibbonTableaux(3)
sage: QRT.shape()
Traceback (most recent call last):
...
ValueError: this family does not have a fixed shape

>>> from sage.all import *
>>> from sage.combinat.quasi_ribbon_tableau import QuasiRibbonTableaux
>>> QRT = QuasiRibbonTableaux(shape=[Integer(3), Integer(2)])
>>> QRT.shape()
[3, 2]
>>> QRT = QuasiRibbonTableaux(Integer(3))
>>> QRT.shape()
Traceback (most recent call last):
...
ValueError: this family does not have a fixed shape