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)#
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)]
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
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
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=
orn_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 . . . . . . . . . . . . . . . . . . .
- cells()#
Return a
list
of the cells contained in the diagramself
.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)]
- check()#
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()
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
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
- n_cells()#
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
- ncols()#
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
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 . . .
- nrows()#
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
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 . . . . . . . . .
- number_of_cells()#
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
- number_of_cols()#
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
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 . . .
- number_of_rows()#
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
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 . . . . . . . . .
- pp()#
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() -
- size()#
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
- specht_module(base_ring=None)#
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]
- specht_module_dimension(base_ring=None)#
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
- class sage.combinat.diagram.Diagrams(category=None)#
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: 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_composition(alpha)#
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_polyomino(p)#
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
We can also call this method directly:
sage: 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_zero_one_matrix(M, check=True)#
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 . . . . .
- class sage.combinat.diagram.NorthwestDiagram(parent, cells, n_rows=None, n_cols=None, check=True)#
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)])
To visualize them, use the
.pp()
method:sage: N.pp() O . O . . . O . .
- check()#
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()
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
- peelable_tableaux()#
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: 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]]}
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 [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]]}
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: D5 = NorthwestDiagram([(2,0)]); D5.pp() . . O sage: 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]]}
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]]}
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]]}
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]]}
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]]}
ALGORITHM:
This implementation uses the algorithm suggested in Remark 25 of [RS1995].
- class sage.combinat.diagram.NorthwestDiagrams(category=None)#
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 . . . . . . . . . .
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
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 . . . . . . . . . .
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
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
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 allNorthwestDiagrams
:sage: w = Permutations(4)([4,3,2,1]) sage: 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, namelysage.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 . . . . . .
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
- Element#
alias of
NorthwestDiagram
- from_parallelogram_polyomino(p)#
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_partition(mu)#
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
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_permutation(w)#
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”.)
See also
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_skew_partition(s)#
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 . . . . .
- rothe_diagram(w)#
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”.)
See also
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- sage.combinat.diagram.RotheDiagram(w)#
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 . . . . . . . . . . . .
The Rothe diagram is a northwest diagram:
sage: 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 . . . . . .
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