Combinatorial diagrams#

A combinatorial diagram is a collection of cells \((i,j)\) indexed by pairs of natural numbers.

For arbitrary diagrams, see Diagram. There are also two other specific types of diagrams implemented here. They are northwest diagrams (NorthwestDiagram) and Rothe diagrams (RotheDiagram(), a special kind of northwest diagram).

AUTHORS:

Trevor K. Karn (2022-08-01): initial version

class sage.combinat.diagram.Diagram(parent, cells, n_rows=None, n_cols=None, check=True)[source]#

Bases: ClonableArray

Combinatorial diagrams with positions indexed by rows and columns.

The positions are indexed by rows and columns as in a matrix. For example, a Ferrers diagram is a diagram obtained from a partition \(\lambda = (\lambda_0, \lambda_1, \ldots, \lambda_{\ell})\), where the cells are in rows \(i\) for \(0 \leq i \leq \ell\) and the cells in row \(i\) consist of \((i,j)\) for \(0 \leq j < \lambda_i\). In English notation, the indices are read from top left to bottom right as in a matrix.

Indexing conventions are the same as Partition. Printing the diagram of a partition, however, will always be in English notation.

EXAMPLES:

To create an arbitrary diagram, pass a list of all cells:

Sage

sage: from sage.combinat.diagram import Diagram
sage: cells = [(0,0), (0,1), (1,0), (1,1), (4,4), (4,5), (4,6), (5,4), (7, 6)]
sage: D = Diagram(cells); D
[(0, 0), (0, 1), (1, 0), (1, 1), (4, 4), (4, 5), (4, 6), (5, 4), (7, 6)]

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> cells = [(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(1),Integer(0)), (Integer(1),Integer(1)), (Integer(4),Integer(4)), (Integer(4),Integer(5)), (Integer(4),Integer(6)), (Integer(5),Integer(4)), (Integer(7), Integer(6))]
>>> D = Diagram(cells); D
[(0, 0), (0, 1), (1, 0), (1, 1), (4, 4), (4, 5), (4, 6), (5, 4), (7, 6)]

We can visualize the diagram by printing O’s and .’s. O’s are present in the cells which are present in the diagram and a . represents the absence of a cell in the diagram:

Sage

sage: D.pp()
O O . . . . .
O O . . . . .
. . . . . . .
. . . . . . .
. . . . O O O
. . . . O . .
. . . . . . .
. . . . . . O

Python

>>> from sage.all import *
>>> D.pp()
O O . . . . .
O O . . . . .
. . . . . . .
. . . . . . .
. . . . O O O
. . . . O . .
. . . . . . .
. . . . . . O

We can also check if certain cells are contained in a given diagram:

Sage

sage: (1, 0) in D
True
sage: (2, 2) in D
False

Python

>>> from sage.all import *
>>> (Integer(1), Integer(0)) in D
True
>>> (Integer(2), Integer(2)) in D
False

If you know that there are entire empty rows or columns at the end of the diagram, you can manually pass them with keyword arguments n_rows= or n_cols=:

Sage

sage: Diagram([(0,0), (0,3), (2,2), (2,4)]).pp()
O . . O .
. . . . .
. . O . O
sage: Diagram([(0,0), (0,3), (2,2), (2,4)], n_rows=6, n_cols=6).pp()
O . . O . .
. . . . . .
. . O . O .
. . . . . .
. . . . . .
. . . . . .

Python

>>> from sage.all import *
>>> Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))]).pp()
O . . O .
. . . . .
. . O . O
>>> Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))], n_rows=Integer(6), n_cols=Integer(6)).pp()
O . . O . .
. . . . . .
. . O . O .
. . . . . .
. . . . . .
. . . . . .

cells()[source]#

Return a list of the cells contained in the diagram self.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.cells()
[(0, 2), (0, 3), (1, 1), (3, 2)]

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.cells()
[(0, 2), (0, 3), (1, 1), (3, 2)]

check()[source]#

Check that this is a valid diagram.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,0), (0,3), (2,2), (2,4)])
sage: D.check()

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))])
>>> D.check()

In the next two examples, a bad diagram is passed. The first example fails because one cell is indexed by negative integers:

Sage

sage: D = Diagram([(0,0), (0,-3), (2,2), (2,4)])
Traceback (most recent call last):
...
ValueError: diagrams must be indexed by non-negative integers

Python

>>> from sage.all import *
>>> D = Diagram([(Integer(0),Integer(0)), (Integer(0),-Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))])
Traceback (most recent call last):
...
ValueError: diagrams must be indexed by non-negative integers

The next example fails because one cell is indexed by rational numbers:

Sage

sage: D = Diagram([(0,0), (0,3), (2/3,2), (2,4)])
Traceback (most recent call last):
...
ValueError: diagrams must be indexed by non-negative integers

Python

>>> from sage.all import *
>>> D = Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2)/Integer(3),Integer(2)), (Integer(2),Integer(4))])
Traceback (most recent call last):
...
ValueError: diagrams must be indexed by non-negative integers

n_cells()[source]#

Return the total number of cells contained in the diagram self.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.number_of_cells()
4
sage: D1.n_cells()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.number_of_cells()
4
>>> D1.n_cells()
4

ncols()[source]#

Return the total number of rows of self.

EXAMPLES:

The following example has three columns which are filled, but they are contained in rows 0 to 3 (for a total of four):

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D.number_of_cols()
4
sage: D.ncols()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D.number_of_cols()
4
>>> D.ncols()
4

We can also include empty columns at the end:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)], n_cols=6)
sage: D.number_of_cols()
6
sage: D.pp()
. . O O . .
. O . . . .
. . . . . .
. . O . . .

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))], n_cols=Integer(6))
>>> D.number_of_cols()
6
>>> D.pp()
. . O O . .
. O . . . .
. . . . . .
. . O . . .

nrows()[source]#

Return the total number of rows of self.

EXAMPLES:

The following example has three rows which are filled, but they are contained in rows 0 to 3 (for a total of four):

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.number_of_rows()
4
sage: D1.nrows()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.number_of_rows()
4
>>> D1.nrows()
4

The total number of rows includes including those which are empty. We can also include empty rows at the end:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)], n_rows=6)
sage: D.number_of_rows()
6
sage: D.pp()
. . O O
. O . .
. . . .
. . O .
. . . .
. . . .

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))], n_rows=Integer(6))
>>> D.number_of_rows()
6
>>> D.pp()
. . O O
. O . .
. . . .
. . O .
. . . .
. . . .

number_of_cells()[source]#

Return the total number of cells contained in the diagram self.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.number_of_cells()
4
sage: D1.n_cells()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.number_of_cells()
4
>>> D1.n_cells()
4

number_of_cols()[source]#

Return the total number of rows of self.

EXAMPLES:

The following example has three columns which are filled, but they are contained in rows 0 to 3 (for a total of four):

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D.number_of_cols()
4
sage: D.ncols()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D.number_of_cols()
4
>>> D.ncols()
4

We can also include empty columns at the end:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)], n_cols=6)
sage: D.number_of_cols()
6
sage: D.pp()
. . O O . .
. O . . . .
. . . . . .
. . O . . .

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))], n_cols=Integer(6))
>>> D.number_of_cols()
6
>>> D.pp()
. . O O . .
. O . . . .
. . . . . .
. . O . . .

number_of_rows()[source]#

Return the total number of rows of self.

EXAMPLES:

The following example has three rows which are filled, but they are contained in rows 0 to 3 (for a total of four):

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.number_of_rows()
4
sage: D1.nrows()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.number_of_rows()
4
>>> D1.nrows()
4

The total number of rows includes including those which are empty. We can also include empty rows at the end:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,2),(0,3),(1,1),(3,2)], n_rows=6)
sage: D.number_of_rows()
6
sage: D.pp()
. . O O
. O . .
. . . .
. . O .
. . . .
. . . .

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))], n_rows=Integer(6))
>>> D.number_of_rows()
6
>>> D.pp()
. . O O
. O . .
. . . .
. . O .
. . . .
. . . .

pp()[source]#

Return a visualization of the diagram.

Cells which are present in the diagram are filled with a O. Cells which are not present in the diagram are filled with a ..

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: Diagram([(0,0), (0,3), (2,2), (2,4)]).pp()
O . . O .
. . . . .
. . O . O
sage: Diagram([(0,0), (0,3), (2,2), (2,4)], n_rows=6, n_cols=6).pp()
O . . O . .
. . . . . .
. . O . O .
. . . . . .
. . . . . .
. . . . . .
sage: Diagram([]).pp()
-

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))]).pp()
O . . O .
. . . . .
. . O . O
>>> Diagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))], n_rows=Integer(6), n_cols=Integer(6)).pp()
O . . O . .
. . . . . .
. . O . O .
. . . . . .
. . . . . .
. . . . . .
>>> Diagram([]).pp()
-

size()[source]#

Return the total number of cells contained in the diagram self.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D1 = Diagram([(0,2),(0,3),(1,1),(3,2)])
sage: D1.number_of_cells()
4
sage: D1.n_cells()
4

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D1 = Diagram([(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(1),Integer(1)),(Integer(3),Integer(2))])
>>> D1.number_of_cells()
4
>>> D1.n_cells()
4

specht_module(base_ring=None)[source]#

Return the Specht module corresponding to self.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,0), (1,1), (2,2), (2,3)])
sage: SM = D.specht_module(QQ)                                              # needs sage.modules
sage: s = SymmetricFunctions(QQ).s()                                        # needs sage.modules
sage: s(SM.frobenius_image())                                               # needs sage.modules
s[2, 1, 1] + s[2, 2] + 2*s[3, 1] + s[4]

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(0)), (Integer(1),Integer(1)), (Integer(2),Integer(2)), (Integer(2),Integer(3))])
>>> SM = D.specht_module(QQ)                                              # needs sage.modules
>>> s = SymmetricFunctions(QQ).s()                                        # needs sage.modules
>>> s(SM.frobenius_image())                                               # needs sage.modules
s[2, 1, 1] + s[2, 2] + 2*s[3, 1] + s[4]

specht_module_dimension(base_ring=None)[source]#

Return the dimension of the Specht module corresponding to self.

INPUT:

base_ring – (default: \(\QQ\)) the base ring

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,0), (1,1), (2,2), (2,3)])
sage: D.specht_module_dimension()                                           # needs sage.modules
12
sage: D.specht_module(QQ).dimension()                                       # needs sage.modules
12

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> D = Diagram([(Integer(0),Integer(0)), (Integer(1),Integer(1)), (Integer(2),Integer(2)), (Integer(2),Integer(3))])
>>> D.specht_module_dimension()                                           # needs sage.modules
12
>>> D.specht_module(QQ).dimension()                                       # needs sage.modules
12

class sage.combinat.diagram.Diagrams(category=None)[source]#

Bases: UniqueRepresentation, Parent

The class of combinatorial diagrams.

A combinatorial diagram is a set of cells indexed by pairs of natural numbers. Calling an instance of Diagrams is one way to construct diagrams.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import Diagrams
sage: Dgms = Diagrams()
sage: D = Dgms([(0,0), (0,3), (2,2), (2,4)])
sage: D.parent()
Combinatorial diagrams

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagrams
>>> Dgms = Diagrams()
>>> D = Dgms([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(2),Integer(2)), (Integer(2),Integer(4))])
>>> D.parent()
Combinatorial diagrams

Element[source]#: alias of Diagram

from_composition(alpha)[source]#

Create the diagram corresponding to a weak composition \(\alpha \vDash n\).

EXAMPLES:

Sage

sage: alpha = Composition([3,0,2,1,4,4])
sage: from sage.combinat.diagram import Diagrams
sage: Diagrams()(alpha).pp()
O O O .
. . . .
O O . .
O . . .
O O O O
O O O O
sage: Diagrams().from_composition(alpha).pp()
O O O .
. . . .
O O . .
O . . .
O O O O
O O O O

Python

>>> from sage.all import *
>>> alpha = Composition([Integer(3),Integer(0),Integer(2),Integer(1),Integer(4),Integer(4)])
>>> from sage.combinat.diagram import Diagrams
>>> Diagrams()(alpha).pp()
O O O .
. . . .
O O . .
O . . .
O O O O
O O O O
>>> Diagrams().from_composition(alpha).pp()
O O O .
. . . .
O O . .
O . . .
O O O O
O O O O

from_polyomino(p)[source]#

Create the diagram corresponding to a 2d Polyomino

EXAMPLES:

Sage

sage: from sage.combinat.tiling import Polyomino                            # needs sage.modules
sage: p = Polyomino([(0,0),(1,0),(1,1),(1,2)])                              # needs sage.modules
sage: from sage.combinat.diagram import Diagrams
sage: Diagrams()(p).pp()                                                    # needs sage.modules
O . .
O O O

Python

>>> from sage.all import *
>>> from sage.combinat.tiling import Polyomino                            # needs sage.modules
>>> p = Polyomino([(Integer(0),Integer(0)),(Integer(1),Integer(0)),(Integer(1),Integer(1)),(Integer(1),Integer(2))])                              # needs sage.modules
>>> from sage.combinat.diagram import Diagrams
>>> Diagrams()(p).pp()                                                    # needs sage.modules
O . .
O O O

We can also call this method directly:

Sage

sage: Diagrams().from_polyomino(p).pp()                                     # needs sage.modules
O . .
O O O

Python

>>> from sage.all import *
>>> Diagrams().from_polyomino(p).pp()                                     # needs sage.modules
O . .
O O O

This only works for a 2d Polyomino:

Sage

sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')     # needs sage.modules
sage: Diagrams().from_polyomino(p)                                          # needs sage.modules
Traceback (most recent call last):
...
ValueError: the polyomino must be 2 dimensional

Python

>>> from sage.all import *
>>> p = Polyomino([(Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(1),Integer(1),Integer(0)), (Integer(1),Integer(1),Integer(1))], color='blue')     # needs sage.modules
>>> Diagrams().from_polyomino(p)                                          # needs sage.modules
Traceback (most recent call last):
...
ValueError: the polyomino must be 2 dimensional

from_zero_one_matrix(M, check=True)[source]#

Get a diagram from a matrix with entries in \(\{0, 1\}\), where positions of cells are indicated by the \(1\)’s.

EXAMPLES:

Sage

sage: M = matrix([[1,0,1,1],[0,1,1,0]])                                     # needs sage.modules
sage: from sage.combinat.diagram import Diagrams
sage: Diagrams()(M).pp()                                                    # needs sage.modules
O . O O
. O O .
sage: Diagrams().from_zero_one_matrix(M).pp()                               # needs sage.modules
O . O O
. O O .

sage: M = matrix([[1, 0, 0], [1, 0, 0], [0, 0, 0]])                         # needs sage.modules
sage: Diagrams()(M).pp()                                                    # needs sage.modules
O . .
O . .
. . .

Python

>>> from sage.all import *
>>> M = matrix([[Integer(1),Integer(0),Integer(1),Integer(1)],[Integer(0),Integer(1),Integer(1),Integer(0)]])                                     # needs sage.modules
>>> from sage.combinat.diagram import Diagrams
>>> Diagrams()(M).pp()                                                    # needs sage.modules
O . O O
. O O .
>>> Diagrams().from_zero_one_matrix(M).pp()                               # needs sage.modules
O . O O
. O O .

>>> M = matrix([[Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(0)]])                         # needs sage.modules
>>> Diagrams()(M).pp()                                                    # needs sage.modules
O . .
O . .
. . .

class sage.combinat.diagram.NorthwestDiagram(parent, cells, n_rows=None, n_cols=None, check=True)[source]#

Bases: Diagram

Diagrams with the northwest property.

A diagram is a set of cells indexed by natural numbers. Such a diagram has the northwest property if the presence of cells \((i1, j1)\) and \((i2, j2)\) implies the presence of the cell \((\min(i1, i2), \min(j1, j2))\). Diagrams with the northwest property are called northwest diagrams.

For general diagrams see Diagram.

EXAMPLES:

Sage

sage: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0, 2), (2,0)])

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram
>>> N = NorthwestDiagram([(Integer(0),Integer(0)), (Integer(0), Integer(2)), (Integer(2),Integer(0))])

To visualize them, use the .pp() method:

Sage

sage: N.pp()
O . O
. . .
O . .

Python

>>> from sage.all import *
>>> N.pp()
O . O
. . .
O . .

check()[source]#

A diagram has the northwest property if the presence of cells \((i1, j1)\) and \((i2, j2)\) implies the presence of the cell \((min(i1, i2), min(j1, j2))\). This method checks if the northwest property is satisfied for self

EXAMPLES:

Sage

sage: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0,3), (3,0)])
sage: N.check()

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram
>>> N = NorthwestDiagram([(Integer(0),Integer(0)), (Integer(0),Integer(3)), (Integer(3),Integer(0))])
>>> N.check()

Here is a non-example:

Sage

sage: notN = NorthwestDiagram([(0,1), (1,0)])  #.check() is implicit
Traceback (most recent call last):
...
ValueError: diagram is not northwest

Python

>>> from sage.all import *
>>> notN = NorthwestDiagram([(Integer(0),Integer(1)), (Integer(1),Integer(0))])  #.check() is implicit
Traceback (most recent call last):
...
ValueError: diagram is not northwest

peelable_tableaux()[source]#

Return the set of peelable tableaux whose diagram is self.

For a fixed northwest diagram \(D\), we say that a Young tableau \(T\) is \(D\)-peelable if:

the row indices of the cells in the first column of \(D\) are the entries in an initial segment in the first column of \(T\) and
the tableau \(Q\) obtained by removing those cells from \(T\) and playing jeu de taquin is \((D-C)\)-peelable, where \(D-C\) is the diagram formed by forgetting the first column of \(D\).

Reiner and Shimozono [RS1995] showed that the number \(\operatorname{red}(w)\) of reduced words of a permutation \(w\) may be computed using the peelable tableaux of the Rothe diagram \(D(w)\). Explicitly,

\[\operatorname{red}(w) = \sum_{T} f_{\operatorname{shape} T},\]

where the sum runs over the \(D(w)\)-peelable tableaux \(T\) and \(f_\lambda\) is the number of standard Young tableaux of shape \(\lambda\) (which may be computed using the hook-length formula).

EXAMPLES:

We can compute the \(D\)-peelable diagrams for a northwest diagram \(D\):

Sage

sage: from sage.combinat.diagram import NorthwestDiagram
sage: cells = [(0,0), (0,1), (0,2), (1,0), (2,0), (2,2), (2,4),
....:          (4,0), (4,2)]
sage: D = NorthwestDiagram(cells); D.pp()
O O O . .
O . . . .
O . O . O
. . . . .
O . O . .
sage: D.peelable_tableaux()
{[[1, 1, 1], [2, 3, 3], [3, 5], [5]],
[[1, 1, 1, 3], [2, 3], [3, 5], [5]]}

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram
>>> cells = [(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(0),Integer(2)), (Integer(1),Integer(0)), (Integer(2),Integer(0)), (Integer(2),Integer(2)), (Integer(2),Integer(4)),
...          (Integer(4),Integer(0)), (Integer(4),Integer(2))]
>>> D = NorthwestDiagram(cells); D.pp()
O O O . .
O . . . .
O . O . O
. . . . .
O . O . .
>>> D.peelable_tableaux()
{[[1, 1, 1], [2, 3, 3], [3, 5], [5]],
[[1, 1, 1, 3], [2, 3], [3, 5], [5]]}

EXAMPLES:

If the diagram is only one column, there is only one peelable tableau:

Sage

sage: from sage.combinat.diagram import NorthwestDiagram
sage: NWD = NorthwestDiagram([(0,0), (2,0)])
sage: NWD.peelable_tableaux()
{[[1], [3]]}

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram
>>> NWD = NorthwestDiagram([(Integer(0),Integer(0)), (Integer(2),Integer(0))])
>>> NWD.peelable_tableaux()
{[[1], [3]]}

From [RS1995], we know that there is only one peelable tableau for the Rothe diagram of the permutation (in one line notation) \(251643\):

Sage

sage: D = NorthwestDiagram([(1, 2), (1, 3), (3, 2), (3, 3), (4, 2)])
sage: D.pp()
. . . .
. . O O
. . . .
. . O O
. . O .

sage: D.peelable_tableaux()
{[[2, 2], [4, 4], [5]]}

Python

>>> from sage.all import *
>>> D = NorthwestDiagram([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(3), Integer(2)), (Integer(3), Integer(3)), (Integer(4), Integer(2))])
>>> D.pp()
. . . .
. . O O
. . . .
. . O O
. . O .

>>> D.peelable_tableaux()
{[[2, 2], [4, 4], [5]]}

Here are all the intermediate steps to compute the peelables for the Rothe diagram of (in one-line notation) \(64817235\). They are listed from deepest in the recursion to the final step. The recursion has depth five in this case so we will label the intermediate tableaux by \(D_i\) where \(i\) is the step in the recursion at which they appear.

Start with the one that has a single column:

Sage

sage: D5 = NorthwestDiagram([(2,0)]); D5.pp()
.
.
O
sage: D5.peelable_tableaux()
{[[3]]}

Python

>>> from sage.all import *
>>> D5 = NorthwestDiagram([(Integer(2),Integer(0))]); D5.pp()
.
.
O
>>> D5.peelable_tableaux()
{[[3]]}

Now we know all of the \(D_5\) peelables, so we can compute the \(D_4\) peelables:

Sage

sage: D4 = NorthwestDiagram([(0, 0), (2,0), (4, 0), (2, 2)])
sage: D4.pp()
O . .
. . .
O . O
. . .
O . .

sage: D4.peelable_tableaux()
{[[1, 3], [3], [5]]}

Python

>>> from sage.all import *
>>> D4 = NorthwestDiagram([(Integer(0), Integer(0)), (Integer(2),Integer(0)), (Integer(4), Integer(0)), (Integer(2), Integer(2))])
>>> D4.pp()
O . .
. . .
O . O
. . .
O . .

>>> D4.peelable_tableaux()
{[[1, 3], [3], [5]]}

There is only one \(D_4\) peelable, so we can compute the \(D_3\) peelables:

Sage

sage: D3 = NorthwestDiagram([(0,0), (0,1), (2, 1), (2, 3), (4,1)])
sage: D3.pp()
O O . .
. . . .
. O . O
. . . .
. O . .

sage: D3.peelable_tableaux()
{[[1, 1], [3, 3], [5]], [[1, 1, 3], [3], [5]]}

Python

>>> from sage.all import *
>>> D3 = NorthwestDiagram([(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(2), Integer(1)), (Integer(2), Integer(3)), (Integer(4),Integer(1))])
>>> D3.pp()
O O . .
. . . .
. O . O
. . . .
. O . .

>>> D3.peelable_tableaux()
{[[1, 1], [3, 3], [5]], [[1, 1, 3], [3], [5]]}

Now compute the \(D_2\) peelables:

Sage

sage: cells = [(0,0), (0,1), (0,2), (1,0), (2,0), (2,2), (2,4),
....:          (4,0), (4,2)]
sage: D2 = NorthwestDiagram(cells); D2.pp()
O O O . .
O . . . .
O . O . O
. . . . .
O . O . .

sage: D2.peelable_tableaux()
{[[1, 1, 1], [2, 3, 3], [3, 5], [5]],
[[1, 1, 1, 3], [2, 3], [3, 5], [5]]}

Python

>>> from sage.all import *
>>> cells = [(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(0),Integer(2)), (Integer(1),Integer(0)), (Integer(2),Integer(0)), (Integer(2),Integer(2)), (Integer(2),Integer(4)),
...          (Integer(4),Integer(0)), (Integer(4),Integer(2))]
>>> D2 = NorthwestDiagram(cells); D2.pp()
O O O . .
O . . . .
O . O . O
. . . . .
O . O . .

>>> D2.peelable_tableaux()
{[[1, 1, 1], [2, 3, 3], [3, 5], [5]],
[[1, 1, 1, 3], [2, 3], [3, 5], [5]]}

And the \(D_1\) peelables:

Sage

sage: cells = [(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (2,0),
....:          (2,1), (2,3), (2,5), (4,0), (4,1), (4,3)]
sage: D1 = NorthwestDiagram(cells); D1.pp()
O O O O . .
O O . . . .
O O . O . O
. . . . . .
O O . O . .

sage: D1.peelable_tableaux()
{[[1, 1, 1, 1], [2, 2, 3, 3], [3, 3, 5], [5, 5]],
[[1, 1, 1, 1, 3], [2, 2, 3], [3, 3, 5], [5, 5]]}

Python

>>> from sage.all import *
>>> cells = [(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(0),Integer(2)), (Integer(0),Integer(3)), (Integer(1),Integer(0)), (Integer(1),Integer(1)), (Integer(2),Integer(0)),
...          (Integer(2),Integer(1)), (Integer(2),Integer(3)), (Integer(2),Integer(5)), (Integer(4),Integer(0)), (Integer(4),Integer(1)), (Integer(4),Integer(3))]
>>> D1 = NorthwestDiagram(cells); D1.pp()
O O O O . .
O O . . . .
O O . O . O
. . . . . .
O O . O . .

>>> D1.peelable_tableaux()
{[[1, 1, 1, 1], [2, 2, 3, 3], [3, 3, 5], [5, 5]],
[[1, 1, 1, 1, 3], [2, 2, 3], [3, 3, 5], [5, 5]]}

Which we can use to get the \(D\) peelables:

Sage

sage: cells = [(0,0), (0,1), (0,2), (0,3), (0,4),
....:          (1,0), (1,1), (1,2),
....:          (2,0), (2,1), (2,2), (2,4), (2,6),
....:                 (4,1), (4,2), (4,4)]
sage: D = NorthwestDiagram(cells); D.pp()
O O O O O . .
O O O . . . .
O O O . O . O
. . . . . . .
. O O . O . .
sage: D.peelable_tableaux()
{[[1, 1, 1, 1, 1], [2, 2, 2, 3, 3], [3, 3, 3], [5, 5, 5]],
 [[1, 1, 1, 1, 1], [2, 2, 2, 3, 3], [3, 3, 3, 5], [5, 5]],
 [[1, 1, 1, 1, 1, 3], [2, 2, 2, 3], [3, 3, 3], [5, 5, 5]],
 [[1, 1, 1, 1, 1, 3], [2, 2, 2, 3], [3, 3, 3, 5], [5, 5]]}

Python

>>> from sage.all import *
>>> cells = [(Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(0),Integer(2)), (Integer(0),Integer(3)), (Integer(0),Integer(4)),
...          (Integer(1),Integer(0)), (Integer(1),Integer(1)), (Integer(1),Integer(2)),
...          (Integer(2),Integer(0)), (Integer(2),Integer(1)), (Integer(2),Integer(2)), (Integer(2),Integer(4)), (Integer(2),Integer(6)),
...                 (Integer(4),Integer(1)), (Integer(4),Integer(2)), (Integer(4),Integer(4))]
>>> D = NorthwestDiagram(cells); D.pp()
O O O O O . .
O O O . . . .
O O O . O . O
. . . . . . .
. O O . O . .
>>> D.peelable_tableaux()
{[[1, 1, 1, 1, 1], [2, 2, 2, 3, 3], [3, 3, 3], [5, 5, 5]],
 [[1, 1, 1, 1, 1], [2, 2, 2, 3, 3], [3, 3, 3, 5], [5, 5]],
 [[1, 1, 1, 1, 1, 3], [2, 2, 2, 3], [3, 3, 3], [5, 5, 5]],
 [[1, 1, 1, 1, 1, 3], [2, 2, 2, 3], [3, 3, 3, 5], [5, 5]]}

ALGORITHM:

This implementation uses the algorithm suggested in Remark 25 of [RS1995].

class sage.combinat.diagram.NorthwestDiagrams(category=None)[source]#

Bases: Diagrams

Diagrams satisfying the northwest property.

A diagram \(D\) is a northwest diagram if for every two cells \((i_1, j_1)\) and \((i_2, j_2)\) in \(D\) then there exists the cell \((\min(i_1, i_2), \min(j_1, j_2)) \in D\).

EXAMPLES:

Sage

sage: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0, 10), (5,0)]); N.pp()
O . . . . . . . . . O
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram
>>> N = NorthwestDiagram([(Integer(0),Integer(0)), (Integer(0), Integer(10)), (Integer(5),Integer(0))]); N.pp()
O . . . . . . . . . O
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .

Note that checking whether or not the northwest property is satisfied is automatically checked. The diagram found by adding the cell \((1,1)\) to the diagram above is not a northwest diagram. The cell \((1,0)\) should be present due to the presence of \((5,0)\) and \((1,1)\):

Sage

sage: from sage.combinat.diagram import Diagram
sage: Diagram([(0, 0), (0, 10), (5, 0), (1, 1)]).pp()
O . . . . . . . . . O
. O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .
sage: NorthwestDiagram([(0, 0), (0, 10), (5, 0), (1, 1)])
Traceback (most recent call last):
...
ValueError: diagram is not northwest

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import Diagram
>>> Diagram([(Integer(0), Integer(0)), (Integer(0), Integer(10)), (Integer(5), Integer(0)), (Integer(1), Integer(1))]).pp()
O . . . . . . . . . O
. O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .
>>> NorthwestDiagram([(Integer(0), Integer(0)), (Integer(0), Integer(10)), (Integer(5), Integer(0)), (Integer(1), Integer(1))])
Traceback (most recent call last):
...
ValueError: diagram is not northwest

However, this behavior can be turned off if you are confident that you are providing a northwest diagram:

Sage

sage: N = NorthwestDiagram([(0, 0), (0, 10), (5, 0),
....:                      (1, 1), (0, 1), (1, 0)],
....:                      check=False)
sage: N.pp()
O O . . . . . . . . O
O O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .

Python

>>> from sage.all import *
>>> N = NorthwestDiagram([(Integer(0), Integer(0)), (Integer(0), Integer(10)), (Integer(5), Integer(0)),
...                      (Integer(1), Integer(1)), (Integer(0), Integer(1)), (Integer(1), Integer(0))],
...                      check=False)
>>> N.pp()
O O . . . . . . . . O
O O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .

Note that arbitrary diagrams which happen to be northwest diagrams only live in the parent of Diagrams:

Sage

sage: D = Diagram([(0, 0), (0, 10), (5, 0), (1, 1), (0, 1), (1, 0)])
sage: D.pp()
O O . . . . . . . . O
O O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .
sage: from sage.combinat.diagram import NorthwestDiagrams
sage: D in NorthwestDiagrams()
False

Python

>>> from sage.all import *
>>> D = Diagram([(Integer(0), Integer(0)), (Integer(0), Integer(10)), (Integer(5), Integer(0)), (Integer(1), Integer(1)), (Integer(0), Integer(1)), (Integer(1), Integer(0))])
>>> D.pp()
O O . . . . . . . . O
O O . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .
>>> from sage.combinat.diagram import NorthwestDiagrams
>>> D in NorthwestDiagrams()
False

Here are some more examples:

Sage

sage: from sage.combinat.diagram import NorthwestDiagram, NorthwestDiagrams
sage: D = NorthwestDiagram([(0,1), (0,2), (1,1)]); D.pp()
. O O
. O .
sage: NWDgms = NorthwestDiagrams()
sage: D = NWDgms([(1,1), (1,2), (2,1)]); D.pp()
. . .
. O O
. O .
sage: D.parent()
Combinatorial northwest diagrams

Python

>>> from sage.all import *
>>> from sage.combinat.diagram import NorthwestDiagram, NorthwestDiagrams
>>> D = NorthwestDiagram([(Integer(0),Integer(1)), (Integer(0),Integer(2)), (Integer(1),Integer(1))]); D.pp()
. O O
. O .
>>> NWDgms = NorthwestDiagrams()
>>> D = NWDgms([(Integer(1),Integer(1)), (Integer(1),Integer(2)), (Integer(2),Integer(1))]); D.pp()
. . .
. O O
. O .
>>> D.parent()
Combinatorial northwest diagrams

Additionally, there are natural constructions of a northwest diagram given the data of a permutation (Rothe diagrams are the protypical example of northwest diagrams), or the data of a partition of an integer, or a skew partition.

The Rothe diagram \(D(\omega)\) of a permutation \(\omega\) is specified by the cells

\[D(\omega) = \{(\omega_j, i) : i<j,\, \omega_i > \omega_j \}.\]

We can construct one by calling rothe_diagram() method on the set of all NorthwestDiagrams:

Sage

sage: w = Permutations(4)([4,3,2,1])
sage: NorthwestDiagrams().rothe_diagram(w).pp()
O O O .
O O . .
O . . .
. . . .

Python

>>> from sage.all import *
>>> w = Permutations(Integer(4))([Integer(4),Integer(3),Integer(2),Integer(1)])
>>> NorthwestDiagrams().rothe_diagram(w).pp()
O O O .
O O . .
O . . .
. . . .

To turn a Ferrers diagram into a northwest diagram, we may call from_partition(). This will return a Ferrer’s diagram in the set of all northwest diagrams. For many use-cases it is probably better to get Ferrer’s diagrams by the corresponding method on partitons, namely sage.combinat.partitions.Partitions.ferrers_diagram():

Sage

sage: mu = Partition([7,3,1,1])
sage: mu.pp()
*******
***
*
*
sage: NorthwestDiagrams().from_partition(mu).pp()
O O O O O O O
O O O . . . .
O . . . . . .
O . . . . . .

Python

>>> from sage.all import *
>>> mu = Partition([Integer(7),Integer(3),Integer(1),Integer(1)])
>>> mu.pp()
*******
***
*
*
>>> NorthwestDiagrams().from_partition(mu).pp()
O O O O O O O
O O O . . . .
O . . . . . .
O . . . . . .

It is also possible to turn a Ferrers diagram of a skew partition into a northwest diagram, altough it is more subtle than just using the skew diagram itself. One must first reflect the partition about a vertical axis so that the skew partition looks “backwards”:

Sage

sage: mu, nu = Partition([5,4,3,2,1]), Partition([3,2,1])
sage: s = mu/nu; s.pp()
   **
  **
 **
**
*
sage: NorthwestDiagrams().from_skew_partition(s).pp()
O O . . .
. O O . .
. . O O .
. . . O O
. . . . O

Python

>>> from sage.all import *
>>> mu, nu = Partition([Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]), Partition([Integer(3),Integer(2),Integer(1)])
>>> s = mu/nu; s.pp()
   **
  **
 **
**
*
>>> NorthwestDiagrams().from_skew_partition(s).pp()
O O . . .
. O O . .
. . O O .
. . . O O
. . . . O

Element[source]#: alias of NorthwestDiagram

from_parallelogram_polyomino(p)[source]#

Create the diagram corresponding to a ParallelogramPolyomino.

EXAMPLES:

Sage

sage: p = ParallelogramPolyomino([[0, 0, 1, 0, 0, 0, 1, 1],                 # needs sage.modules
....:                              [1, 1, 0, 1, 0, 0, 0, 0]])
sage: from sage.combinat.diagram import NorthwestDiagrams
sage: NorthwestDiagrams().from_parallelogram_polyomino(p).pp()              # needs sage.modules
O O .
O O O
. O O
. O O
. O O

Python

>>> from sage.all import *
>>> p = ParallelogramPolyomino([[Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1)],                 # needs sage.modules
...                              [Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)]])
>>> from sage.combinat.diagram import NorthwestDiagrams
>>> NorthwestDiagrams().from_parallelogram_polyomino(p).pp()              # needs sage.modules
O O .
O O O
. O O
. O O
. O O

from_partition(mu)[source]#

Return the Ferrer’s diagram of mu as a northwest diagram.

EXAMPLES:

Sage

sage: mu = Partition([5,2,1]); mu.pp()
*****
**
*
sage: mu.parent()
Partitions
sage: from sage.combinat.diagram import NorthwestDiagrams
sage: D = NorthwestDiagrams().from_partition(mu)
sage: D.pp()
O O O O O
O O . . .
O . . . .
sage: D.parent()
Combinatorial northwest diagrams

Python

>>> from sage.all import *
>>> mu = Partition([Integer(5),Integer(2),Integer(1)]); mu.pp()
*****
**
*
>>> mu.parent()
Partitions
>>> from sage.combinat.diagram import NorthwestDiagrams
>>> D = NorthwestDiagrams().from_partition(mu)
>>> D.pp()
O O O O O
O O . . .
O . . . .
>>> D.parent()
Combinatorial northwest diagrams

This will print in English notation even if the notation is set to French for the partition:

Sage

sage: Partitions.options.convention="french"
sage: mu.pp()
*
**
*****
sage: D.pp()
O O O O O
O O . . .
O . . . .

Python

>>> from sage.all import *
>>> Partitions.options.convention="french"
>>> mu.pp()
*
**
*****
>>> D.pp()
O O O O O
O O . . .
O . . . .

from_permutation(w)[source]#

Return the Rothe diagram of w.

We construct a northwest diagram from a permutation by constructing its Rothe diagram. Formally, if \(\omega\) is a Permutation then the Rothe diagram \(D(\omega)\) is the diagram whose cells are

\[D(\omega) = \{(\omega_j, i) : i<j,\, \omega_i > \omega_j \}.\]

Informally, one can construct the Rothe diagram by starting with all \(n^2\) possible cells, and then deleting the cells \((i, \omega(i))\) as well as all cells to the right and below. (These are sometimes called “death rays”.)