# 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: 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)]

>>> 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: D.pp()
O O . . . . .
O O . . . . .
. . . . . . .
. . . . . . .
. . . . O O O
. . . . O . .
. . . . . . .
. . . . . . O

>>> 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: (1, 0) in D
True
sage: (2, 2) in D
False

>>> 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: 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 .
. . . . . .
. . . . . .
. . . . . .

>>> 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: 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)]

>>> 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: from sage.combinat.diagram import Diagram
sage: D = Diagram([(0,0), (0,3), (2,2), (2,4)])
sage: D.check()

>>> 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: D = Diagram([(0,0), (0,-3), (2,2), (2,4)])
Traceback (most recent call last):
...
ValueError: diagrams must be indexed by non-negative integers

>>> 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: 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

>>> 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: 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

>>> 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: 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

>>> 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: 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 . . .

>>> 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: 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

>>> 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: 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 .
. . . .
. . . .

>>> 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: 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

>>> 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: 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

>>> 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: 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 . . .

>>> 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: 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

>>> 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: 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 .
. . . .
. . . .

>>> 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: 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()
-

>>> 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: 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

>>> 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: 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]

>>> 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: 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

>>> 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]#

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: 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

>>> 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: 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

>>> 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: 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

>>> 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: Diagrams().from_polyomino(p).pp()                                     # needs sage.modules
O . .
O O O

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


This only works for a 2d Polyomino:

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

>>> 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: 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 . .
. . .

>>> 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: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0, 2), (2,0)])

>>> 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: N.pp()
O . O
. . .
O . .

>>> 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: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0,3), (3,0)])
sage: N.check()

>>> 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: notN = NorthwestDiagram([(0,1), (1,0)])  #.check() is implicit
Traceback (most recent call last):
...
ValueError: diagram is not northwest

>>> 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:

1. 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

2. 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: 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]]}

>>> 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: from sage.combinat.diagram import NorthwestDiagram
sage: NWD = NorthwestDiagram([(0,0), (2,0)])
sage: NWD.peelable_tableaux()
{[[1], [3]]}

>>> 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: 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]]}

>>> 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.

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

>>> 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: 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]]}

>>> 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: 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]]}

>>> 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: 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]]}

>>> 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: 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]]}

>>> 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: 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]]}

>>> 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: from sage.combinat.diagram import NorthwestDiagram
sage: N = NorthwestDiagram([(0,0), (0, 10), (5,0)]); N.pp()
O . . . . . . . . . O
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
O . . . . . . . . . .

>>> 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: 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

>>> 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: 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 . . . . . . . . . .

>>> 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: 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

>>> 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: 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

>>> 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: w = Permutations(4)([4,3,2,1])
sage: NorthwestDiagrams().rothe_diagram(w).pp()
O O O .
O O . .
O . . .
. . . .

>>> 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: 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 . . . . . .

>>> 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: 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

>>> 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: 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

>>> 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: 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

>>> 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: Partitions.options.convention="french"
sage: mu.pp()
*
**
*****
sage: D.pp()
O O O O O
O O . . .
O . . . .

>>> 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”.)

EXAMPLES:

sage: from sage.combinat.diagram import NorthwestDiagrams
sage: w = Permutations(3)([2,1,3])
sage: NorthwestDiagrams().rothe_diagram(w).pp()
O . .
. . .
. . .
sage: NorthwestDiagrams().from_permutation(w).pp()
O . .
. . .
. . .

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

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

>>> w = Permutations(Integer(8))([Integer(2),Integer(5),Integer(4),Integer(1),Integer(3),Integer(6),Integer(7),Integer(8)])
>>> NorthwestDiagrams().rothe_diagram(w).pp()
O . . . . . . .
O . O O . . . .
O . O . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

from_skew_partition(s)[source]#

Get the northwest diagram found by reflecting a skew shape across a vertical plane.

EXAMPLES:

sage: mu, nu = Partition([3,2,1]), Partition([2,1])
sage: s = mu/nu; s.pp()
*
*
*
sage: from sage.combinat.diagram import NorthwestDiagrams
sage: D = NorthwestDiagrams().from_skew_partition(s)
sage: D.pp()
O . .
. O .
. . O

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

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

>>> mu, nu = Partition([Integer(3),Integer(3),Integer(2)]), Partition([Integer(2),Integer(2),Integer(2)])
>>> s = mu/nu; s.pp()
*
*
>>> NorthwestDiagrams().from_skew_partition(s).pp()
O . .
O . .
. . .

rothe_diagram(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”.)

EXAMPLES:

sage: from sage.combinat.diagram import NorthwestDiagrams
sage: w = Permutations(3)([2,1,3])
sage: NorthwestDiagrams().rothe_diagram(w).pp()
O . .
. . .
. . .
sage: NorthwestDiagrams().from_permutation(w).pp()
O . .
. . .
. . .

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

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

>>> w = Permutations(Integer(8))([Integer(2),Integer(5),Integer(4),Integer(1),Integer(3),Integer(6),Integer(7),Integer(8)])
>>> NorthwestDiagrams().rothe_diagram(w).pp()
O . . . . . . .
O . O O . . . .
O . O . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

sage.combinat.diagram.RotheDiagram(w)[source]#

The Rothe diagram of a permutation w.

EXAMPLES:

sage: w = Permutations(9)([1, 7, 4, 5, 9, 3, 2, 8, 6])
sage: from sage.combinat.diagram import RotheDiagram
sage: D = RotheDiagram(w); D.pp()
. . . . . . . . .
. O O O O O . . .
. O O . . . . . .
. O O . . . . . .
. O O . . O . O .
. O . . . . . . .
. . . . . . . . .
. . . . . O . . .
. . . . . . . . .

>>> from sage.all import *
>>> w = Permutations(Integer(9))([Integer(1), Integer(7), Integer(4), Integer(5), Integer(9), Integer(3), Integer(2), Integer(8), Integer(6)])
>>> from sage.combinat.diagram import RotheDiagram
>>> D = RotheDiagram(w); D.pp()
. . . . . . . . .
. O O O O O . . .
. O O . . . . . .
. O O . . . . . .
. O O . . O . O .
. O . . . . . . .
. . . . . . . . .
. . . . . O . . .
. . . . . . . . .


The Rothe diagram is a northwest diagram:

sage: D.parent()
Combinatorial northwest diagrams

>>> from sage.all import *
>>> D.parent()
Combinatorial northwest diagrams


Some other examples:

sage: RotheDiagram([2, 1, 4, 3]).pp()
O . . .
. . . .
. . O .
. . . .

sage: RotheDiagram([4, 1, 3, 2]).pp()
O O O .
. . . .
. O . .
. . . .

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

>>> RotheDiagram([Integer(4), Integer(1), Integer(3), Integer(2)]).pp()
O O O .
. . . .
. O . .
. . . .


Currently, only elements of the set of sage.combinat.permutations.Permutations are supported. In particular, elements of permutation groups are not supported:

sage: w = SymmetricGroup(9).an_element()                                        # needs sage.groups
sage: RotheDiagram(w)                                                           # needs sage.groups
Traceback (most recent call last):
...
ValueError: w must be a permutation

>>> from sage.all import *
>>> w = SymmetricGroup(Integer(9)).an_element()                                        # needs sage.groups
>>> RotheDiagram(w)                                                           # needs sage.groups
Traceback (most recent call last):
...
ValueError: w must be a permutation