A skew partition skp of size is a pair of
partitions
where
is a
partition of the integer
,
is a
partition of the integer
,
is an inner
partition of
, and
. We say
that
and
are respectively the inner
and outer partitions of skp.
A skew partition can be depicted by a diagram made of rows of
cells, in the same way as a partition. Only the cells of the outer
partition which are not in the inner partition
appear in the picture. For example, this is the
diagram of the skew partition [[5,4,3,1],[3,3,1]].
sage: print SkewPartition([[5,4,3,1],[3,3,1]]).diagram()
**
*
**
*
A skew partition can be connected, which can easily be described in graphic terms: for each pair of consecutive rows, there are at least two cells (one in each row) which have a common edge. This is the diagram of the connected skew partition [[5,4,3,1],[3,1]]:
sage: print SkewPartition([[5,4,3,1],[3,1]]).diagram()
**
***
***
*
sage: SkewPartition([[5,4,3,1],[3,1]]).is_connected()
True
The first example of a skew partition is not a connected one.
Applying a reflection with respect to the main diagonal yields the diagram of the conjugate skew partition, here [[4,3,3,2,1],[3,3,2]]:
sage: SkewPartition([[5,4,3,1],[3,3,1]]).conjugate()
[4, 3, 3, 2, 1] / [3, 2, 2]
sage: print SkewPartition([[5,4,3,1],[3,3,1]]).conjugate().diagram()
*
*
*
**
*
The outer corners of a skew partition are the corners of its outer partition. The inner corners are the internal corners of the outer partition when the inner partition is taken off. Shown below are the coordinates of the inner and outer corners.
sage: SkewPartition([[5,4,3,1],[3,3,1]]).outer_corners()
[(0, 4), (1, 3), (2, 2), (3, 0)]
sage: SkewPartition([[5,4,3,1],[3,3,1]]).inner_corners()
[(0, 3), (2, 1), (3, 0)]
EXAMPLES:
There are 9 skew partitions of size 3, with no empty row nor empty column:
sage: SkewPartitions(3).cardinality()
9
sage: SkewPartitions(3).list()
[[3] / [],
[2, 1] / [],
[3, 1] / [1],
[2, 2] / [1],
[3, 2] / [2],
[1, 1, 1] / [],
[2, 2, 1] / [1, 1],
[2, 1, 1] / [1],
[3, 2, 1] / [2, 1]]
There are 4 connected skew partitions of size 3:
sage: SkewPartitions(3, overlap=1).cardinality()
4
sage: SkewPartitions(3, overlap=1).list()
[[3] / [], [2, 1] / [], [2, 2] / [1], [1, 1, 1] / []]
This is the conjugate of the skew partition [[4,3,1], [2]]
sage: SkewPartition([[4,3,1], [2]]).conjugate()
[3, 2, 2, 1] / [1, 1]
Geometrically, we just applied a reflection with respect to the main diagonal on the diagram of the partition. Of course, this operation is an involution:
sage: SkewPartition([[4,3,1],[2]]).conjugate().conjugate()
[4, 3, 1] / [2]
The jacobi_trudi() method computes the Jacobi-Trudi matrix. See [Mac95] for a definition and discussion.
sage: SkewPartition([[4,3,1],[2]]).jacobi_trudi()
[h[2] h[] 0]
[h[5] h[3] h[]]
[h[6] h[4] h[1]]
This example shows how to compute the corners of a skew partition.
sage: SkewPartition([[4,3,1],[2]]).inner_corners()
[(0, 2), (1, 0)]
sage: SkewPartition([[4,3,1],[2]]).outer_corners()
[(0, 3), (1, 2), (2, 0)]
REFERENCES:
[Mac95] | Macdonald I.-G., (1995), “Symmetric Functions and Hall Polynomials”, Oxford Science Publication |
AUTHORS:
Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element
A skew partition.
A skew partition of shape is the Young diagram from the
partition
and removing the partition
from the upper-left
corner in English convention.
Return the Young diagram of self as a poset. The optional keyword variable orientation determines the order relation of the poset.
The poset always uses the set of cells of the Young diagram
of self as its ground set. The order relation of the poset
depends on the orientation variable (which defaults to
"SE"). Concretely, orientation has to be specified to
one of the strings "NW", "NE", "SW", and "SE",
standing for “northwest”, “northeast”, “southwest” and
“southeast”, respectively. If orientation is "SE", then
the order relation of the poset is such that a cell is
greater or equal to a cell
in the poset if and only if
lies weakly southeast of
(this means that
can be
reached from
by a sequence of south and east steps; the
sequence is allowed to consist of south steps only, or of east
steps only, or even be empty). Similarly the order relation is
defined for the other three orientations. The Young diagram is
supposed to be drawn in English notation.
The elements of the poset are the cells of the Young diagram
of self, written as tuples of zero-based coordinates (so
that stands for the
-th cell of the
-th row,
etc.).
EXAMPLES:
sage: p = SkewPartition([[3,3,1], [2,1]])
sage: Q = p.cell_poset(); Q
Finite poset containing 4 elements
sage: sorted(Q)
[(0, 2), (1, 1), (1, 2), (2, 0)]
sage: sorted(Q.maximal_elements())
[(1, 2), (2, 0)]
sage: sorted(Q.minimal_elements())
[(0, 2), (1, 1), (2, 0)]
sage: sorted(Q.upper_covers((1, 1)))
[(1, 2)]
sage: sorted(Q.upper_covers((0, 2)))
[(1, 2)]
sage: P = p.cell_poset(orientation="NW"); P
Finite poset containing 4 elements
sage: sorted(P)
[(0, 2), (1, 1), (1, 2), (2, 0)]
sage: sorted(P.minimal_elements())
[(1, 2), (2, 0)]
sage: sorted(P.maximal_elements())
[(0, 2), (1, 1), (2, 0)]
sage: sorted(P.upper_covers((1, 2)))
[(0, 2), (1, 1)]
sage: R = p.cell_poset(orientation="NE"); R
Finite poset containing 4 elements
sage: sorted(R)
[(0, 2), (1, 1), (1, 2), (2, 0)]
sage: R.maximal_elements()
[(0, 2)]
sage: R.minimal_elements()
[(2, 0)]
sage: R.upper_covers((2, 0))
[(1, 1)]
sage: sorted([len(R.upper_covers(v)) for v in R])
[0, 1, 1, 1]
TESTS:
We check that the posets are really what they should be for size
up to :
sage: def check_NW(n):
....: for p in SkewPartitions(n):
....: P = p.cell_poset(orientation="NW")
....: for c in p.cells():
....: for d in p.cells():
....: if P.le(c, d) != (c[0] >= d[0]
....: and c[1] >= d[1]):
....: return False
....: return True
sage: all( check_NW(n) for n in range(7) )
True
sage: def check_NE(n):
....: for p in SkewPartitions(n):
....: P = p.cell_poset(orientation="NE")
....: for c in p.cells():
....: for d in p.cells():
....: if P.le(c, d) != (c[0] >= d[0]
....: and c[1] <= d[1]):
....: return False
....: return True
sage: all( check_NE(n) for n in range(7) )
True
sage: def test_duality(n, ori1, ori2):
....: for p in SkewPartitions(n):
....: P = p.cell_poset(orientation=ori1)
....: Q = p.cell_poset(orientation=ori2)
....: for c in p.cells():
....: for d in p.cells():
....: if P.lt(c, d) != Q.lt(d, c):
....: return False
....: return True
sage: all( test_duality(n, "NW", "SE") for n in range(7) )
True
sage: all( test_duality(n, "NE", "SW") for n in range(7) )
True
sage: all( test_duality(n, "NE", "SE") for n in range(4) )
False
Return the coordinates of the cells of self. Coordinates are given as (row-index, column-index) and are 0 based.
EXAMPLES:
sage: SkewPartition([[4, 3, 1], [2]]).cells()
[(0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (2, 0)]
sage: SkewPartition([[4, 3, 1], []]).cells()
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (2, 0)]
sage: SkewPartition([[2], []]).cells()
[(0, 0), (0, 1)]
Return the column lengths of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[1,1]]).column_lengths()
[1, 2, 1]
sage: SkewPartition([[5,2,2,2],[2,1]]).column_lengths()
[2, 3, 1, 1, 1]
Return the set of cells in the columns of the outer shape of self which columns intersect the skew diagram of self.
EXAMPLES:
sage: skp = SkewPartition([[3,2,1],[2,1]])
sage: cells = Set([ (0,0), (0, 1), (0,2), (1, 0), (1, 1), (2, 0)])
sage: skp.columns_intersection_set() == cells
True
Return the conjugate of the skew partition skp.
EXAMPLES:
sage: SkewPartition([[3,2,1],[2]]).conjugate()
[3, 2, 1] / [1, 1]
Return the Ferrers diagram of self.
EXAMPLES:
sage: print SkewPartition([[5,4,3,1],[3,3,1]]).ferrers_diagram()
**
*
**
*
sage: print SkewPartition([[5,4,3,1],[3,1]]).diagram()
**
***
***
*
sage: SkewPartitions.global_options(diagram_str='#', convention="French")
sage: print SkewPartition([[5,4,3,1],[3,1]]).diagram()
#
###
###
##
sage: SkewPartitions.global_options.reset()
Return the Ferrers diagram of self.
EXAMPLES:
sage: print SkewPartition([[5,4,3,1],[3,3,1]]).ferrers_diagram()
**
*
**
*
sage: print SkewPartition([[5,4,3,1],[3,1]]).diagram()
**
***
***
*
sage: SkewPartitions.global_options(diagram_str='#', convention="French")
sage: print SkewPartition([[5,4,3,1],[3,1]]).diagram()
#
###
###
##
sage: SkewPartitions.global_options.reset()
Return the Frobenius rank of the skew partition self.
The Frobenius rank of a skew partition can be
defined in various ways. The quickest one is probably the
following: Writing
as
, and writing
as
, we define the Frobenius
rank of
to be the number of all
such that
In other words, the Frobenius rank of is the
number of rows in the Jacobi-Trudi matrix of
which don’t contain
. Further definitions have been
considered in [Stan2002] (where Frobenius rank is just being
called rank).
If is the empty shape, then the Frobenius rank of
is just the usual Frobenius rank of the
partition
(see
frobenius_rank()).
REFERENCES:
[Stan2002] | Richard P. Stanley, The rank and minimal border strip decompositions of a skew partition, J. Combin. Theory Ser. A 100 (2002), pp. 349-375. Arxiv math/0109092v1. |
EXAMPLES:
sage: SkewPartition([[8,8,7,4], [4,1,1]]).frobenius_rank()
4
sage: SkewPartition([[2,1], [1]]).frobenius_rank()
2
sage: SkewPartition([[2,1,1], [1]]).frobenius_rank()
2
sage: SkewPartition([[2,1,1], [1,1]]).frobenius_rank()
2
sage: SkewPartition([[5,4,3,2], [2,1,1]]).frobenius_rank()
3
sage: SkewPartition([[4,2,1], [3,1,1]]).frobenius_rank()
2
sage: SkewPartition([[4,2,1], [3,2,1]]).frobenius_rank()
1
If the inner shape is empty, then the Frobenius rank of the skew partition is just the standard Frobenius rank of the partition:
sage: all( SkewPartition([lam, Partition([])]).frobenius_rank()
....: == lam.frobenius_rank() for i in range(6)
....: for lam in Partitions(i) )
True
If the inner and outer shapes are equal, then the Frobenius rank is zero:
sage: all( SkewPartition([lam, lam]).frobenius_rank() == 0
....: for i in range(6) for lam in Partitions(i) )
True
Return the inner partition of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[1,1]]).inner()
[1, 1]
Return a list of the inner corners of self.
EXAMPLES:
sage: SkewPartition([[4, 3, 1], [2]]).inner_corners()
[(0, 2), (1, 0)]
sage: SkewPartition([[4, 3, 1], []]).inner_corners()
[(0, 0)]
Return True if self is a connected skew partition.
A skew partition is said to be connected if for each pair of consecutive rows, there are at least two cells (one in each row) which have a common edge.
EXAMPLES:
sage: SkewPartition([[5,4,3,1],[3,3,1]]).is_connected()
False
sage: SkewPartition([[5,4,3,1],[3,1]]).is_connected()
True
Return True if the overlap of self is at most n.
See also
EXAMPLES:
sage: SkewPartition([[5,4,3,1],[3,1]]).is_overlap(1)
True
Return True if and only if self is a ribbon, that is if it
has no boxes.
EXAMPLES:
sage: SkewPartition([[3,3,1],[2,2]]).is_ribbon()
True
sage: SkewPartition([[3,1],[3]]).is_ribbon()
True
sage: SkewPartition([[3,3,2],[2]]).is_ribbon()
False
Return the Jacobi-Trudi matrix of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[2,1]]).jacobi_trudi()
[h[1] 0 0]
[h[3] h[1] 0]
[h[5] h[3] h[1]]
sage: SkewPartition([[4,3,2],[2,1]]).jacobi_trudi()
[h[2] h[] 0]
[h[4] h[2] h[]]
[h[6] h[4] h[2]]
Return the -conjugate of the skew partition.
EXAMPLES:
sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(3)
[2, 1, 1, 1, 1] / [2, 1]
sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(4)
[2, 2, 1, 1] / [2, 1]
sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(5)
[3, 2, 1] / [2, 1]
Return the outer partition of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[1,1]]).outer()
[3, 2, 1]
Return a list of the outer corners of self.
EXAMPLES:
sage: SkewPartition([[4, 3, 1], [2]]).outer_corners()
[(0, 3), (1, 2), (2, 0)]
Return the overlap of self.
The overlap of two consecutive rows in a skew partition is the number of pairs of cells (one in each row) that share a common edge. This number can be positive, zero, or negative.
The overlap of a skew partition is the minimum of the overlap of the consecutive rows, or infinity in the case of at most one row. If the overlap is positive, then the skew partition is called connected.
EXAMPLES:
sage: SkewPartition([[],[]]).overlap()
+Infinity
sage: SkewPartition([[1],[]]).overlap()
+Infinity
sage: SkewPartition([[10],[]]).overlap()
+Infinity
sage: SkewPartition([[10],[2]]).overlap()
+Infinity
sage: SkewPartition([[10,1],[2]]).overlap()
-1
sage: SkewPartition([[10,10],[1]]).overlap()
9
Computation of the coefficients which appear in the Pieri formula for Macdonald polynomials given in his book ( Chapter 6.6 formula 6.24(ii) )
EXAMPLES:
sage: SkewPartition([[3,2,1],[2,1]]).pieri_macdonald_coeffs()
1
sage: SkewPartition([[3,2,1],[2,2]]).pieri_macdonald_coeffs()
(q^2*t^3 - q^2*t - t^2 + 1)/(q^2*t^3 - q*t^2 - q*t + 1)
sage: SkewPartition([[3,2,1],[2,2,1]]).pieri_macdonald_coeffs()
(q^6*t^8 - q^6*t^6 - q^4*t^7 - q^5*t^5 + q^4*t^5 - q^3*t^6 + q^5*t^3 + 2*q^3*t^4 + q*t^5 - q^3*t^2 + q^2*t^3 - q*t^3 - q^2*t - t^2 + 1)/(q^6*t^8 - q^5*t^7 - q^5*t^6 - q^4*t^6 + q^3*t^5 + 2*q^3*t^4 + q^3*t^3 - q^2*t^2 - q*t^2 - q*t + 1)
sage: SkewPartition([[3,3,2,2],[3,2,2,1]]).pieri_macdonald_coeffs()
(q^5*t^6 - q^5*t^5 + q^4*t^6 - q^4*t^5 - q^4*t^3 + q^4*t^2 - q^3*t^3 - q^2*t^4 + q^3*t^2 + q^2*t^3 - q*t^4 + q*t^3 + q*t - q + t - 1)/(q^5*t^6 - q^4*t^5 - q^3*t^4 - q^3*t^3 + q^2*t^3 + q^2*t^2 + q*t - 1)
Pretty-print self.
EXAMPLES:
sage: SkewPartition([[5,4,3,1],[3,3,1]]).pp()
**
*
**
*
The quotient map extended to skew partitions.
EXAMPLES:
sage: SkewPartition([[3, 3, 2, 1], [2, 1]]).quotient(2)
[[3] / [], [] / []]
Return the row lengths of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[1,1]]).row_lengths()
[2, 1, 1]
Return the set of cells in the rows of the outer shape of self which rows intersect the skew diagram of self.
EXAMPLES:
sage: skp = SkewPartition([[3,2,1],[2,1]])
sage: cells = Set([ (0,0), (0, 1), (0,2), (1, 0), (1, 1), (2, 0)])
sage: skp.rows_intersection_set() == cells
True
Return the size of self.
EXAMPLES:
sage: SkewPartition([[3,2,1],[1,1]]).size()
4
Return a directed acyclic graph corresponding to the skew partition self.
The directed acyclic graph corresponding to a skew partition
is the digraph whose vertices are the cells of
, and
whose edges go from each cell to its lower and right
neighbors (in English notation).
EXAMPLES:
sage: dag = SkewPartition([[3, 2, 1], [1, 1]]).to_dag()
sage: dag.edges()
[('0,1', '0,2', None), ('0,1', '1,1', None)]
sage: dag.vertices()
['0,1', '0,2', '1,1', '2,0']
Return self as a list of lists.
EXAMPLES:
sage: s = SkewPartition([[4,3,1],[2]])
sage: s.to_list()
[[4, 3, 1], [2]]
sage: type(s.to_list())
<type 'list'>
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
Skew partitions.
Warning
The iterator of this class only yields skew partitions which are reduced, in the sense that there are no empty rows before the last nonempty row, and there are no empty columns before the last nonempty column.
EXAMPLES:
sage: SkewPartitions(4)
Skew partitions of 4
sage: SkewPartitions(4).cardinality()
28
sage: SkewPartitions(row_lengths=[2,1,2])
Skew partitions with row lengths [2, 1, 2]
sage: SkewPartitions(4, overlap=2)
Skew partitions of 4 with a minimum overlap of 2
sage: SkewPartitions(4, overlap=2).list()
[[4] / [], [2, 2] / []]
alias of SkewPartition
Construct a partition from its row lengths and column lengths.
INPUT:
OUTPUT:
EXAMPLES:
sage: S = SkewPartitions()
sage: print S.from_row_and_column_length([3,1,2,2],[2,3,1,1,1]).diagram()
***
*
**
**
sage: S.from_row_and_column_length([],[])
[] / []
sage: S.from_row_and_column_length([1],[1])
[1] / []
sage: S.from_row_and_column_length([2,1],[2,1])
[2, 1] / []
sage: S.from_row_and_column_length([1,2],[1,2])
[2, 2] / [1]
sage: S.from_row_and_column_length([1,2],[1,3])
Traceback (most recent call last):
...
ValueError: Sum mismatch : [1, 2] and [1, 3]
sage: S.from_row_and_column_length([3,2,1,2],[2,3,1,1,1])
Traceback (most recent call last):
...
ValueError: Incompatible row and column length : [3, 2, 1, 2] and [2, 3, 1, 1, 1]
Warning
If some rows and columns have length zero, there is no way to retrieve unambiguously the skew partition. We therefore raise a ValueError. For examples here are two skew partitions with the same row and column lengths:
sage: skp1 = SkewPartition([[2,2],[2,2]])
sage: skp2 = SkewPartition([[2,1],[2,1]])
sage: skp1.row_lengths(), skp1.column_lengths()
([0, 0], [0, 0])
sage: skp2.row_lengths(), skp2.column_lengths()
([0, 0], [0, 0])
sage: SkewPartitions().from_row_and_column_length([0,0], [0,0])
Traceback (most recent call last):
...
ValueError: row and column length must be positive
TESTS:
sage: all(SkewPartitions().from_row_and_column_length(p.row_lengths(), p.column_lengths()) == p
....: for i in range(8) for p in SkewPartitions(i))
True
Sets and displays the global options for elements of the skew partition classes. If no parameters are set, then the function returns a copy of the options dictionary.
The options to skew partitions can be accessed as the method SkewPartitions.global_options of SkewPartitions and related parent classes.
OPTIONS:
EXAMPLES:
sage: SP = SkewPartition([[4,2,2,1], [3, 1, 1]])
sage: SP
[4, 2, 2, 1] / [3, 1, 1]
sage: SkewPartitions.global_options(display="lists")
sage: SP
[[4, 2, 2, 1], [3, 1, 1]]
Changing the convention for skew partitions also changes the convention option for partitions and tableaux and vice versa:
sage: SkewPartitions.global_options(display="diagram", convention='French')
sage: SP
*
*
*
*
sage: T = Tableau([[1,2,3],[4,5]])
sage: T.pp()
4 5
1 2 3
sage: P = Partition([4, 2, 2, 1])
sage: P.pp()
*
**
**
****
sage: Tableaux.global_options(convention="english")
sage: SP
*
*
*
*
sage: T.pp()
1 2 3
4 5
sage: SkewPartitions.global_options.reset()
See GlobalOptions for more features of these options.
Bases: sage.combinat.skew_partition.SkewPartitions
Class of all skew partitions.
Bases: sage.combinat.skew_partition.SkewPartitions
The set of skew partitions of n with overlap at least overlap and no empty row.
INPUT:
Caveat: this set is stable under conjugation only for overlap equal to 0 or 1. What exactly happens for negative overlaps is not yet well specified and subject to change (we may want to introduce vertical overlap constraints as well).
Todo
As is, this set is essentially the composition of Compositions(n) (which give the row lengths) and SkewPartition(n, row_lengths=...), and one would want to “inherit” list and cardinality from this composition.
Return the number of skew partitions of the integer
(with given overlap, if specified; and with no empty rows before
the last row).
EXAMPLES:
sage: SkewPartitions(0).cardinality()
1
sage: SkewPartitions(4).cardinality()
28
sage: SkewPartitions(5).cardinality()
87
sage: SkewPartitions(4, overlap=1).cardinality()
9
sage: SkewPartitions(5, overlap=1).cardinality()
20
sage: s = SkewPartitions(5, overlap=-1)
sage: s.cardinality() == len(s.list())
True
Bases: sage.combinat.skew_partition.SkewPartitions
All skew partitions with given row lengths.
This has been deprecated in trac ticket #14101. Use SkewPartitions().from_row_and_column_length() instead.
EXAMPLES:
sage: sage.combinat.skew_partition.from_row_and_column_length([3,1,2,2],[2,3,1,1,1])
doctest:...: DeprecationWarning: from_row_and_column_length is deprecated. Use SkewPartitions().from_row_and_column_length instead.
See http://trac.sagemath.org/14101 for details.
[5, 2, 2, 2] / [2, 1]
EXAMPLES:
sage: from sage.combinat.skew_partition import row_lengths_aux
sage: row_lengths_aux([[5,4,3,1],[3,3,1]])
[2, 1, 2]
sage: row_lengths_aux([[5,4,3,1],[3,1]])
[2, 3]