Integer partitions¶
A partition \(p\) of a nonnegative integer \(n\) is a non-increasing list of positive integers (the parts of the partition) with total sum \(n\).
A partition can be depicted by a diagram made of rows of cells, where the number of cells in the \(i^{th}\) row starting from the top is the \(i^{th}\) part of the partition.
The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition \([5, 3, 1]\) are \([[0,4], [1,2], [2,0]]\).
For display options, see Partitions.options
.
Note
Boxes is a synonym for cells. All methods will use ‘cell’ and ‘cells’ instead of ‘box’ and ‘boxes’.
Partitions are 0 based with coordinates in the form of (row-index, column-index).
If given coordinates of the form
(r, c)
, then use Python’s *-operator.Throughout this documentation, for a partition \(\lambda\) we will denote its conjugate partition by \(\lambda^{\prime}\). For more on conjugate partitions, see
Partition.conjugate()
.The comparisons on partitions use lexicographic order.
Note
We use the convention that lexicographic ordering is read from left-to-right. That is to say \([1, 3, 7]\) is smaller than \([2, 3, 4]\).
AUTHORS:
Mike Hansen (2007): initial version
Dan Drake (2009-03-28): deprecate RestrictedPartitions and implement Partitions_parts_in
Travis Scrimshaw (2012-01-12): Implemented latex function to Partition_class
Travis Scrimshaw (2012-05-09): Fixed Partitions(-1).list() infinite recursion loop by saying Partitions_n is the empty set.
Travis Scrimshaw (2012-05-11): Fixed bug in inner where if the length was longer than the length of the inner partition, it would include 0’s.
Andrew Mathas (2012-06-01): Removed deprecated functions and added compatibility with the PartitionTuple classes. See trac ticket #13072
Travis Scrimshaw (2012-10-12): Added options. Made
Partition_class
to the elementPartition
.Partitions*
are now all in the category framework exceptPartitionsRestricted
(which will eventually be removed). Cleaned up documentation.Matthew Lancellotti (2018-09-14): Added a bunch of “k” methods to Partition.
EXAMPLES:
There are \(5\) partitions of the integer \(4\):
sage: Partitions(4).cardinality()
5
sage: Partitions(4).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
We can use the method .first()
to get the ‘first’ partition of a
number:
sage: Partitions(4).first()
[4]
Using the method .next(p)
, we can calculate the ‘next’ partition
after \(p\). When we are at the last partition, None
will be returned:
sage: Partitions(4).next([4])
[3, 1]
sage: Partitions(4).next([1,1,1,1]) is None
True
We can use iter
to get an object which iterates over the partitions
one by one to save memory. Note that when we do something like
for part in Partitions(4)
this iterator is used in the background:
sage: g = iter(Partitions(4))
sage: next(g)
[4]
sage: next(g)
[3, 1]
sage: next(g)
[2, 2]
sage: for p in Partitions(4): print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
We can add constraints to the type of partitions we want. For example, to get all of the partitions of \(4\) of length \(2\), we’d do the following:
sage: Partitions(4, length=2).list()
[[3, 1], [2, 2]]
Here is the list of partitions of length at least \(2\) and the list of ones with length at most \(2\):
sage: Partitions(4, min_length=2).list()
[[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: Partitions(4, max_length=2).list()
[[4], [3, 1], [2, 2]]
The options min_part
and max_part
can be used to set constraints
on the sizes of all parts. Using max_part
, we can select
partitions having only ‘small’ entries. The following is the list
of the partitions of \(4\) with parts at most \(2\):
sage: Partitions(4, max_part=2).list()
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]
The min_part
options is complementary to max_part
and selects
partitions having only ‘large’ parts. Here is the list of all
partitions of \(4\) with each part at least \(2\):
sage: Partitions(4, min_part=2).list()
[[4], [2, 2]]
The options inner
and outer
can be used to set part-by-part
constraints. This is the list of partitions of \(4\) with [3, 1, 1]
as
an outer bound (that is, partitions of \(4\) contained in the partition
[3, 1, 1]
):
sage: Partitions(4, outer=[3,1,1]).list()
[[3, 1], [2, 1, 1]]
outer
sets max_length
to the length of its argument. Moreover, the
parts of outer
may be infinite to clear constraints on specific
parts. Here is the list of the partitions of \(4\) of length at most \(3\)
such that the second and third part are \(1\) when they exist:
sage: Partitions(4, outer=[oo,1,1]).list()
[[4], [3, 1], [2, 1, 1]]
Finally, here are the partitions of \(4\) with [1,1,1]
as an inner
bound (i. e., the partitions of \(4\) containing the partition [1,1,1]
).
Note that inner
sets min_length
to the length of its argument:
sage: Partitions(4, inner=[1,1,1]).list()
[[2, 1, 1], [1, 1, 1, 1]]
The options min_slope
and max_slope
can be used to set
constraints on the slope, that is on the difference p[i+1]-p[i]
of
two consecutive parts. Here is the list of the strictly decreasing
partitions of \(4\):
sage: Partitions(4, max_slope=-1).list()
[[4], [3, 1]]
The constraints can be combined together in all reasonable ways. Here are all the partitions of \(11\) of length between \(2\) and \(4\) such that the difference between two consecutive parts is between \(-3\) and \(-1\):
sage: Partitions(11,min_slope=-3,max_slope=-1,min_length=2,max_length=4).list()
[[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]]
Partition objects can also be created individually with Partition
:
sage: Partition([2,1])
[2, 1]
Once we have a partition object, then there are a variety of methods that we can use. For example, we can get the conjugate of a partition. Geometrically, the conjugate of a partition is the reflection of that partition through its main diagonal. Of course, this operation is an involution:
sage: Partition([4,1]).conjugate()
[2, 1, 1, 1]
sage: Partition([4,1]).conjugate().conjugate()
[4, 1]
If we create a partition with extra zeros at the end, they will be dropped:
sage: Partition([4,1,0,0])
[4, 1]
sage: Partition([0])
[]
sage: Partition([0,0])
[]
The idea of a partition being followed by infinitely many parts of size
\(0\) is consistent with the get_part
method:
sage: p = Partition([5, 2])
sage: p.get_part(0)
5
sage: p.get_part(10)
0
We can go back and forth between the standard and the exponential notations of a partition. The exponential notation can be padded with extra zeros:
sage: Partition([6,4,4,2,1]).to_exp()
[1, 1, 0, 2, 0, 1]
sage: Partition(exp=[1,1,0,2,0,1])
[6, 4, 4, 2, 1]
sage: Partition([6,4,4,2,1]).to_exp(5)
[1, 1, 0, 2, 0, 1]
sage: Partition([6,4,4,2,1]).to_exp(7)
[1, 1, 0, 2, 0, 1, 0]
sage: Partition([6,4,4,2,1]).to_exp(10)
[1, 1, 0, 2, 0, 1, 0, 0, 0, 0]
We can get the (zero-based!) coordinates of the corners of a partition:
sage: Partition([4,3,1]).corners()
[(0, 3), (1, 2), (2, 0)]
We can compute the core and quotient of a partition and build the partition back up from them:
sage: Partition([6,3,2,2]).core(3)
[2, 1, 1]
sage: Partition([7,7,5,3,3,3,1]).quotient(3)
([2], [1], [2, 2, 2])
sage: p = Partition([11,5,5,3,2,2,2])
sage: p.core(3)
[]
sage: p.quotient(3)
([2, 1], [4], [1, 1, 1])
sage: Partition(core=[],quotient=([2, 1], [4], [1, 1, 1]))
[11, 5, 5, 3, 2, 2, 2]
We can compute the \(0-1\) sequence and go back and forth:
sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0])
[5, 4]
sage: all(Partitions().from_zero_one(mu.zero_one_sequence())
....: == mu for n in range(5) for mu in Partitions(n))
True
We can compute the Frobenius coordinates and go back and forth:
sage: Partition([7,3,1]).frobenius_coordinates()
([6, 1], [2, 0])
sage: Partition(frobenius_coordinates=([6,1],[2,0]))
[7, 3, 1]
sage: all(mu == Partition(frobenius_coordinates=mu.frobenius_coordinates())
....: for n in range(12) for mu in Partitions(n))
True
We use the lexicographic ordering:
sage: pl = Partition([4,1,1])
sage: ql = Partitions()([3,3])
sage: pl > ql
True
sage: PL = Partitions()
sage: pl = PL([4,1,1])
sage: ql = PL([3,3])
sage: pl > ql
True
- class sage.combinat.partition.OrderedPartitions(n, k)¶
Bases:
sage.combinat.partition.Partitions
The class of ordered partitions of \(n\). If \(k\) is specified, then this contains only the ordered partitions of length \(k\).
An ordered partition of a nonnegative integer \(n\) means a list of positive integers whose sum is \(n\). This is the same as a composition of \(n\).
Note
It is recommended that you use
Compositions()
instead asOrderedPartitions()
wraps GAP.EXAMPLES:
sage: OrderedPartitions(3) Ordered partitions of 3 sage: OrderedPartitions(3).list() [[3], [2, 1], [1, 2], [1, 1, 1]] sage: OrderedPartitions(3,2) Ordered partitions of 3 of length 2 sage: OrderedPartitions(3,2).list() [[2, 1], [1, 2]] sage: OrderedPartitions(10,k=2).list() [[9, 1], [8, 2], [7, 3], [6, 4], [5, 5], [4, 6], [3, 7], [2, 8], [1, 9]] sage: OrderedPartitions(4).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: OrderedPartitions(3).cardinality() 4 sage: OrderedPartitions(3,2).cardinality() 2 sage: OrderedPartitions(10,2).cardinality() 9 sage: OrderedPartitions(15).cardinality() 16384
- list()¶
Return a list of partitions in
self
.EXAMPLES:
sage: OrderedPartitions(3).list() [[3], [2, 1], [1, 2], [1, 1, 1]] sage: OrderedPartitions(3,2).list() [[2, 1], [1, 2]]
- class sage.combinat.partition.Partition(parent, mu)¶
Bases:
sage.combinat.combinat.CombinatorialElement
A partition \(p\) of a nonnegative integer \(n\) is a non-increasing list of positive integers (the parts of the partition) with total sum \(n\).
A partition is often represented as a diagram consisting of cells, or boxes, placed in rows on top of each other such that the number of cells in the \(i^{th}\) row, reading from top to bottom, is the \(i^{th}\) part of the partition. The rows are left-justified (and become shorter and shorter the farther down one goes). This diagram is called the Young diagram of the partition, or more precisely its Young diagram in English notation. (French and Russian notations are variations on this representation.)
The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition
[5, 3, 1]
are[[0,4], [1,2], [2,0]]
.For display options, see
Partitions.options()
.Note
Partitions are 0 based with coordinates in the form of (row-index, column-index). For example consider the partition
mu=Partition([4,3,2,2])
, the first part ismu[0]
(which is 4), the second ismu[1]
, and so on, and the upper-left cell in English convention is(0, 0)
.A partition can be specified in one of the following ways:
a list (the default)
using exponential notation
by Frobenius coordinates
specifying its \(0-1\) sequence
specifying the core and the quotient
See the examples below.
EXAMPLES:
Creating partitions though parents:
sage: mu = Partitions(8)([3,2,1,1,1]); mu [3, 2, 1, 1, 1] sage: nu = Partition([3,2,1,1,1]); nu [3, 2, 1, 1, 1] sage: mu == nu True sage: mu is nu False sage: mu in Partitions() True sage: mu.parent() Partitions of the integer 8 sage: mu.size() 8 sage: mu.category() Category of elements of Partitions of the integer 8 sage: nu.parent() Partitions sage: nu.category() Category of elements of Partitions sage: mu[0] 3 sage: mu[1] 2 sage: mu[2] 1 sage: mu.pp() *** ** * * * sage: mu.removable_cells() [(0, 2), (1, 1), (4, 0)] sage: mu.down_list() [[2, 2, 1, 1, 1], [3, 1, 1, 1, 1], [3, 2, 1, 1]] sage: mu.addable_cells() [(0, 3), (1, 2), (2, 1), (5, 0)] sage: mu.up_list() [[4, 2, 1, 1, 1], [3, 3, 1, 1, 1], [3, 2, 2, 1, 1], [3, 2, 1, 1, 1, 1]] sage: mu.conjugate() [5, 2, 1] sage: mu.dominates(nu) True sage: nu.dominates(mu) True
Creating partitions using
Partition
:sage: Partition([3,2,1]) [3, 2, 1] sage: Partition(exp=[2,1,1]) [3, 2, 1, 1] sage: Partition(core=[2,1], quotient=[[2,1],[3],[1,1,1]]) [11, 5, 5, 3, 2, 2, 2] sage: Partition(frobenius_coordinates=([3,2],[4,0])) [4, 4, 1, 1, 1] sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0]) [5, 4] sage: [2,1] in Partitions() True sage: [2,1,0] in Partitions() True sage: Partition([1,2,3]) Traceback (most recent call last): ... ValueError: [1, 2, 3] is not an element of Partitions
Sage ignores trailing zeros at the end of partitions:
sage: Partition([3,2,1,0]) [3, 2, 1] sage: Partitions()([3,2,1,0]) [3, 2, 1] sage: Partitions(6)([3,2,1,0]) [3, 2, 1]
- add_cell(i, j=None)¶
Return a partition corresponding to
self
with a cell added in rowi
. (This does not changeself
.)EXAMPLES:
sage: Partition([3, 2, 1, 1]).add_cell(0) [4, 2, 1, 1] sage: cell = [4, 0]; Partition([3, 2, 1, 1]).add_cell(*cell) [3, 2, 1, 1, 1]
- add_horizontal_border_strip(k)¶
Return a list of all the partitions that can be obtained by adding a horizontal border strip of length
k
toself
.EXAMPLES:
sage: Partition([]).add_horizontal_border_strip(0) [[]] sage: Partition([]).add_horizontal_border_strip(2) [[2]] sage: Partition([2,2]).add_horizontal_border_strip(2) [[2, 2, 2], [3, 2, 1], [4, 2]] sage: Partition([3,2,2]).add_horizontal_border_strip(2) [[3, 2, 2, 2], [3, 3, 2, 1], [4, 2, 2, 1], [4, 3, 2], [5, 2, 2]]
Todo
Reimplement like
remove_horizontal_border_strip
usingIntegerListsLex
- add_vertical_border_strip(k)¶
Return a list of all the partitions that can be obtained by adding a vertical border strip of length
k
toself
.EXAMPLES:
sage: Partition([]).add_vertical_border_strip(0) [[]] sage: Partition([]).add_vertical_border_strip(2) [[1, 1]] sage: Partition([2,2]).add_vertical_border_strip(2) [[3, 3], [3, 2, 1], [2, 2, 1, 1]] sage: Partition([3,2,2]).add_vertical_border_strip(2) [[4, 3, 2], [4, 2, 2, 1], [3, 3, 3], [3, 3, 2, 1], [3, 2, 2, 1, 1]]
- addable_cells()¶
Return a list of the outside corners of the partition
self
.An outside corner (also called a cocorner) of a partition \(\lambda\) is a cell on \(\ZZ^2\) which does not belong to the Young diagram of \(\lambda\) but can be added to this Young diagram to still form a straight-shape Young diagram.
The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([2,2,1]).outside_corners() [(0, 2), (2, 1), (3, 0)] sage: Partition([2,2]).outside_corners() [(0, 2), (2, 0)] sage: Partition([6,3,3,1,1,1]).outside_corners() [(0, 6), (1, 3), (3, 1), (6, 0)] sage: Partition([]).outside_corners() [(0, 0)]
- addable_cells_residue(i, l)¶
Return a list of the outside corners of the partition
self
havingl
-residuei
.An outside corner (also called a cocorner) of a partition \(\lambda\) is a cell on \(\ZZ^2\) which does not belong to the Young diagram of \(\lambda\) but can be added to this Young diagram to still form a straight-shape Young diagram. See
residue()
for the definition of thel
-residue.The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).outside_corners_residue(0, 3) [(0, 3), (3, 0)] sage: Partition([3,2,1]).outside_corners_residue(1, 3) [(1, 2)] sage: Partition([3,2,1]).outside_corners_residue(2, 3) [(2, 1)]
- arm_cells(i, j)¶
Return the list of the cells of the arm of cell \((i,j)\) in
self
.The arm of cell \(c = (i,j)\) is the boxes that appear to the right of \(c\).
The cell coordinates are zero-based, i. e., the northwesternmost cell is \((0,0)\).
INPUT:
i, j
– two integers
OUTPUT:
A list of pairs of integers
EXAMPLES:
sage: Partition([4,4,3,1]).arm_cells(1,1) [(1, 2), (1, 3)] sage: Partition([]).arm_cells(0,0) Traceback (most recent call last): ... ValueError: The cell is not in the diagram
- arm_length(i, j)¶
Return the length of the arm of cell \((i,j)\) in
self
.The arm of cell \((i,j)\) is the cells that appear to the right of cell \((i,j)\).
The cell coordinates are zero-based, i. e., the northwesternmost cell is \((0,0)\).
INPUT:
i, j
– two integers
OUTPUT:
An integer or a
ValueError
EXAMPLES:
sage: p = Partition([2,2,1]) sage: p.arm_length(0, 0) 1 sage: p.arm_length(0, 1) 0 sage: p.arm_length(2, 0) 0 sage: Partition([3,3]).arm_length(0, 0) 2 sage: Partition([3,3]).arm_length(*[0,0]) 2
- arm_lengths(flat=False)¶
Return a tableau of shape
self
where each cell is filled with its arm length. The optional boolean parameterflat
provides the option of returning a flat list.EXAMPLES:
sage: Partition([2,2,1]).arm_lengths() [[1, 0], [1, 0], [0]] sage: Partition([2,2,1]).arm_lengths(flat=True) [1, 0, 1, 0, 0] sage: Partition([3,3]).arm_lengths() [[2, 1, 0], [2, 1, 0]] sage: Partition([3,3]).arm_lengths(flat=True) [2, 1, 0, 2, 1, 0]
- arms_legs_coeff(i, j)¶
This is a statistic on a cell \(c = (i,j)\) in the diagram of partition \(p\) given by
\[\frac{ 1 - q^a \cdot t^{\ell + 1} }{ 1 - q^{a + 1} \cdot t^{\ell} }\]where \(a\) is the arm length of \(c\) and \(\ell\) is the leg length of \(c\).
The coordinates
i
andj
of the cell are understood to be \(0\)-based, so that(0, 0)
is the northwesternmost cell (in English notation).EXAMPLES:
sage: Partition([3,2,1]).arms_legs_coeff(1,1) (-t + 1)/(-q + 1) sage: Partition([3,2,1]).arms_legs_coeff(0,0) (-q^2*t^3 + 1)/(-q^3*t^2 + 1) sage: Partition([3,2,1]).arms_legs_coeff(*[0,0]) (-q^2*t^3 + 1)/(-q^3*t^2 + 1)
- atom()¶
Return a list of the standard tableaux of size
self.size()
whose atom is equal toself
.EXAMPLES:
sage: Partition([2,1]).atom() [[[1, 2], [3]]] sage: Partition([3,2,1]).atom() [[[1, 2, 3, 6], [4, 5]], [[1, 2, 3], [4, 5], [6]]]
- attacking_pairs()¶
Return a list of the attacking pairs of the Young diagram of
self
.A pair of cells \((c, d)\) of a Young diagram (in English notation) is said to be attacking if one of the following conditions holds:
\(c\) and \(d\) lie in the same row with \(c\) strictly to the west of \(d\).
\(c\) is in the row immediately to the south of \(d\), and \(c\) lies strictly east of \(d\).
This particular method returns each pair \((c, d)\) as a tuple, where each of \(c\) and \(d\) is given as a tuple \((i, j)\) with \(i\) and \(j\) zero-based (so \(i = 0\) means that the cell lies in the topmost row).
EXAMPLES:
sage: p = Partition([3, 2]) sage: p.attacking_pairs() [((0, 0), (0, 1)), ((0, 0), (0, 2)), ((0, 1), (0, 2)), ((1, 0), (1, 1)), ((1, 1), (0, 0))] sage: Partition([]).attacking_pairs() []
- aut(t=0, q=0)¶
Return the size of the centralizer of any permutation of cycle type
self
.If \(m_i\) is the multiplicity of \(i\) as a part of \(p\), this is given by
\[\prod_i m_i! i^{m_i}.\]Including the optional parameters \(t\) and \(q\) gives the \(q,t\) analog, which is the former product times
\[\prod_{i=1}^{\mathrm{length}(p)} \frac{1 - q^{p_i}}{1 - t^{p_i}}.\]See Section 1.3, p. 24, in [Ke1991].
EXAMPLES:
sage: Partition([2,2,1]).centralizer_size() 8 sage: Partition([2,2,2]).centralizer_size() 48 sage: Partition([2,2,1]).centralizer_size(q=2, t=3) 9/16 sage: Partition([]).centralizer_size() 1 sage: Partition([]).centralizer_size(q=2, t=4) 1
- beta_numbers(length=None)¶
Return the set of beta numbers corresponding to
self
.The optional argument
length
specifies the length of the beta set (which must be at least the length ofself
).For more on beta numbers, see
frobenius_coordinates()
.EXAMPLES:
sage: Partition([4,3,2]).beta_numbers() [6, 4, 2] sage: Partition([4,3,2]).beta_numbers(5) [8, 6, 4, 1, 0] sage: Partition([]).beta_numbers() [] sage: Partition([]).beta_numbers(3) [2, 1, 0] sage: Partition([6,4,1,1]).beta_numbers() [9, 6, 2, 1] sage: Partition([6,4,1,1]).beta_numbers(6) [11, 8, 4, 3, 1, 0] sage: Partition([1,1,1]).beta_numbers() [3, 2, 1] sage: Partition([1,1,1]).beta_numbers(4) [4, 3, 2, 0]
- block(e, multicharge=(0))¶
Return a dictionary \(\beta\) that determines the block associated to the partition
self
and thequantum_characteristic()
e
.INPUT:
e
– the quantum characteristicmulticharge
– the multicharge (default \((0,)\))
OUTPUT:
A dictionary giving the multiplicities of the residues in the partition tuple
self
In more detail, the value
beta[i]
is equal to the number of nodes of residuei
. This corresponds to the positive root\[\sum_{i\in I} \beta_i \alpha_i \in Q^+,\]a element of the positive root lattice of the corresponding Kac-Moody algebra. See [DJM1998] and [BK2009] for more details.
This is a useful statistics because two Specht modules for a Hecke algebra of type \(A\) belong to the same block if and only if they correspond to same element \(\beta\) of the root lattice, given above.
We return a dictionary because when the quantum characteristic is \(0\), the Cartan type is \(A_{\infty}\), in which case the simple roots are indexed by the integers.
EXAMPLES:
sage: Partition([4,3,2]).block(0) {-2: 1, -1: 2, 0: 2, 1: 2, 2: 1, 3: 1} sage: Partition([4,3,2]).block(2) {0: 4, 1: 5} sage: Partition([4,3,2]).block(2, multicharge=(1,)) {0: 5, 1: 4} sage: Partition([4,3,2]).block(3) {0: 3, 1: 3, 2: 3} sage: Partition([4,3,2]).block(4) {0: 2, 1: 2, 2: 2, 3: 3}
- boundary()¶
Return the integer coordinates of points on the boundary of
self
.For the following description, picture the Ferrer’s diagram of
self
using the French convention. Recall that the French convention puts the longest row on the bottom and the shortest row on the top. In addition, interpret the Ferrer’s diagram as 1 x 1 cells in the Euclidean plane. So ifself
was the partition [3, 1], the lower-left vertices of the 1 x 1 cells in the Ferrer’s diagram would be (0, 0), (1, 0), (2, 0), and (0, 1).The boundary of a partition is the set \(\{ \text{NE}(d) \mid \forall d\:\text{diagonal} \}\). That is, for every diagonal line \(y = x + b\) where \(b \in \mathbb{Z}\), we find the northeasternmost (NE) point on that diagonal which is also in the Ferrer’s diagram.
The boundary will go from bottom-right to top-left.
EXAMPLES:
Consider the partition (1) depicted as a square on a cartesian plane with vertices (0, 0), (1, 0), (1, 1), and (0, 1). Three of those vertices in the appropriate order form the boundary:
sage: Partition([1]).boundary() [(1, 0), (1, 1), (0, 1)]
The partition (3, 1) can be visualized as three squares on a cartesian plane. The coordinates of the appropriate vertices form the boundary:
sage: Partition([3, 1]).boundary() [(3, 0), (3, 1), (2, 1), (1, 1), (1, 2), (0, 2)]
See also
k_rim()
. You might have been looking fork_boundary()
instead.
- cell_poset(orientation='SE')¶
Return the Young diagram of
self
as a poset. The optional keyword variableorientation
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 theorientation
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. Iforientation
is"SE"
, then the order relation of the poset is such that a cell \(u\) is greater or equal to a cell \(v\) in the poset if and only if \(u\) lies weakly southeast of \(v\) (this means that \(u\) can be reached from \(v\) 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 \((3, 7)\) stands for the \(8\)-th cell of the \(4\)-th row, etc.).EXAMPLES:
sage: p = Partition([3,3,1]) sage: Q = p.cell_poset(); Q Finite poset containing 7 elements sage: sorted(Q) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)] sage: sorted(Q.maximal_elements()) [(1, 2), (2, 0)] sage: Q.minimal_elements() [(0, 0)] sage: sorted(Q.upper_covers((1, 0))) [(1, 1), (2, 0)] sage: Q.upper_covers((1, 1)) [(1, 2)] sage: P = p.cell_poset(orientation="NW"); P Finite poset containing 7 elements sage: sorted(P) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)] sage: sorted(P.minimal_elements()) [(1, 2), (2, 0)] sage: P.maximal_elements() [(0, 0)] sage: P.upper_covers((2, 0)) [(1, 0)] sage: sorted(P.upper_covers((1, 2))) [(0, 2), (1, 1)] sage: sorted(P.upper_covers((1, 1))) [(0, 1), (1, 0)] sage: sorted([len(P.upper_covers(v)) for v in P]) [0, 1, 1, 1, 1, 2, 2] sage: R = p.cell_poset(orientation="NE"); R Finite poset containing 7 elements sage: sorted(R) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)] sage: R.maximal_elements() [(0, 2)] sage: R.minimal_elements() [(2, 0)] sage: sorted([len(R.upper_covers(v)) for v in R]) [0, 1, 1, 1, 1, 2, 2] sage: R.is_isomorphic(P) False sage: R.is_isomorphic(P.dual()) False
Linear extensions of
p.cell_poset()
are in 1-to-1 correspondence with standard Young tableaux of shape \(p\):sage: all( len(p.cell_poset().linear_extensions()) ....: == len(p.standard_tableaux()) ....: for n in range(8) for p in Partitions(n) ) True
This is not the case for northeast orientation:
sage: q = Partition([3, 1]) sage: q.cell_poset(orientation="NE").is_chain() True
- cells()¶
Return the coordinates of the cells of
self
.EXAMPLES:
sage: Partition([2,2]).cells() [(0, 0), (0, 1), (1, 0), (1, 1)] sage: Partition([3,2]).cells() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)]
- centralizer_size(t=0, q=0)¶
Return the size of the centralizer of any permutation of cycle type
self
.If \(m_i\) is the multiplicity of \(i\) as a part of \(p\), this is given by
\[\prod_i m_i! i^{m_i}.\]Including the optional parameters \(t\) and \(q\) gives the \(q,t\) analog, which is the former product times
\[\prod_{i=1}^{\mathrm{length}(p)} \frac{1 - q^{p_i}}{1 - t^{p_i}}.\]See Section 1.3, p. 24, in [Ke1991].
EXAMPLES:
sage: Partition([2,2,1]).centralizer_size() 8 sage: Partition([2,2,2]).centralizer_size() 48 sage: Partition([2,2,1]).centralizer_size(q=2, t=3) 9/16 sage: Partition([]).centralizer_size() 1 sage: Partition([]).centralizer_size(q=2, t=4) 1
- character_polynomial()¶
Return the character polynomial associated to the partition
self
.The character polynomial \(q_\mu\) associated to a partition \(\mu\) is defined by
\[q_\mu(x_1, x_2, \ldots, x_k) = \downarrow \sum_{\alpha \vdash k} \frac{ \chi^\mu_\alpha }{1^{a_1}2^{a_2}\cdots k^{a_k}a_1!a_2!\cdots a_k!} \prod_{i=1}^{k} (ix_i-1)^{a_i}\]where \(k\) is the size of \(\mu\), and \(a_i\) is the multiplicity of \(i\) in \(\alpha\).
It is computed in the following manner:
Expand the Schur function \(s_\mu\) in the power-sum basis,
Replace each \(p_i\) with \(ix_i-1\),
Apply the umbral operator \(\downarrow\) to the resulting polynomial.
EXAMPLES:
sage: Partition([1]).character_polynomial() x - 1 sage: Partition([1,1]).character_polynomial() 1/2*x0^2 - 3/2*x0 - x1 + 1 sage: Partition([2,1]).character_polynomial() 1/3*x0^3 - 2*x0^2 + 8/3*x0 - x2
- components()¶
Return a list containing the shape of
self
.This method exists only for compatibility with
PartitionTuples
.EXAMPLES:
sage: Partition([3,2]).components() [[3, 2]]
- conjugacy_class_size()¶
Return the size of the conjugacy class of the symmetric group indexed by
self
.EXAMPLES:
sage: Partition([2,2,2]).conjugacy_class_size() 15 sage: Partition([2,2,1]).conjugacy_class_size() 15 sage: Partition([2,1,1]).conjugacy_class_size() 6
- conjugate()¶
Return the conjugate partition of the partition
self
. This is also called the associated partition or the transpose in the literature.EXAMPLES:
sage: Partition([2,2]).conjugate() [2, 2] sage: Partition([6,3,1]).conjugate() [3, 2, 2, 1, 1, 1]
The conjugate partition is obtained by transposing the Ferrers diagram of the partition (see
ferrers_diagram()
):sage: print(Partition([6,3,1]).ferrers_diagram()) ****** *** * sage: print(Partition([6,3,1]).conjugate().ferrers_diagram()) *** ** ** * * *
- contains(x)¶
Return
True
ifx
is a partition whose Ferrers diagram is contained in the Ferrers diagram ofself
.EXAMPLES:
sage: p = Partition([3,2,1]) sage: p.contains([2,1]) True sage: all(p.contains(mu) for mu in Partitions(3)) True sage: all(p.contains(mu) for mu in Partitions(4)) False
- content(r, c, multicharge=(0))¶
Return the content of the cell at row \(r\) and column \(c\).
The content of a cell is \(c - r\).
For consistency with partition tuples there is also an optional
multicharge
argument which is an offset to the usual content. By setting themulticharge
equal to the 0-element of the ring \(\ZZ/e\ZZ\), the corresponding \(e\)-residue will be returned. This is the content modulo \(e\).The content (and residue) do not strictly depend on the partition, however, this method is included because it is often useful in the context of partitions.
EXAMPLES:
sage: Partition([2,1]).content(1,0) -1 sage: p = Partition([3,2]) sage: sum([p.content(*c) for c in p.cells()]) 2
and now we return the 3-residue of a cell:
sage: Partition([2,1]).content(1,0, multicharge=[IntegerModRing(3)(0)]) 2
- contents_tableau(multicharge=(0))¶
Return the tableau which has
(k,r,c)
-th cell equal to the contentmulticharge[k] - r + c
of the cell.EXAMPLES:
sage: Partition([2,1]).contents_tableau() [[0, 1], [-1]] sage: Partition([3,2,1,1]).contents_tableau().pp() 0 1 2 -1 0 -2 -3 sage: Partition([3,2,1,1]).contents_tableau([ IntegerModRing(3)(0)] ).pp() 0 1 2 2 0 1 0
- core(length)¶
Return the
length
-core of the partition – in the literature the core is commonly referred to as the \(k\)-core, \(p\)-core, \(r\)-core, … .The \(r\)-core of a partition \(\lambda\) can be obtained by repeatedly removing rim hooks of size \(r\) from (the Young diagram of) \(\lambda\) until this is no longer possible. The remaining partition is the core.
EXAMPLES:
sage: Partition([6,3,2,2]).core(3) [2, 1, 1] sage: Partition([]).core(3) [] sage: Partition([8,7,7,4,1,1,1,1,1]).core(3) [2, 1, 1]
- corners()¶
Return a list of the corners of the partition
self
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind.
The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners() [(0, 2), (1, 1), (2, 0)] sage: Partition([3,3,1]).corners() [(1, 2), (2, 0)] sage: Partition([]).corners() []
- corners_residue(i, l)¶
Return a list of the corners of the partition
self
havingl
-residuei
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind. See
residue()
for the definition of thel
-residue.The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners_residue(0, 3) [(1, 1)] sage: Partition([3,2,1]).corners_residue(1, 3) [(2, 0)] sage: Partition([3,2,1]).corners_residue(2, 3) [(0, 2)]
- crank()¶
Return the Dyson crank of
self
.The Dyson crank of a partition \(\lambda\) is defined as follows: If \(\lambda\) contains at least one \(1\), then the crank is \(\mu(\lambda) - \omega(\lambda)\), where \(\omega(\lambda)\) is the number of \(1\), and \(\mu(\lambda)\) is the number of parts of \(\lambda\) larger than \(\omega(\lambda)\). If \(\lambda\) contains no \(1\), then the crank is simply the largest part of \(\lambda\).
REFERENCES:
EXAMPLES:
sage: Partition([]).crank() 0 sage: Partition([3,2,2]).crank() 3 sage: Partition([5,4,2,1,1]).crank() 0 sage: Partition([1,1,1]).crank() -3 sage: Partition([6,4,4,3]).crank() 6 sage: Partition([6,3,3,1,1]).crank() 1 sage: Partition([6]).crank() 6 sage: Partition([5,1]).crank() 0 sage: Partition([4,2]).crank() 4 sage: Partition([4,1,1]).crank() -1 sage: Partition([3,3]).crank() 3 sage: Partition([3,2,1]).crank() 1 sage: Partition([3,1,1,1]).crank() -3 sage: Partition([2,2,2]).crank() 2 sage: Partition([2,2,1,1]).crank() -2 sage: Partition([2,1,1,1,1]).crank() -4 sage: Partition([1,1,1,1,1,1]).crank() -6
- defect(e, multicharge=(0))¶
Return the
e
-defect or thee
-weight ofself
.The \(e\)-defect is the number of (connected) \(e\)-rim hooks that can be removed from the partition.
The defect of a partition is given by
\[\text{defect}(\beta) = (\Lambda, \beta) - \tfrac12(\beta, \beta),\]where \(\Lambda = \sum_r \Lambda_{\kappa_r}\) for the multicharge \((\kappa_1, \ldots, \kappa_{\ell})\) and \(\beta = \sum_{(r,c)} \alpha_{(c-r) \pmod e}\), with the sum being over the cells in the partition.
INPUT:
e
– the quantum characteristicmulticharge
– the multicharge (default \((0,)\))
OUTPUT:
a non-negative integer, which is the defect of the block containing the partition
self
EXAMPLES:
sage: Partition([4,3,2]).defect(2) 3 sage: Partition([0]).defect(2) 0 sage: Partition([3]).defect(2) 1 sage: Partition([6]).defect(2) 3 sage: Partition([9]).defect(2) 4 sage: Partition([12]).defect(2) 6 sage: Partition([4,3,2]).defect(3) 3 sage: Partition([0]).defect(3) 0 sage: Partition([3]).defect(3) 1 sage: Partition([6]).defect(3) 2 sage: Partition([9]).defect(3) 3 sage: Partition([12]).defect(3) 4
- degree(e)¶
Return the
e
-th degree ofself
.The \(e\)-th degree of a partition \(\lambda\) is the sum of the \(e\)-th degrees of the standard tableaux of shape \(\lambda\). The \(e\)-th degree is the exponent of \(\Phi_e(q)\) in the Gram determinant of the Specht module for a semisimple Iwahori-Hecke algebra of type \(A\) with parameter \(q\).
INPUT:
e
– an integer \(e > 1\)
OUTPUT:
A non-negative integer.
EXAMPLES:
sage: Partition([4,3]).degree(2) 28 sage: Partition([4,3]).degree(3) 15 sage: Partition([4,3]).degree(4) 8 sage: Partition([4,3]).degree(5) 13 sage: Partition([4,3]).degree(6) 0 sage: Partition([4,3]).degree(7) 0
Therefore, the Gram determinant of \(S(5,3)\) when the Hecke parameter \(q\) is “generic” is
\[q^N \Phi_2(q)^{28} \Phi_3(q)^{15} \Phi_4(q)^8 \Phi_5(q)^{13}\]for some integer \(N\). Compare with
prime_degree()
.
- dimension(smaller=None, k=1)¶
Return the number of paths from the
smaller
partition to the partitionself
, where each step consists of adding a \(k\)-ribbon while keeping a partition.Note that a 1-ribbon is just a single cell, so this counts paths in the Young graph when \(k = 1\).
Note also that the default case (\(k = 1\) and
smaller = []
) gives the dimension of the irreducible representation of the symmetric group corresponding toself
.INPUT:
smaller
– a partition (default: an empty list[]
)\(k\) – a positive integer (default: 1)
OUTPUT:
The number of such paths
EXAMPLES:
Looks at the number of ways of getting from
[5,4]
to the empty partition, removing one cell at a time:sage: mu = Partition([5,4]) sage: mu.dimension() 42
Same, but removing one 3-ribbon at a time. Note that the 3-core of
mu
is empty:sage: mu.dimension(k=3) 3
The 2-core of
mu
is not the empty partition:sage: mu.dimension(k=2) 0
Indeed, the 2-core of
mu
is[1]
:sage: mu.dimension(Partition([1]),k=2) 2
ALGORITHM:
Depending on the parameters given, different simplifications occur. When \(k=1\) and
smaller
is empty, this function uses the hook formula. When \(k=1\) andsmaller
is not empty, it uses a formula from [ORV].When \(k \neq 1\), we first check that both
self
andsmaller
have the same \(k\)-core, then use the \(k\)-quotients and the same algorithm on each of the \(k\)-quotients.AUTHORS:
Paul-Olivier Dehaye (2011-06-07)
- dominated_partitions(rows=None)¶
Return a list of the partitions dominated by \(n\). If
rows
is specified, then it only returns the ones whose number of rows is at mostrows
.EXAMPLES:
sage: Partition([3,2,1]).dominated_partitions() [[3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] sage: Partition([3,2,1]).dominated_partitions(rows=3) [[3, 2, 1], [2, 2, 2]]
- dominates(p2)¶
Return
True
ifself
dominates the partitionp2
. Otherwise it returnsFalse
.EXAMPLES:
sage: p = Partition([3,2]) sage: p.dominates([3,1]) True sage: p.dominates([2,2]) True sage: p.dominates([2,1,1]) True sage: p.dominates([3,3]) False sage: p.dominates([4]) False sage: Partition([4]).dominates(p) False sage: Partition([]).dominates([1]) False sage: Partition([]).dominates([]) True sage: Partition([1]).dominates([]) True
- down()¶
Return a generator for partitions that can be obtained from
self
by removing a cell.EXAMPLES:
sage: [p for p in Partition([2,1,1]).down()] [[1, 1, 1], [2, 1]] sage: [p for p in Partition([3,2]).down()] [[2, 2], [3, 1]] sage: [p for p in Partition([3,2,1]).down()] [[2, 2, 1], [3, 1, 1], [3, 2]]
- down_list()¶
Return a list of the partitions that can be obtained from
self
by removing a cell.EXAMPLES:
sage: Partition([2,1,1]).down_list() [[1, 1, 1], [2, 1]] sage: Partition([3,2]).down_list() [[2, 2], [3, 1]] sage: Partition([3,2,1]).down_list() [[2, 2, 1], [3, 1, 1], [3, 2]] sage: Partition([]).down_list() #checks :trac:`11435` []
- dual_equivalence_graph(directed=False, coloring=None)¶
Return the dual equivalence graph of
self
.Two permutations \(p\) and \(q\) in the symmetric group \(S_n\) differ by an \(i\)-elementary dual equivalence (or dual Knuth) relation (where \(i\) is an integer with \(1 < i < n\)) when the following two conditions are satisfied:
In the one-line notation of the permutation \(p\), the letter \(i\) does not appear inbetween \(i-1\) and \(i+1\).
The permutation \(q\) is obtained from \(p\) by switching two of the three letters \(i-1, i, i+1\) (in its one-line notation) – namely, the leftmost and the rightmost one in order of their appearance in \(p\).
Notice that this is equivalent to the statement that the permutations \(p^{-1}\) and \(q^{-1}\) differ by an elementary Knuth equivalence at positions \(i-1, i, i+1\).
Two standard Young tableaux of shape \(\lambda\) differ by an \(i\)-elementary dual equivalence relation (of color \(i\)), if their reading words differ by an \(i\)-elementary dual equivalence relation.
The dual equivalence graph of the partition \(\lambda\) is the edge-colored graph whose vertices are the standard Young tableaux of shape \(\lambda\), and whose edges colored by \(i\) are given by the \(i\)-elementary dual equivalences.
INPUT:
directed
– (default:False
) whether to have the dual equivalence graph be directed (where we have a directed edge \(S \to T\) if \(i\) appears to the left of \(i+1\) in the reading word of \(T\); otherwise we have the directed edge \(T \to S\))coloring
– (optional) a function which sends each integer \(i > 1\) to a color (as a string, e.g.,'red'
or'black'
) to be used when visually representing the resulting graph using dot2tex; the default choice is2 -> 'red', 3 -> 'blue', 4 -> 'green', 5 -> 'purple', 6 -> 'brown', 7 -> 'orange', 8 -> 'yellow', anything greater than 8 -> 'black'
.
REFERENCES:
EXAMPLES:
sage: P = Partition([3,1,1]) sage: G = P.dual_equivalence_graph() sage: sorted(G.edges()) [([[1, 2, 3], [4], [5]], [[1, 2, 4], [3], [5]], 3), ([[1, 2, 4], [3], [5]], [[1, 2, 5], [3], [4]], 4), ([[1, 2, 4], [3], [5]], [[1, 3, 4], [2], [5]], 2), ([[1, 2, 5], [3], [4]], [[1, 3, 5], [2], [4]], 2), ([[1, 3, 4], [2], [5]], [[1, 3, 5], [2], [4]], 4), ([[1, 3, 5], [2], [4]], [[1, 4, 5], [2], [3]], 3)] sage: G = P.dual_equivalence_graph(directed=True) sage: sorted(G.edges()) [([[1, 2, 4], [3], [5]], [[1, 2, 3], [4], [5]], 3), ([[1, 2, 5], [3], [4]], [[1, 2, 4], [3], [5]], 4), ([[1, 3, 4], [2], [5]], [[1, 2, 4], [3], [5]], 2), ([[1, 3, 5], [2], [4]], [[1, 2, 5], [3], [4]], 2), ([[1, 3, 5], [2], [4]], [[1, 3, 4], [2], [5]], 4), ([[1, 4, 5], [2], [3]], [[1, 3, 5], [2], [4]], 3)]
- evaluation()¶
Return the evaluation of
self
.The commutative evaluation, often shortened to evaluation, of a word (we think of a partition as a word in \(\{1, 2, 3, \ldots\}\)) is its image in the free commutative monoid. In other words, this counts how many occurrences there are of each letter.
This is also is known as Parikh vector and abelianization and has the same output as
to_exp()
.EXAMPLES:
sage: Partition([4,3,1,1]).evaluation() [2, 0, 1, 1]
- ferrers_diagram()¶
Return the Ferrers diagram of
self
.EXAMPLES:
sage: mu = Partition([5,5,2,1]) sage: Partitions.options(diagram_str='*', convention="english") sage: print(mu.ferrers_diagram()) ***** ***** ** * sage: Partitions.options(diagram_str='#') sage: print(mu.ferrers_diagram()) ##### ##### ## # sage: Partitions.options.convention="french" sage: print(mu.ferrers_diagram()) # ## ##### ##### sage: print(Partition([]).ferrers_diagram()) - sage: Partitions.options(diagram_str='-') sage: print(Partition([]).ferrers_diagram()) (/) sage: Partitions.options._reset()
- frobenius_coordinates()¶
Return a pair of sequences of Frobenius coordinates aka beta numbers of the partition.
These are two strictly decreasing sequences of nonnegative integers of the same length.
EXAMPLES:
sage: Partition([]).frobenius_coordinates() ([], []) sage: Partition([1]).frobenius_coordinates() ([0], [0]) sage: Partition([3,3,3]).frobenius_coordinates() ([2, 1, 0], [2, 1, 0]) sage: Partition([9,1,1,1,1,1,1]).frobenius_coordinates() ([8], [6])
- frobenius_rank()¶
Return the Frobenius rank of the partition
self
.The Frobenius rank of a partition \(\lambda = (\lambda_1, \lambda_2, \lambda_3, \cdots)\) is defined to be the largest \(i\) such that \(\lambda_i \geq i\). In other words, it is the number of cells on the main diagonal of \(\lambda\). In yet other words, it is the size of the largest square fitting into the Young diagram of \(\lambda\).
EXAMPLES:
sage: Partition([]).frobenius_rank() 0 sage: Partition([1]).frobenius_rank() 1 sage: Partition([3,3,3]).frobenius_rank() 3 sage: Partition([9,1,1,1,1,1]).frobenius_rank() 1 sage: Partition([2,1,1,1,1,1]).frobenius_rank() 1 sage: Partition([2,2,1,1,1,1]).frobenius_rank() 2 sage: Partition([3,2]).frobenius_rank() 2 sage: Partition([3,2,2]).frobenius_rank() 2 sage: Partition([8,4,4,4,4]).frobenius_rank() 4 sage: Partition([8,4,1]).frobenius_rank() 2 sage: Partition([3,3,1]).frobenius_rank() 2
- from_kbounded_to_grassmannian(k)¶
Maps a \(k\)-bounded partition to a Grassmannian element in the affine Weyl group of type \(A_k^{(1)}\).
For details, see the documentation of the method
from_kbounded_to_reduced_word()
.EXAMPLES:
sage: p=Partition([2,1,1]) sage: p.from_kbounded_to_grassmannian(2) [-1 1 1] [-2 2 1] [-2 1 2] sage: p=Partition([]) sage: p.from_kbounded_to_grassmannian(2) [1 0 0] [0 1 0] [0 0 1]
- from_kbounded_to_reduced_word(k)¶
Maps a \(k\)-bounded partition to a reduced word for an element in the affine permutation group.
This uses the fact that there is a bijection between \(k\)-bounded partitions and \((k+1)\)-cores and an action of the affine nilCoxeter algebra of type \(A_k^{(1)}\) on \((k+1)\)-cores as described in [LM2006b].
EXAMPLES:
sage: p=Partition([2,1,1]) sage: p.from_kbounded_to_reduced_word(2) [2, 1, 2, 0] sage: p=Partition([3,1]) sage: p.from_kbounded_to_reduced_word(3) [3, 2, 1, 0] sage: p.from_kbounded_to_reduced_word(2) Traceback (most recent call last): ... ValueError: the partition must be 2-bounded sage: p=Partition([]) sage: p.from_kbounded_to_reduced_word(2) []
- garnir_tableau(*cell)¶
Return the Garnir tableau of shape
self
corresponding to the cellcell
. Ifcell
\(= (a,c)\) then \((a+1,c)\) must belong to the diagram ofself
.The Garnir tableaux play an important role in integral and non-semisimple representation theory because they determine the “straightening” rules for the Specht modules over an arbitrary ring.
The Garnir tableaux are the “first” non-standard tableaux which arise when you act by simple transpositions. If \((a,c)\) is a cell in the Young diagram of a partition, which is not at the bottom of its column, then the corresponding Garnir tableau has the integers \(1, 2, \ldots, n\) entered in order from left to right along the rows of the diagram up to the cell \((a,c-1)\), then along the cells \((a+1,1)\) to \((a+1,c)\), then \((a,c)\) until the end of row \(a\) and then continuing from left to right in the remaining positions. The examples below probably make this clearer!
Note
The function also sets
g._garnir_cell
, whereg
is the resulting Garnir tableau, equal tocell
which is used by some other functions.EXAMPLES:
sage: g = Partition([5,3,3,2]).garnir_tableau((0,2)); g.pp() 1 2 6 7 8 3 4 5 9 10 11 12 13 sage: g.is_row_strict(); g.is_column_strict() True False sage: Partition([5,3,3,2]).garnir_tableau(0,2).pp() 1 2 6 7 8 3 4 5 9 10 11 12 13 sage: Partition([5,3,3,2]).garnir_tableau(2,1).pp() 1 2 3 4 5 6 7 8 9 12 13 10 11 sage: Partition([5,3,3,2]).garnir_tableau(2,2).pp() Traceback (most recent call last): ... ValueError: (row+1, col) must be inside the diagram
See also
- generalized_pochhammer_symbol(a, alpha)¶
Return the generalized Pochhammer symbol \((a)_{self}^{(\alpha)}\). This is the product over all cells \((i,j)\) in
self
of \(a - (i-1) / \alpha + j - 1\).EXAMPLES:
sage: Partition([2,2]).generalized_pochhammer_symbol(2,1) 12
- get_part(i, default=0)¶
Return the \(i^{th}\) part of
self
, ordefault
if it does not exist.EXAMPLES:
sage: p = Partition([2,1]) sage: p.get_part(0), p.get_part(1), p.get_part(2) (2, 1, 0) sage: p.get_part(10,-1) -1 sage: Partition([]).get_part(0) 0
- has_k_rectangle(k)¶
Return
True
if the Ferrer’s diagram ofself
contains \(k-i+1\) rows (or more) of length \(i\) (exactly) for any \(i\) in \([1, k]\).This is mainly a helper function for
is_k_reducible()
andis_k_irreducible()
, the only difference between this function andis_k_reducible()
being that this function allows any partition as input whileis_k_reducible()
requires the input to be \(k\)-bounded.EXAMPLES:
The partition [1, 1, 1] has at least 2 rows of length 1:
sage: Partition([1, 1, 1]).has_k_rectangle(2) True
The partition [1, 1, 1] does not have 4 rows of length 1, 3 rows of length 2, 2 rows of length 3, nor 1 row of length 4:
sage: Partition([1, 1, 1]).has_k_rectangle(4) False
See also
- has_rectangle(h, w)¶
Return
True
if the Ferrer’s diagram ofself
hash
(or more) rows of lengthw
(exactly).INPUT:
h
– An integer \(h \geq 1\). The (minimum) height of the rectangle.w
– An integer \(w \geq 1\). The width of the rectangle.
EXAMPLES:
sage: Partition([3, 3, 3, 3]).has_rectangle(2, 3) True sage: Partition([3, 3]).has_rectangle(2, 3) True sage: Partition([4, 3]).has_rectangle(2, 3) False sage: Partition([3]).has_rectangle(2, 3) False
See also
- hook_length(i, j)¶
Return the length of the hook of cell \((i,j)\) in
self
.The (length of the) hook of cell \((i,j)\) of a partition \(\lambda\) is
\[\lambda_i + \lambda^{\prime}_j - i - j + 1\]where \(\lambda^{\prime}\) is the conjugate partition. In English convention, the hook length is the number of cells horizontally to the right and vertically below the cell \((i,j)\) (including that cell).
EXAMPLES:
sage: p = Partition([2,2,1]) sage: p.hook_length(0, 0) 4 sage: p.hook_length(0, 1) 2 sage: p.hook_length(2, 0) 1 sage: Partition([3,3]).hook_length(0, 0) 4 sage: cell = [0,0]; Partition([3,3]).hook_length(*cell) 4
- hook_lengths()¶
Return a tableau of shape
self
with the cells filled in with the hook lengths.In each cell, put the sum of one plus the number of cells horizontally to the right and vertically below the cell (the hook length).
For example, consider the partition
[3,2,1]
of 6 with Ferrers diagram:# # # # # #
When we fill in the cells with the hook lengths, we obtain:
5 3 1 3 1 1
EXAMPLES:
sage: Partition([2,2,1]).hook_lengths() [[4, 2], [3, 1], [1]] sage: Partition([3,3]).hook_lengths() [[4, 3, 2], [3, 2, 1]] sage: Partition([3,2,1]).hook_lengths() [[5, 3, 1], [3, 1], [1]] sage: Partition([2,2]).hook_lengths() [[3, 2], [2, 1]] sage: Partition([5]).hook_lengths() [[5, 4, 3, 2, 1]]
REFERENCES:
- hook_polynomial(q, t)¶
Return the two-variable hook polynomial.
EXAMPLES:
sage: R.<q,t> = PolynomialRing(QQ) sage: a = Partition([2,2]).hook_polynomial(q,t) sage: a == (1 - t)*(1 - q*t)*(1 - t^2)*(1 - q*t^2) True sage: a = Partition([3,2,1]).hook_polynomial(q,t) sage: a == (1 - t)^3*(1 - q*t^2)^2*(1 - q^2*t^3) True
- hook_product(a)¶
Return the Jack hook-product.
EXAMPLES:
sage: Partition([3,2,1]).hook_product(x) (2*x + 3)*(x + 2)^2 sage: Partition([2,2]).hook_product(x) 2*(x + 2)*(x + 1)
- hooks()¶
Return a sorted list of the hook lengths in
self
.EXAMPLES:
sage: Partition([3,2,1]).hooks() [5, 3, 3, 1, 1, 1]
- initial_column_tableau()¶
Return the initial column tableau of shape
self
.The initial column tableau of shape self is the standard tableau that has the numbers \(1\) to \(n\), where \(n\) is the
size()
ofself
, entered in order from top to bottom and then left to right down the columns ofself
.EXAMPLES:
sage: Partition([3,2]).initial_column_tableau() [[1, 3, 5], [2, 4]]
- initial_tableau()¶
Return the
standard tableau
which has the numbers \(1, 2, \ldots, n\) where \(n\) is thesize()
ofself
entered in order from left to right along the rows of each component, where the components are ordered from left to right.EXAMPLES:
sage: Partition([3,2,2]).initial_tableau() [[1, 2, 3], [4, 5], [6, 7]]
- inside_corners()¶
Return a list of the corners of the partition
self
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind.
The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners() [(0, 2), (1, 1), (2, 0)] sage: Partition([3,3,1]).corners() [(1, 2), (2, 0)] sage: Partition([]).corners() []
- inside_corners_residue(i, l)¶
Return a list of the corners of the partition
self
havingl
-residuei
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind. See
residue()
for the definition of thel
-residue.The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners_residue(0, 3) [(1, 1)] sage: Partition([3,2,1]).corners_residue(1, 3) [(2, 0)] sage: Partition([3,2,1]).corners_residue(2, 3) [(0, 2)]
- is_core(k)¶
Return
True
if the Partitionself
is ak
-core.A partition is said to be a `k`-core if it has no hooks of length \(k\). Equivalently, a partition is said to be a \(k\)-core if it is its own \(k\)-core (where the latter is defined as in
core()
).Visually, this can be checked by trying to remove border strips of size \(k\) from
self
. If this is not possible, thenself
is a \(k\)-core.EXAMPLES:
In the partition (2, 1), a hook length of 2 does not occur, but a hook length of 3 does:
sage: p = Partition([2, 1]) sage: p.is_core(2) True sage: p.is_core(3) False sage: q = Partition([12, 8, 5, 5, 2, 2, 1]) sage: q.is_core(4) False sage: q.is_core(5) True sage: q.is_core(0) True
- is_empty()¶
Return
True
ifself
is the empty partition.EXAMPLES:
sage: Partition([]).is_empty() True sage: Partition([2,1,1]).is_empty() False
- is_k_bounded(k)¶
Return
True
if the partitionself
is bounded byk
.EXAMPLES:
sage: Partition([4, 3, 1]).is_k_bounded(4) True sage: Partition([4, 3, 1]).is_k_bounded(7) True sage: Partition([4, 3, 1]).is_k_bounded(3) False
- is_k_irreducible(k)¶
Return
True
if the partitionself
isk
-irreducible.A \(k\)-bounded partition is \(k\)-irreducible if its Ferrer’s diagram does not contain \(k-i+1\) rows (or more) of length \(i\) (exactly) for every \(i \in [1, k]\).
(Also, a \(k\)-bounded partition is \(k\)-irreducible if and only if it is not \(k\)-reducible.)
EXAMPLES:
The partition [1, 1, 1] has at least 2 rows of length 1:
sage: Partition([1, 1, 1]).is_k_irreducible(2) False
The partition [1, 1, 1] does not have 4 rows of length 1, 3 rows of length 2, 2 rows of length 3, nor 1 row of length 4:
sage: Partition([1, 1, 1]).is_k_irreducible(4) True
See also
- is_k_reducible(k)¶
Return
True
if the partitionself
isk
-reducible.A \(k\)-bounded partition is \(k\)-reducible if its Ferrer’s diagram contains \(k-i+1\) rows (or more) of length \(i\) (exactly) for some \(i \in [1, k]\).
(Also, a \(k\)-bounded partition is \(k\)-reducible if and only if it is not \(k\)-irreducible.)
EXAMPLES:
The partition [1, 1, 1] has at least 2 rows of length 1:
sage: Partition([1, 1, 1]).is_k_reducible(2) True
The partition [1, 1, 1] does not have 4 rows of length 1, 3 rows of length 2, 2 rows of length 3, nor 1 row of length 4:
sage: Partition([1, 1, 1]).is_k_reducible(4) False
See also
- is_regular(e, multicharge=(0))¶
Return
True
is this is ane
-regular partition.A partition is \(e\)-regular if it does not have \(e\) equal non-zero parts.
EXAMPLES:
sage: Partition([4,3,3,3]).is_regular(2) False sage: Partition([4,3,3,3]).is_regular(3) False sage: Partition([4,3,3,3]).is_regular(4) True
- is_restricted(e, multicharge=(0))¶
Return
True
is this is ane
-restricted partition.An \(e\)-restricted partition is a partition such that the difference of consecutive parts is always strictly less than \(e\), where partitions are considered to have an infinite number of \(0\) parts. I.e., the last part must be strictly less than \(e\).
EXAMPLES:
sage: Partition([4,3,3,2]).is_restricted(2) False sage: Partition([4,3,3,2]).is_restricted(3) True sage: Partition([4,3,3,2]).is_restricted(4) True sage: Partition([4]).is_restricted(4) False
- is_symmetric()¶
Return
True
if the partitionself
equals its own transpose.EXAMPLES:
sage: Partition([2, 1]).is_symmetric() True sage: Partition([3, 1]).is_symmetric() False
- jacobi_trudi()¶
Return the Jacobi-Trudi matrix of
self
thought of as a skew partition. SeeSkewPartition.jacobi_trudi()
.EXAMPLES:
sage: part = Partition([3,2,1]) sage: jt = part.jacobi_trudi(); jt [h[3] h[1] 0] [h[4] h[2] h[]] [h[5] h[3] h[1]] sage: s = SymmetricFunctions(QQ).schur() sage: h = SymmetricFunctions(QQ).homogeneous() sage: h( s(part) ) h[3, 2, 1] - h[3, 3] - h[4, 1, 1] + h[5, 1] sage: jt.det() h[3, 2, 1] - h[3, 3] - h[4, 1, 1] + h[5, 1]
- k_atom(k)¶
Return a list of the standard tableaux of size
self.size()
whosek
-atom is equal toself
.EXAMPLES:
sage: p = Partition([3,2,1]) sage: p.k_atom(1) [] sage: p.k_atom(3) [[[1, 1, 1], [2, 2], [3]], [[1, 1, 1, 2], [2], [3]], [[1, 1, 1, 3], [2, 2]], [[1, 1, 1, 2, 3], [2]]] sage: Partition([3,2,1]).k_atom(4) [[[1, 1, 1], [2, 2], [3]], [[1, 1, 1, 3], [2, 2]]]
- k_boundary(k)¶
Return the skew partition formed by removing the cells of the
k
-interior, seek_interior()
.EXAMPLES:
sage: p = Partition([3,2,1]) sage: p.k_boundary(2) [3, 2, 1] / [2, 1] sage: p.k_boundary(3) [3, 2, 1] / [1] sage: p = Partition([12,8,5,5,2,2,1]) sage: p.k_boundary(4) [12, 8, 5, 5, 2, 2, 1] / [8, 5, 2, 2]
- k_column_lengths(k)¶
Return the
k
-column-shape of the partitionself
.This is the ‘column’ analog of
k_row_lengths()
.EXAMPLES:
sage: Partition([6, 1]).k_column_lengths(2) [1, 0, 0, 0, 1, 1] sage: Partition([4, 4, 4, 3, 2]).k_column_lengths(2) [1, 1, 1, 2]
- k_conjugate(k)¶
Return the
k
-conjugate ofself
.The \(k\)-conjugate is the partition that is given by the columns of the \(k\)-skew diagram of the partition.
We can also define the \(k\)-conjugate in the following way. Let \(P\) denote the bijection from \((k+1)\)-cores to \(k\)-bounded partitions. The \(k\)-conjugate of a \((k+1)\)-core \(\lambda\) is
\[\lambda^{(k)} = P^{-1}\left( (P(\lambda))^{\prime} \right).\]EXAMPLES:
sage: p = Partition([4,3,2,2,1,1]) sage: p.k_conjugate(4) [3, 2, 2, 1, 1, 1, 1, 1, 1]
- k_interior(k)¶
Return the partition consisting of the cells of
self
whose hook lengths are greater thank
.EXAMPLES:
sage: p = Partition([3,2,1]) sage: p.hook_lengths() [[5, 3, 1], [3, 1], [1]] sage: p.k_interior(2) [2, 1] sage: p.k_interior(3) [1] sage: p = Partition([]) sage: p.k_interior(3) []
- k_irreducible(k)¶
Return the partition with all \(r \times (k+1-r)\) rectangles removed.
If
self
is a \(k\)-bounded partition, then this method will return the partition where all rectangles of dimension \(r \times (k+1-r)\) for \(1 \leq r \leq k\) have been deleted.If
self
is not a \(k\)-bounded partition then the method will raise an error.INPUT:
k
– a non-negative integer
OUTPUT:
a partition
EXAMPLES:
sage: Partition([3,2,2,1,1,1]).k_irreducible(4) [3, 2, 2, 1, 1, 1] sage: Partition([3,2,2,1,1,1]).k_irreducible(3) [] sage: Partition([3,3,3,2,2,2,2,2,1,1,1,1]).k_irreducible(3) [2, 1]
- k_rim(k)¶
Return the
k
-rim ofself
as a list of integer coordinates.The \(k\)-rim of a partition is the “line between” (or “intersection of”) the \(k\)-boundary and the \(k\)-interior. (Section 2.3 of [HM2011])
It will be output as an ordered list of integer coordinates, where the origin is \((0, 0)\). It will start at the top-left of the \(k\)-rim (using French convention) and end at the bottom-right.
EXAMPLES:
Consider the partition (3, 1) split up into its 1-interior and 1-boundary:
The line shown in bold is the 1-rim, and that information is equivalent to the integer coordinates of the points that occur along that line:
sage: Partition([3, 1]).k_rim(1) [(3, 0), (2, 0), (2, 1), (1, 1), (0, 1), (0, 2)]
See also
- k_row_lengths(k)¶
Return the
k
-row-shape of the partitionself
.This is equivalent to taking the \(k\)-boundary of the partition and then returning the row-shape of that. We do not discard rows of length 0. (Section 2.2 of [LLMS2013])
EXAMPLES:
sage: Partition([6, 1]).k_row_lengths(2) [2, 1] sage: Partition([4, 4, 4, 3, 2]).k_row_lengths(2) [0, 1, 1, 1, 2]
- k_size(k)¶
Given a partition
self
and ak
, return the size of the \(k\)-boundary.This is the same as the length method
sage.combinat.core.Core.length()
of thesage.combinat.core.Core
object, with the exception that here we don’t requireself
to be a \(k+1\)-core.EXAMPLES:
sage: Partition([2, 1, 1]).k_size(1) 2 sage: Partition([2, 1, 1]).k_size(2) 3 sage: Partition([2, 1, 1]).k_size(3) 3 sage: Partition([2, 1, 1]).k_size(4) 4
See also
- k_skew(k)¶
Return the \(k\)-skew partition.
The \(k\)-skew diagram of a \(k\)-bounded partition is the skew diagram denoted \(\lambda/^k\) satisfying the conditions:
row \(i\) of \(\lambda/^k\) has length \(\lambda_i\),
no cell in \(\lambda/^k\) has hook-length exceeding \(k\),
every square above the diagram of \(\lambda/^k\) has hook length exceeding \(k\).
REFERENCES:
EXAMPLES:
sage: p = Partition([4,3,2,2,1,1]) sage: p.k_skew(4) [9, 5, 3, 2, 1, 1] / [5, 2, 1]
- k_split(k)¶
Return the
k
-split ofself
.EXAMPLES:
sage: Partition([4,3,2,1]).k_split(3) [] sage: Partition([4,3,2,1]).k_split(4) [[4], [3, 2], [1]] sage: Partition([4,3,2,1]).k_split(5) [[4, 3], [2, 1]] sage: Partition([4,3,2,1]).k_split(6) [[4, 3, 2], [1]] sage: Partition([4,3,2,1]).k_split(7) [[4, 3, 2, 1]] sage: Partition([4,3,2,1]).k_split(8) [[4, 3, 2, 1]]
- larger_lex(rhs)¶
Return
True
ifself
is larger thanrhs
in lexicographic order. Otherwise returnFalse
.EXAMPLES:
sage: p = Partition([3,2]) sage: p.larger_lex([3,1]) True sage: p.larger_lex([1,4]) True sage: p.larger_lex([3,2,1]) False sage: p.larger_lex([3]) True sage: p.larger_lex([5]) False sage: p.larger_lex([3,1,1,1,1,1,1,1]) True
- leg_cells(i, j)¶
Return the list of the cells of the leg of cell \((i,j)\) in
self
.The leg of cell \(c = (i,j)\) is defined to be the cells below \(c\) (in English convention).
The cell coordinates are zero-based, i. e., the northwesternmost cell is \((0,0)\).
INPUT:
i, j
– two integers
OUTPUT:
A list of pairs of integers
EXAMPLES:
sage: Partition([4,4,3,1]).leg_cells(1,1) [(2, 1)] sage: Partition([4,4,3,1]).leg_cells(0,1) [(1, 1), (2, 1)] sage: Partition([]).leg_cells(0,0) Traceback (most recent call last): ... ValueError: The cell is not in the diagram
- leg_length(i, j)¶
Return the length of the leg of cell \((i,j)\) in
self
.The leg of cell \(c = (i,j)\) is defined to be the cells below \(c\) (in English convention).
The cell coordinates are zero-based, i. e., the northwesternmost cell is \((0,0)\).
INPUT:
i, j
– two integers
OUTPUT:
An integer or a
ValueError
EXAMPLES:
sage: p = Partition([2,2,1]) sage: p.leg_length(0, 0) 2 sage: p.leg_length(0,1) 1 sage: p.leg_length(2,0) 0 sage: Partition([3,3]).leg_length(0, 0) 1 sage: cell = [0,0]; Partition([3,3]).leg_length(*cell) 1
- leg_lengths(flat=False)¶
Return a tableau of shape
self
with each cell filled in with its leg length. The optional boolean parameterflat
provides the option of returning a flat list.EXAMPLES:
sage: Partition([2,2,1]).leg_lengths() [[2, 1], [1, 0], [0]] sage: Partition([2,2,1]).leg_lengths(flat=True) [2, 1, 1, 0, 0] sage: Partition([3,3]).leg_lengths() [[1, 1, 1], [0, 0, 0]] sage: Partition([3,3]).leg_lengths(flat=True) [1, 1, 1, 0, 0, 0]
- length()¶
Return the number of parts in
self
.EXAMPLES:
sage: Partition([3,2]).length() 2 sage: Partition([2,2,1]).length() 3 sage: Partition([]).length() 0
- level()¶
Return the level of
self
, which is always 1.This method exists only for compatibility with
PartitionTuples
.EXAMPLES:
sage: Partition([4,3,2]).level() 1
- lower_hook(i, j, alpha)¶
Return the lower hook length of the cell \((i,j)\) in
self
. Whenalpha = 1
, this is just the normal hook length.The lower hook length of a cell \((i,j)\) in a partition \(\kappa\) is defined by
\[h_*^\kappa(i,j) = \kappa^\prime_j - i + 1 + \alpha(\kappa_i - j).\]EXAMPLES:
sage: p = Partition([2,1]) sage: p.lower_hook(0,0,1) 3 sage: p.hook_length(0,0) 3 sage: [ p.lower_hook(i,j,x) for i,j in p.cells() ] [x + 2, 1, 1]
- lower_hook_lengths(alpha)¶
Return a tableau of shape
self
with the cells filled in with the lower hook lengths. Whenalpha = 1
, these are just the normal hook lengths.The lower hook length of a cell \((i,j)\) in a partition \(\kappa\) is defined by
\[h_*^\kappa(i,j) = \kappa^\prime_j - i + 1 + \alpha(\kappa_i - j).\]EXAMPLES:
sage: Partition([3,2,1]).lower_hook_lengths(x) [[2*x + 3, x + 2, 1], [x + 2, 1], [1]] sage: Partition([3,2,1]).lower_hook_lengths(1) [[5, 3, 1], [3, 1], [1]] sage: Partition([3,2,1]).hook_lengths() [[5, 3, 1], [3, 1], [1]]
- next()¶
Return the partition that lexicographically follows
self
, of the same size. Ifself
is the last partition, then returnFalse
.EXAMPLES:
sage: next(Partition([4])) [3, 1] sage: next(Partition([1,1,1,1])) False
- next_within_bounds(min=[], max=None, partition_type=None)¶
Get the next partition lexicographically that contains
min
and is contained inmax
.INPUT:
min
– (default[]
, the empty partition) The ‘minimum partition’ thatnext_within_bounds(self)
must contain.max
– (defaultNone
) The ‘maximum partition’ thatnext_within_bounds(self)
must be contained in. If set toNone
, then there is no restriction.partition_type
– (defaultNone
) The type of partitions allowed. For example, ‘strict’ for strictly decreasing partitions, orNone
to allow any valid partition.
EXAMPLES:
sage: m = [1, 1] sage: M = [3, 2, 1] sage: Partition([1, 1]).next_within_bounds(min=m, max=M) [1, 1, 1] sage: Partition([1, 1, 1]).next_within_bounds(min=m, max=M) [2, 1] sage: Partition([2, 1]).next_within_bounds(min=m, max=M) [2, 1, 1] sage: Partition([2, 1, 1]).next_within_bounds(min=m, max=M) [2, 2] sage: Partition([2, 2]).next_within_bounds(min=m, max=M) [2, 2, 1] sage: Partition([2, 2, 1]).next_within_bounds(min=m, max=M) [3, 1] sage: Partition([3, 1]).next_within_bounds(min=m, max=M) [3, 1, 1] sage: Partition([3, 1, 1]).next_within_bounds(min=m, max=M) [3, 2] sage: Partition([3, 2]).next_within_bounds(min=m, max=M) [3, 2, 1] sage: Partition([3, 2, 1]).next_within_bounds(min=m, max=M) == None True
See also
- outer_rim()¶
Return the outer rim of
self
.The outer rim of a partition \(\lambda\) is defined as the cells which do not belong to \(\lambda\) and which are adjacent to cells in \(\lambda\).
EXAMPLES:
The outer rim of the partition \([4,1]\) consists of the cells marked with
#
below:****# *#### ##
sage: Partition([4,1]).outer_rim() [(2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)] sage: Partition([2,2,1]).outer_rim() [(3, 0), (3, 1), (2, 1), (2, 2), (1, 2), (0, 2)] sage: Partition([2,2]).outer_rim() [(2, 0), (2, 1), (2, 2), (1, 2), (0, 2)] sage: Partition([6,3,3,1,1]).outer_rim() [(5, 0), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 4), (1, 5), (1, 6), (0, 6)] sage: Partition([]).outer_rim() [(0, 0)]
- outline(variable=None)¶
Return the outline of the partition
self
.This is a piecewise linear function, normalized so that the area under the partition
[1]
is 2.INPUT:
variable – a variable (default:
'x'
in the symbolic ring)
EXAMPLES:
sage: [Partition([5,4]).outline()(x=i) for i in range(-10,11)] [10, 9, 8, 7, 6, 5, 6, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 10] sage: Partition([]).outline() abs(x) sage: Partition([1]).outline() abs(x + 1) + abs(x - 1) - abs(x) sage: y=sage.symbolic.ring.var("y") sage: Partition([6,5,1]).outline(variable=y) abs(y + 6) - abs(y + 5) + abs(y + 4) - abs(y + 3) + abs(y - 1) - abs(y - 2) + abs(y - 3)
- outside_corners()¶
Return a list of the outside corners of the partition
self
.An outside corner (also called a cocorner) of a partition \(\lambda\) is a cell on \(\ZZ^2\) which does not belong to the Young diagram of \(\lambda\) but can be added to this Young diagram to still form a straight-shape Young diagram.
The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([2,2,1]).outside_corners() [(0, 2), (2, 1), (3, 0)] sage: Partition([2,2]).outside_corners() [(0, 2), (2, 0)] sage: Partition([6,3,3,1,1,1]).outside_corners() [(0, 6), (1, 3), (3, 1), (6, 0)] sage: Partition([]).outside_corners() [(0, 0)]
- outside_corners_residue(i, l)¶
Return a list of the outside corners of the partition
self
havingl
-residuei
.An outside corner (also called a cocorner) of a partition \(\lambda\) is a cell on \(\ZZ^2\) which does not belong to the Young diagram of \(\lambda\) but can be added to this Young diagram to still form a straight-shape Young diagram. See
residue()
for the definition of thel
-residue.The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).outside_corners_residue(0, 3) [(0, 3), (3, 0)] sage: Partition([3,2,1]).outside_corners_residue(1, 3) [(1, 2)] sage: Partition([3,2,1]).outside_corners_residue(2, 3) [(2, 1)]
- plancherel_measure()¶
Return the probability of
self
under the Plancherel probability measure on partitions of the same size.This probability distribution comes from the uniform distribution on permutations via the Robinson-Schensted correspondence.
See Wikipedia article Plancherel_measure and
Partitions_n.random_element_plancherel()
.EXAMPLES:
sage: Partition([]).plancherel_measure() 1 sage: Partition([1]).plancherel_measure() 1 sage: Partition([2]).plancherel_measure() 1/2 sage: [mu.plancherel_measure() for mu in Partitions(3)] [1/6, 2/3, 1/6] sage: Partition([5,4]).plancherel_measure() 7/1440
- power(k)¶
Return the cycle type of the \(k\)-th power of any permutation with cycle type
self
(thus describes the powermap of symmetric groups).Equivalent to GAP’s
PowerPartition
.EXAMPLES:
sage: p = Partition([5,3]) sage: p.power(1) [5, 3] sage: p.power(2) [5, 3] sage: p.power(3) [5, 1, 1, 1] sage: p.power(4) [5, 3]
Now let us compare this to the power map on \(S_8\):
sage: G = SymmetricGroup(8) sage: g = G([(1,2,3,4,5),(6,7,8)]) sage: g (1,2,3,4,5)(6,7,8) sage: g^2 (1,3,5,2,4)(6,8,7) sage: g^3 (1,4,2,5,3) sage: g^4 (1,5,4,3,2)(6,7,8)
sage: Partition([3,2,1]).power(3) [2, 1, 1, 1, 1]
- pp()¶
Print the Ferrers diagram.
See
ferrers_diagram()
for more on the Ferrers diagram.EXAMPLES:
sage: Partition([5,5,2,1]).pp() ***** ***** ** * sage: Partitions.options.convention='French' sage: Partition([5,5,2,1]).pp() * ** ***** ***** sage: Partitions.options._reset()
- prime_degree(p)¶
Return the prime degree for the prime integer``p`` for
self
.INPUT:
p
– a prime integer
OUTPUT:
A non-negative integer
The degree of a partition \(\lambda\) is the sum of the \(e\)-
degree()
of the standard tableaux of shape \(\lambda\), for \(e\) a power of the prime \(p\). The prime degree gives the exponent of \(p\) in the Gram determinant of the integral Specht module of the symmetric group.EXAMPLES:
sage: Partition([4,3]).prime_degree(2) 36 sage: Partition([4,3]).prime_degree(3) 15 sage: Partition([4,3]).prime_degree(5) 13 sage: Partition([4,3]).prime_degree(7) 0
Therefore, the Gram determinant of \(S(5,3)\) when \(q = 1\) is \(2^{36} 3^{15} 5^{13}\). Compare with
degree()
.
- quotient(length)¶
Return the quotient of the partition – in the literature the quotient is commonly referred to as the \(k\)-quotient, \(p\)-quotient, \(r\)-quotient, … .
The \(r\)-quotient of a partition \(\lambda\) is a list of \(r\) partitions (labelled from \(0\) to \(r-1\)), constructed in the following way. Label each cell in the Young diagram of \(\lambda\) with its content modulo \(r\). Let \(R_i\) be the set of rows ending in a cell labelled \(i\), and \(C_i\) be the set of columns ending in a cell labelled \(i\). Then the \(j\)-th component of the quotient of \(\lambda\) is the partition defined by intersecting \(R_j\) with \(C_{j+1}\). (See Theorem 2.7.37 in [JK1981].)
EXAMPLES:
sage: Partition([7,7,5,3,3,3,1]).quotient(3) ([2], [1], [2, 2, 2])
- reading_tableau()¶
Return the RSK recording tableau of the reading word of the (standard) tableau \(T\) labeled down (in English convention) each column to the shape of
self
.For an example of the tableau \(T\), consider the partition \(\lambda = (3,2,1)\), then we have:
1 4 6 2 5 3
For more, see
RSK()
.EXAMPLES:
sage: Partition([3,2,1]).reading_tableau() [[1, 3, 6], [2, 5], [4]]
- removable_cells()¶
Return a list of the corners of the partition
self
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind.
The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners() [(0, 2), (1, 1), (2, 0)] sage: Partition([3,3,1]).corners() [(1, 2), (2, 0)] sage: Partition([]).corners() []
- removable_cells_residue(i, l)¶
Return a list of the corners of the partition
self
havingl
-residuei
.A corner of a partition \(\lambda\) is a cell of the Young diagram of \(\lambda\) which can be removed from the Young diagram while still leaving a straight shape behind. See
residue()
for the definition of thel
-residue.The entries of the list returned are pairs of the form \((i,j)\), where \(i\) and \(j\) are the coordinates of the respective corner. The coordinates are counted from \(0\).
EXAMPLES:
sage: Partition([3,2,1]).corners_residue(0, 3) [(1, 1)] sage: Partition([3,2,1]).corners_residue(1, 3) [(2, 0)] sage: Partition([3,2,1]).corners_residue(2, 3) [(0, 2)]
- remove_cell(i, j=None)¶
Return the partition obtained by removing a cell at the end of row
i
ofself
.EXAMPLES:
sage: Partition([2,2]).remove_cell(1) [2, 1] sage: Partition([2,2,1]).remove_cell(2) [2, 2] sage: #Partition([2,2]).remove_cell(0)
sage: Partition([2,2]).remove_cell(1,1) [2, 1] sage: #Partition([2,2]).remove_cell(1,0)
- remove_horizontal_border_strip(k)¶
Return the partitions obtained from
self
by removing an horizontal border strip of lengthk
.EXAMPLES:
sage: Partition([5,3,1]).remove_horizontal_border_strip(0).list() [[5, 3, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(1).list() [[5, 3], [5, 2, 1], [4, 3, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(2).list() [[5, 2], [5, 1, 1], [4, 3], [4, 2, 1], [3, 3, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(3).list() [[5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(4).list() [[4, 1], [3, 2], [3, 1, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(5).list() [[3, 1]] sage: Partition([5,3,1]).remove_horizontal_border_strip(6).list() []
The result is returned as an instance of
Partitions_with_constraints
:sage: Partition([5,3,1]).remove_horizontal_border_strip(5) The subpartitions of [5, 3, 1] obtained by removing an horizontal border strip of length 5
- residue(r, c, l)¶
Return the
l
-residue of the cell at rowr
and columnc
.The \(\ell\)-residue of a cell is \(c - r\) modulo \(\ell\).
This does not strictly depend upon the partition, however, this method is included because it is often useful in the context of partitions.
EXAMPLES:
sage: Partition([2,1]).residue(1, 0, 3) 2
- rim()¶
Return the rim of
self
.The rim of a partition \(\lambda\) is defined as the cells which belong to \(\lambda\) and which are adjacent to cells not in \(\lambda\).
EXAMPLES:
The rim of the partition \([5,5,2,1]\) consists of the cells marked with
#
below:****# *#### ## # sage: Partition([5,5,2,1]).rim() [(3, 0), (2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)] sage: Partition([2,2,1]).rim() [(2, 0), (1, 0), (1, 1), (0, 1)] sage: Partition([2,2]).rim() [(1, 0), (1, 1), (0, 1)] sage: Partition([6,3,3,1,1]).rim() [(4, 0), (3, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4), (0, 5)] sage: Partition([]).rim() []
- row_standard_tableaux()¶
Return the
row standard tableaux
of shapeself
.EXAMPLES:
sage: Partition([3,2,2,1]).row_standard_tableaux() Row standard tableaux of shape [3, 2, 2, 1]
- sign()¶
Return the sign of any permutation with cycle type
self
.This function corresponds to a homomorphism from the symmetric group \(S_n\) into the cyclic group of order 2, whose kernel is exactly the alternating group \(A_n\). Partitions of sign \(1\) are called even partitions while partitions of sign \(-1\) are called odd.
EXAMPLES:
sage: Partition([5,3]).sign() 1 sage: Partition([5,2]).sign() -1
Zolotarev’s lemma states that the Legendre symbol \(\left(\frac{a}{p}\right)\) for an integer \(a \pmod p\) (\(p\) a prime number), can be computed as sign(p_a), where sign denotes the sign of a permutation and p_a the permutation of the residue classes \(\pmod p\) induced by modular multiplication by \(a\), provided \(p\) does not divide \(a\).
We verify this in some examples.
sage: F = GF(11) sage: a = F.multiplicative_generator();a 2 sage: plist = [int(a*F(x)) for x in range(1,11)]; plist [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
This corresponds to the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6) (acting the set \(\{1,2,...,10\}\)) and to the partition [10].
sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)') sage: p.sign() -1 sage: Partition([10]).sign() -1 sage: kronecker_symbol(11,2) -1
Now replace \(2\) by \(3\):
sage: plist = [int(F(3*x)) for x in range(1,11)]; plist [3, 6, 9, 1, 4, 7, 10, 2, 5, 8] sage: list(range(1, 11)) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sage: p = PermutationGroupElement('(3,4,8,7,9)') sage: p.sign() 1 sage: kronecker_symbol(3,11) 1 sage: Partition([5,1,1,1,1,1]).sign() 1
In both cases, Zolotarev holds.
REFERENCES:
- size()¶
Return the size of
self
.EXAMPLES:
sage: Partition([2,2]).size() 4 sage: Partition([3,2,1]).size() 6
- standard_tableaux()¶
Return the
standard tableaux
of shapeself
.EXAMPLES:
sage: Partition([3,2,2,1]).standard_tableaux() Standard tableaux of shape [3, 2, 2, 1]
- suter_diagonal_slide(n, exp=1)¶
Return the image of
self
in \(Y_n\) under Suter’s diagonal slide \(\sigma_n\), where the notations used are those defined in [Sut2002].The set \(Y_n\) is defined as the set of all partitions \(\lambda\) such that the hook length of the \((0, 0)\)-cell (i.e. the northwestern most cell in English notation) of \(\lambda\) is less than \(n\), including the empty partition.
The map \(\sigma_n\) sends a partition (with non-zero entries) \((\lambda_1, \lambda_2, \ldots, \lambda_m) \in Y_n\) to the partition \((\lambda_2 + 1, \lambda_3 + 1, \ldots, \lambda_m + 1, \underbrace{1, 1, \ldots, 1}_{n - m - \lambda_1\text{ ones}})\). In other words, it pads the partition with trailing zeroes until it has length \(n - \lambda_1\), then removes its first part, and finally adds \(1\) to each part.
By Theorem 2.1 of [Sut2002], the dihedral group \(D_n\) with \(2n\) elements acts on \(Y_n\) by letting the primitive rotation act as \(\sigma_n\) and the reflection act as conjugation of partitions (
conjugate()
). This action is faithful if \(n \geq 3\).INPUT:
n
– nonnegative integerexp
– (default: 1) how many times \(\sigma_n\) should be applied
OUTPUT:
The result of applying Suter’s diagonal slide \(\sigma_n\) to
self
, assuming thatself
lies in \(Y_n\). If the optional argumentexp
is set, then the slide \(\sigma_n\) is applied not just once, butexp
times (note thatexp
is allowed to be negative, since the slide has finite order).EXAMPLES:
sage: Partition([5,4,1]).suter_diagonal_slide(8) [5, 2] sage: Partition([5,4,1]).suter_diagonal_slide(9) [5, 2, 1] sage: Partition([]).suter_diagonal_slide(7) [1, 1, 1, 1, 1, 1] sage: Partition([]).suter_diagonal_slide(1) [] sage: Partition([]).suter_diagonal_slide(7, exp=-1) [6] sage: Partition([]).suter_diagonal_slide(1, exp=-1) [] sage: P7 = Partitions(7) sage: all( p == p.suter_diagonal_slide(9, exp=-1).suter_diagonal_slide(9) ....: for p in P7 ) True sage: all( p == p.suter_diagonal_slide(9, exp=3) ....: .suter_diagonal_slide(9, exp=3) ....: .suter_diagonal_slide(9, exp=3) ....: for p in P7 ) True sage: all( p == p.suter_diagonal_slide(9, exp=6) ....: .suter_diagonal_slide(9, exp=6) ....: .suter_diagonal_slide(9, exp=6) ....: for p in P7 ) True sage: all( p == p.suter_diagonal_slide(9, exp=-1) ....: .suter_diagonal_slide(9, exp=1) ....: for p in P7 ) True
Check of the assertion in [Sut2002] that \(\sigma_n\bigl( \sigma_n( \lambda^{\prime})^{\prime} \bigr) = \lambda\):
sage: all( p.suter_diagonal_slide(8).conjugate() ....: == p.conjugate().suter_diagonal_slide(8, exp=-1) ....: for p in P7 ) True
Check of Claim 1 in [Sut2002]:
sage: P5 = Partitions(5) sage: all( all( (p.suter_diagonal_slide(6) in q.suter_diagonal_slide(6).down()) ....: or (q.suter_diagonal_slide(6) in p.suter_diagonal_slide(6).down()) ....: for p in q.down() ) ....: for q in P5 ) True
- t_completion(t)¶
Return the
t
-completion of the partitionself
.If \(\lambda = (\lambda_1, \lambda_2, \lambda_3, \ldots)\) is a partition and \(t\) is an integer greater or equal to \(\left\lvert \lambda \right\rvert + \lambda_1\), then the \(t\)-completion of \(\lambda\) is defined as the partition \((t - \left\lvert \lambda \right\rvert, \lambda_1, \lambda_2, \lambda_3, \ldots)\) of \(t\). This partition is denoted by \(\lambda[t]\) in [BOR2009], by \(\lambda_{[t]}\) in [BdVO2012], and by \(\lambda(t)\) in [CO2010].
EXAMPLES:
sage: Partition([]).t_completion(0) [] sage: Partition([]).t_completion(1) [1] sage: Partition([]).t_completion(2) [2] sage: Partition([]).t_completion(3) [3] sage: Partition([2, 1]).t_completion(5) [2, 2, 1] sage: Partition([2, 1]).t_completion(6) [3, 2, 1] sage: Partition([4, 2, 2, 1]).t_completion(13) [4, 4, 2, 2, 1] sage: Partition([4, 2, 2, 1]).t_completion(19) [10, 4, 2, 2, 1] sage: Partition([4, 2, 2, 1]).t_completion(10) Traceback (most recent call last): ... ValueError: 10-completion is not defined sage: Partition([4, 2, 2, 1]).t_completion(5) Traceback (most recent call last): ... ValueError: 5-completion is not defined
- to_core(k)¶
Maps the \(k\)-bounded partition
self
to its corresponding \(k+1\)-core.See also
k_skew()
.EXAMPLES:
sage: p = Partition([4,3,2,2,1,1]) sage: c = p.to_core(4); c [9, 5, 3, 2, 1, 1] sage: type(c) <class 'sage.combinat.core.Cores_length_with_category.element_class'> sage: c.to_bounded_partition() == p True
- to_dyck_word(n=None)¶
Return the
n
-Dyck word whose corresponding partition isself
(or, ifn
is not specified, the \(n\)-Dyck word with smallest \(n\) to satisfy this property).If \(w\) is an \(n\)-Dyck word (that is, a Dyck word with \(n\) open symbols and \(n\) close symbols), then the Dyck path corresponding to \(w\) can be regarded as a lattice path in the northeastern half of an \(n \times n\)-square. The region to the northeast of this Dyck path can be regarded as a partition. It is called the partition corresponding to the Dyck word \(w\). (See
to_partition()
.)For every partition \(\lambda\) and every nonnegative integer \(n\), there exists at most one \(n\)-Dyck word \(w\) such that the partition corresponding to \(w\) is \(\lambda\) (in fact, such \(w\) exists if and only if \(\lambda_i + i \leq n\) for every \(i\), where \(\lambda\) is written in the form \((\lambda_1, \lambda_2, \ldots, \lambda_k)\) with \(\lambda_k > 0\)). This method computes this \(w\) for a given \(\lambda\) and \(n\). If \(n\) is not specified, this method computes the \(w\) for the smallest possible \(n\) for which such an \(w\) exists. (The minimality of \(n\) means that the partition demarcated by the Dyck path touches the diagonal.)
EXAMPLES:
sage: Partition([2,2]).to_dyck_word() [1, 1, 0, 0, 1, 1, 0, 0] sage: Partition([2,2]).to_dyck_word(4) [1, 1, 0, 0, 1, 1, 0, 0] sage: Partition([2,2]).to_dyck_word(5) [1, 1, 1, 0, 0, 1, 1, 0, 0, 0] sage: Partition([6,3,1]).to_dyck_word() [1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0] sage: Partition([]).to_dyck_word() [] sage: Partition([]).to_dyck_word(3) [1, 1, 1, 0, 0, 0]
The partition corresponding to
self.dyck_word()
isself
indeed:sage: all( p.to_dyck_word().to_partition() == p ....: for p in Partitions(5) ) True
- to_exp(k=0)¶
Return a list of the multiplicities of the parts of a partition. Use the optional parameter
k
to get a return list of length at leastk
.EXAMPLES:
sage: Partition([3,2,2,1]).to_exp() [1, 2, 1] sage: Partition([3,2,2,1]).to_exp(5) [1, 2, 1, 0, 0]
- to_exp_dict()¶
Return a dictionary containing the multiplicities of the parts of
self
.EXAMPLES:
sage: p = Partition([4,2,2,1]) sage: d = p.to_exp_dict() sage: d[4] 1 sage: d[2] 2 sage: d[1] 1 sage: 5 in d False
- to_list()¶
Return
self
as a list.EXAMPLES:
sage: p = Partition([2,1]).to_list(); p [2, 1] sage: type(p) <... 'list'>
- top_garnir_tableau(e, cell)¶
Return the most dominant standard tableau which dominates the corresponding Garnir tableau and has the same
e
-residue.The Garnir tableau play an important role in integral and non-semisimple representation theory because they determine the “straightening” rules for the Specht modules. The top Garnir tableaux arise in the graded representation theory of the symmetric groups and higher level Hecke algebras. They were introduced in [KMR2012].
If the Garnir node is
cell=(r,c)
and \(m\) and \(M\) are the entries in the cells(r,c)
and(r+1,c)
, respectively, in the initial tableau then the tope
-Garnir tableau is obtained by inserting the numbers \(m, m+1, \ldots, M\) in order from left to right first in the cells in rowr+1
which are not in thee
-Garnir belt, then in the cell in rowsr
andr+1
which are in the Garnir belt and then, finally, in the remaining cells in rowr
which are not in the Garnir belt. All other entries in the tableau remain unchanged.If
e = 0
, or if there are noe
-bricks in either rowr
orr+1
, then the top Garnir tableau is the corresponding Garnir tableau.EXAMPLES:
sage: Partition([5,4,3,2]).top_garnir_tableau(2,(0,2)).pp() 1 2 4 5 8 3 6 7 9 10 11 12 13 14 sage: Partition([5,4,3,2]).top_garnir_tableau(3,(0,2)).pp() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 sage: Partition([5,4,3,2]).top_garnir_tableau(4,(0,2)).pp() 1 2 6 7 8 3 4 5 9 10 11 12 13 14 sage: Partition([5,4,3,2]).top_garnir_tableau(0,(0,2)).pp() 1 2 6 7 8 3 4 5 9 10 11 12 13 14
REFERENCES:
- up()¶
Return a generator for partitions that can be obtained from
self
by adding a cell.EXAMPLES:
sage: list(Partition([2,1,1]).up()) [[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]] sage: list(Partition([3,2]).up()) [[4, 2], [3, 3], [3, 2, 1]] sage: [p for p in Partition([]).up()] [[1]]
- up_list()¶
Return a list of the partitions that can be formed from
self
by adding a cell.EXAMPLES:
sage: Partition([2,1,1]).up_list() [[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]] sage: Partition([3,2]).up_list() [[4, 2], [3, 3], [3, 2, 1]] sage: Partition([]).up_list() [[1]]
- upper_hook(i, j, alpha)¶
Return the upper hook length of the cell \((i,j)\) in
self
. Whenalpha = 1
, this is just the normal hook length.The upper hook length of a cell \((i,j)\) in a partition \(\kappa\) is defined by
\[h^*_\kappa(i,j) = \kappa^\prime_j - i + \alpha(\kappa_i - j + 1).\]EXAMPLES:
sage: p = Partition([2,1]) sage: p.upper_hook(0,0,1) 3 sage: p.hook_length(0,0) 3 sage: [ p.upper_hook(i,j,x) for i,j in p.cells() ] [2*x + 1, x, x]
- upper_hook_lengths(alpha)¶
Return a tableau of shape
self
with the cells filled in with the upper hook lengths. Whenalpha = 1
, these are just the normal hook lengths.The upper hook length of a cell \((i,j)\) in a partition \(\kappa\) is defined by
\[h^*_\kappa(i,j) = \kappa^\prime_j - i + \alpha(\kappa_i - j + 1).\]EXAMPLES:
sage: Partition([3,2,1]).upper_hook_lengths(x) [[3*x + 2, 2*x + 1, x], [2*x + 1, x], [x]] sage: Partition([3,2,1]).upper_hook_lengths(1) [[5, 3, 1], [3, 1], [1]] sage: Partition([3,2,1]).hook_lengths() [[5, 3, 1], [3, 1], [1]]
- weighted_size()¶
Return the weighted size of
self
.The weighted size of a partition \(\lambda\) is
\[\sum_i i \cdot \lambda_i,\]where \(\lambda = (\lambda_0, \lambda_1, \lambda_2, \cdots )\).
This also the sum of the leg length of every cell in \(\lambda\), or
\[\sum_i \binom{\lambda^{\prime}_i}{2}\]where \(\lambda^{\prime}\) is the conjugate partition of \(\lambda\).
EXAMPLES:
sage: Partition([2,2]).weighted_size() 2 sage: Partition([3,3,3]).weighted_size() 9 sage: Partition([5,2]).weighted_size() 2 sage: Partition([]).weighted_size() 0
- young_subgroup()¶
Return the corresponding Young, or parabolic, subgroup of the symmetric group.
The Young subgroup of a partition \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_{\ell})\) of \(n\) is the group:
\[S_{\lambda_1} \times S_{\lambda_2} \times \cdots \times S_{\lambda_{\ell}}\]embedded into \(S_n\) in the standard way (i.e., the \(S_{\lambda_i}\) factor acts on the numbers from \(\lambda_1 + \lambda_2 + \cdots + \lambda_{i-1} + 1\) to \(\lambda_1 + \lambda_2 + \cdots + \lambda_i\)).
EXAMPLES:
sage: Partition([4,2]).young_subgroup() Permutation Group with generators [(), (5,6), (3,4), (2,3), (1,2)]
- young_subgroup_generators()¶
Return an indexing set for the generators of the corresponding Young subgroup. Here the generators correspond to the simple adjacent transpositions \(s_i = (i \; i+1)\).
EXAMPLES:
sage: Partition([4,2]).young_subgroup_generators() [1, 2, 3, 5] sage: Partition([1,1,1]).young_subgroup_generators() [] sage: Partition([2,2]).young_subgroup_generators() [1, 3]
See also
- zero_one_sequence()¶
Compute the finite \(0-1\) sequence of the partition.
The full \(0-1\) sequence is the sequence (infinite in both directions) indicating the steps taken when following the outer rim of the diagram of the partition. We use the convention that in English convention, a 1 corresponds to an East step, and a 0 corresponds to a North step.
Note that every full \(0-1\) sequence starts with infinitely many 0’s and ends with infinitely many 1’s.
One place where these arise is in the affine symmetric group where one takes an affine permutation \(w\) and every \(i\) such that \(w(i) \leq 0\) corresponds to a 1 and \(w(i) > 0\) corresponds to a 0. See pages 24-25 of [LLMSSZ2013] for connections to affine Grassmannian elements (note there they use the French convention for their partitions).
These are also known as path sequences, Maya diagrams, plus-minus diagrams, Comet code [Sta-EC2], among others.
OUTPUT:
The finite \(0-1\) sequence is obtained from the full \(0-1\) sequence by omitting all heading 0’s and trailing 1’s. The output sequence is finite, starts with a 1 and ends with a 0 (unless it is empty, for the empty partition). Its length is the sum of the first part of the partition with the length of the partition.
EXAMPLES:
sage: Partition([5,4]).zero_one_sequence() [1, 1, 1, 1, 0, 1, 0] sage: Partition([]).zero_one_sequence() [] sage: Partition([2]).zero_one_sequence() [1, 1, 0]
- class sage.combinat.partition.Partitions(is_infinite=False)¶
Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
Partitions(n, **kwargs)
returns the combinatorial class of integer partitions of \(n\) subject to the constraints given by the keywords.Valid keywords are:
starting
,ending
,min_part
,max_part
,max_length
,min_length
,length
,max_slope
,min_slope
,inner
,outer
,parts_in
,regular
, andrestricted
. They have the following meanings:starting=p
specifies that the partitions should all be less than or equal to \(p\) in lex order. This argument cannot be combined with any other (see trac ticket #15467).ending=p
specifies that the partitions should all be greater than or equal to \(p\) in lex order. This argument cannot be combined with any other (see trac ticket #15467).length=k
specifies that the partitions have exactly \(k\) parts.min_length=k
specifies that the partitions have at least \(k\) parts.min_part=k
specifies that all parts of the partitions are at least \(k\).inner=p
specifies that the partitions must contain the partition \(p\).outer=p
specifies that the partitions be contained inside the partition \(p\).min_slope=k
specifies that the partitions have slope at least \(k\); the slope at position \(i\) is the difference between the \((i+1)\)-th part and the \(i\)-th part.parts_in=S
specifies that the partitions have parts in the set \(S\), which can be any sequence of pairwise distinct positive integers. This argument cannot be combined with any other (see trac ticket #15467).regular=ell
specifies that the partitions are \(\ell\)-regular, and can only be combined with themax_length
ormax_part
, but not both, keywords if \(n\) is not specifiedrestricted=ell
specifies that the partitions are \(\ell\)-restricted, and cannot be combined with any other keywords
The
max_*
versions, along withinner
andending
, work analogously.Right now, the
parts_in
,starting
,ending
,regular
, andrestricted
keyword arguments are mutually exclusive, both of each other and of other keyword arguments. If you specify, say,parts_in
, all other keyword arguments will be ignored;starting
,ending
,regular
, andrestricted
work the same way.EXAMPLES:
If no arguments are passed, then the combinatorial class of all integer partitions is returned:
sage: Partitions() Partitions sage: [2,1] in Partitions() True
If an integer \(n\) is passed, then the combinatorial class of integer partitions of \(n\) is returned:
sage: Partitions(3) Partitions of the integer 3 sage: Partitions(3).list() [[3], [2, 1], [1, 1, 1]]
If
starting=p
is passed, then the combinatorial class of partitions greater than or equal to \(p\) in lexicographic order is returned:sage: Partitions(3, starting=[2,1]) Partitions of the integer 3 starting with [2, 1] sage: Partitions(3, starting=[2,1]).list() [[2, 1], [1, 1, 1]]
If
ending=p
is passed, then the combinatorial class of partitions at most \(p\) in lexicographic order is returned:sage: Partitions(3, ending=[2,1]) Partitions of the integer 3 ending with [2, 1] sage: Partitions(3, ending=[2,1]).list() [[3], [2, 1]]
Using
max_slope=-1
yields partitions into distinct parts – each part differs from the next by at least 1. Use a differentmax_slope
to get parts that differ by, say, 2:sage: Partitions(7, max_slope=-1).list() [[7], [6, 1], [5, 2], [4, 3], [4, 2, 1]] sage: Partitions(15, max_slope=-1).cardinality() 27
The number of partitions of \(n\) into odd parts equals the number of partitions into distinct parts. Let’s test that for \(n\) from 10 to 20:
sage: test = lambda n: Partitions(n, max_slope=-1).cardinality() == Partitions(n, parts_in=[1,3..n]).cardinality() sage: all(test(n) for n in [10..20]) True
The number of partitions of \(n\) into distinct parts that differ by at least 2 equals the number of partitions into parts that equal 1 or 4 modulo 5; this is one of the Rogers-Ramanujan identities:
sage: test = lambda n: Partitions(n, max_slope=-2).cardinality() == Partitions(n, parts_in=([1,6..n] + [4,9..n])).cardinality() sage: all(test(n) for n in [10..20]) True
Here are some more examples illustrating
min_part
,max_part
, andlength
:sage: Partitions(5,min_part=2) Partitions of the integer 5 satisfying constraints min_part=2 sage: Partitions(5,min_part=2).list() [[5], [3, 2]]
sage: Partitions(3,max_length=2).list() [[3], [2, 1]]
sage: Partitions(10, min_part=2, length=3).list() [[6, 2, 2], [5, 3, 2], [4, 4, 2], [4, 3, 3]]
Some examples using the
regular
keyword:sage: Partitions(regular=4) 4-Regular Partitions sage: Partitions(regular=4, max_length=3) 4-Regular Partitions with max length 3 sage: Partitions(regular=4, max_part=3) 4-Regular 3-Bounded Partitions sage: Partitions(3, regular=4) 4-Regular Partitions of the integer 3
Some examples using the
restricted
keyword:sage: Partitions(restricted=4) 4-Restricted Partitions sage: Partitions(3, restricted=4) 4-Restricted Partitions of the integer 3
Here are some further examples using various constraints:
sage: [x for x in Partitions(4)] [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, length=2)] [[3, 1], [2, 2]] sage: [x for x in Partitions(4, min_length=2)] [[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, max_length=2)] [[4], [3, 1], [2, 2]] sage: [x for x in Partitions(4, min_length=2, max_length=2)] [[3, 1], [2, 2]] sage: [x for x in Partitions(4, max_part=2)] [[2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, min_part=2)] [[4], [2, 2]] sage: [x for x in Partitions(4, outer=[3,1,1])] [[3, 1], [2, 1, 1]] sage: [x for x in Partitions(4, outer=[infinity, 1, 1])] [[4], [3, 1], [2, 1, 1]] sage: [x for x in Partitions(4, inner=[1,1,1])] [[2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, max_slope=-1)] [[4], [3, 1]] sage: [x for x in Partitions(4, min_slope=-1)] [[4], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(11, max_slope=-1, min_slope=-3, min_length=2, max_length=4)] [[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]] sage: [x for x in Partitions(11, max_slope=-1, min_slope=-3, min_length=2, max_length=4, outer=[6,5,2])] [[6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2]]
Note that if you specify
min_part=0
, then it will treat the minimum part as being 1 (see trac ticket #13605):sage: [x for x in Partitions(4, length=3, min_part=0)] [[2, 1, 1]] sage: [x for x in Partitions(4, min_length=3, min_part=0)] [[2, 1, 1], [1, 1, 1, 1]]
Except for very special cases, counting is done by brute force iteration through all the partitions. However the iteration itself has a reasonable complexity (see
IntegerListsLex
), which allows for manipulating large partitions:sage: Partitions(1000, max_length=1).list() [[1000]]
In particular, getting the first element is also constant time:
sage: Partitions(30, max_part=29).first() [29, 1]
- options(*get_value, **set_value)¶
Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to partitions can be accessed as the methodPartitions.options
ofPartitions
and related parent classes.OPTIONS:
convention
– (default:English
) Sets the convention used for displaying tableaux and partitionsEnglish
– use the English conventionFrench
– use the French convention
diagram_str
– (default:*
) The character used for the cells when printing Ferrers diagramsdisplay
– (default:list
) Specifies how partitions should be printedarray
– alias fordiagram
compact
– alias forcompact_low
compact_high
– compact form ofexp_high
compact_low
– compact form ofexp_low
diagram
– as a Ferrers diagramexp
– alias forexp_low
exp_high
– in exponential form (highest first)exp_low
– in exponential form (lowest first)ferrers_diagram
– alias fordiagram
list
– displayed as a listyoung_diagram
– alias fordiagram
latex
– (default:young_diagram
) Specifies how partitions should be latexedarray
– alias fordiagram
diagram
– latex as a Ferrers diagramexp
– alias forexp_low
exp_high
– latex as a list in exponential notation (highest first)exp_low
– as a list latex in exponential notation (lowest first)ferrers_diagram
– alias fordiagram
list
– latex as a listyoung_diagram
– latex as a Young diagram
latex_diagram_str
– (default:\ast
) The character used for the cells when latexing Ferrers diagramsnotation
– alternative name forconvention
EXAMPLES:
sage: P = Partition([4,2,2,1]) sage: P [4, 2, 2, 1] sage: Partitions.options.display="exp" sage: P 1, 2^2, 4 sage: Partitions.options.display="exp_high" sage: P 4, 2^2, 1
It is also possible to use user defined functions for the
display
andlatex
options:sage: Partitions.options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P <4,2,2,1> sage: Partitions.options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P) \Diagram{4,2,2,1} sage: Partitions.options(display="diagram", diagram_str="#") sage: P #### ## ## # sage: Partitions.options(diagram_str="*", convention="french") sage: print(P.ferrers_diagram()) * ** ** ****
Changing the
convention
for partitions also changes theconvention
option for tableaux and vice versa:sage: T = Tableau([[1,2,3],[4,5]]) sage: T.pp() 4 5 1 2 3 sage: Tableaux.options.convention="english" sage: print(P.ferrers_diagram()) **** ** ** * sage: T.pp() 1 2 3 4 5 sage: Partitions.options._reset()
See
GlobalOptions
for more features of these options.
- subset(*args, **kwargs)¶
Return
self
if no arguments are given, otherwise raises aValueError
.EXAMPLES:
sage: P = Partitions(5, starting=[3,1]); P Partitions of the integer 5 starting with [3, 1] sage: P.subset() Partitions of the integer 5 starting with [3, 1] sage: P.subset(ending=[3,1]) Traceback (most recent call last): ... ValueError: Invalid combination of arguments
- class sage.combinat.partition.PartitionsGreatestEQ(n, k)¶
Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.combinat.integer_lists.invlex.IntegerListsLex
The class of all (unordered) “restricted” partitions of the integer \(n\) having all its greatest parts equal to the integer \(k\).
EXAMPLES:
sage: PartitionsGreatestEQ(10, 2) Partitions of 10 having greatest part equal to 2 sage: PartitionsGreatestEQ(10, 2).list() [[2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1]] sage: [4,3,2,1] in PartitionsGreatestEQ(10, 2) False sage: [2,2,2,2,2] in PartitionsGreatestEQ(10, 2) True
The empty partition has no maximal part, but it is contained in the set of partitions with any specified maximal part:
sage: PartitionsGreatestEQ(0, 2).list() [[]]
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: PartitionsGreatestEQ(10, 2).cardinality() 5
- options(*get_value, **set_value)¶
Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to partitions can be accessed as the methodPartitions.options
ofPartitions
and related parent classes.OPTIONS:
convention
– (default:English
) Sets the convention used for displaying tableaux and partitionsEnglish
– use the English conventionFrench
– use the French convention
diagram_str
– (default:*
) The character used for the cells when printing Ferrers diagramsdisplay
– (default:list
) Specifies how partitions should be printedarray
– alias fordiagram
compact
– alias forcompact_low
compact_high
– compact form ofexp_high
compact_low
– compact form ofexp_low
diagram
– as a Ferrers diagramexp
– alias forexp_low
exp_high
– in exponential form (highest first)exp_low
– in exponential form (lowest first)ferrers_diagram
– alias fordiagram
list
– displayed as a listyoung_diagram
– alias fordiagram
latex
– (default:young_diagram
) Specifies how partitions should be latexedarray
– alias fordiagram
diagram
– latex as a Ferrers diagramexp
– alias forexp_low
exp_high
– latex as a list in exponential notation (highest first)exp_low
– as a list latex in exponential notation (lowest first)ferrers_diagram
– alias fordiagram
list
– latex as a listyoung_diagram
– latex as a Young diagram
latex_diagram_str
– (default:\ast
) The character used for the cells when latexing Ferrers diagramsnotation
– alternative name forconvention
EXAMPLES:
sage: P = Partition([4,2,2,1]) sage: P [4, 2, 2, 1] sage: Partitions.options.display="exp" sage: P 1, 2^2, 4 sage: Partitions.options.display="exp_high" sage: P 4, 2^2, 1
It is also possible to use user defined functions for the
display
andlatex
options:sage: Partitions.options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P <4,2,2,1> sage: Partitions.options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P) \Diagram{4,2,2,1} sage: Partitions.options(display="diagram", diagram_str="#") sage: P #### ## ## # sage: Partitions.options(diagram_str="*", convention="french") sage: print(P.ferrers_diagram()) * ** ** ****
Changing the
convention
for partitions also changes theconvention
option for tableaux and vice versa:sage: T = Tableau([[1,2,3],[4,5]]) sage: T.pp() 4 5 1 2 3 sage: Tableaux.options.convention="english" sage: print(P.ferrers_diagram()) **** ** ** * sage: T.pp() 1 2 3 4 5 sage: Partitions.options._reset()
See
GlobalOptions
for more features of these options.
- class sage.combinat.partition.PartitionsGreatestLE(n, k)¶
Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.combinat.integer_lists.invlex.IntegerListsLex
The class of all (unordered) “restricted” partitions of the integer \(n\) having parts less than or equal to the integer \(k\).
EXAMPLES:
sage: PartitionsGreatestLE(10, 2) Partitions of 10 having parts less than or equal to 2 sage: PartitionsGreatestLE(10, 2).list() [[2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] sage: [4,3,2,1] in PartitionsGreatestLE(10, 2) False sage: [2,2,2,2,2] in PartitionsGreatestLE(10, 2) True sage: PartitionsGreatestLE(10, 2).first().parent() Partitions...
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: PartitionsGreatestLE(9, 5).cardinality() 23
- options(*get_value, **set_value)¶
Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to partitions can be accessed as the methodPartitions.options
ofPartitions
and related parent classes.OPTIONS:
convention
– (default:English
) Sets the convention used for displaying tableaux and partitionsEnglish
– use the English conventionFrench
– use the French convention
diagram_str
– (default:*
) The character used for the cells when printing Ferrers diagramsdisplay
– (default:list
) Specifies how partitions should be printedarray
– alias fordiagram
compact
– alias forcompact_low
compact_high
– compact form ofexp_high
compact_low
– compact form ofexp_low
diagram
– as a Ferrers diagramexp
– alias forexp_low
exp_high
– in exponential form (highest first)exp_low
– in exponential form (lowest first)ferrers_diagram
– alias fordiagram
list
– displayed as a listyoung_diagram
– alias fordiagram
latex
– (default:young_diagram
) Specifies how partitions should be latexedarray
– alias fordiagram
diagram
– latex as a Ferrers diagramexp
– alias forexp_low
exp_high
– latex as a list in exponential notation (highest first)exp_low
– as a list latex in exponential notation (lowest first)ferrers_diagram
– alias fordiagram
list
– latex as a listyoung_diagram
– latex as a Young diagram
latex_diagram_str
– (default:\ast
) The character used for the cells when latexing Ferrers diagramsnotation
– alternative name forconvention
EXAMPLES:
sage: P = Partition([4,2,2,1]) sage: P [4, 2, 2, 1] sage: Partitions.options.display="exp" sage: P 1, 2^2, 4 sage: Partitions.options.display="exp_high" sage: P 4, 2^2, 1
It is also possible to use user defined functions for the
display
andlatex
options:sage: Partitions.options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P <4,2,2,1> sage: Partitions.options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P) \Diagram{4,2,2,1} sage: Partitions.options(display="diagram", diagram_str="#") sage: P #### ## ## # sage: Partitions.options(diagram_str="*", convention="french") sage: print(P.ferrers_diagram()) * ** ** ****
Changing the
convention
for partitions also changes theconvention
option for tableaux and vice versa:sage: T = Tableau([[1,2,3],[4,5]]) sage: T.pp() 4 5 1 2 3 sage: Tableaux.options.convention="english" sage: print(P.ferrers_diagram()) **** ** ** * sage: T.pp() 1 2 3 4 5 sage: Partitions.options._reset()
See
GlobalOptions
for more features of these options.
- class sage.combinat.partition.PartitionsInBox(h, w)¶
Bases:
sage.combinat.partition.Partitions
All partitions which fit in an \(h \times w\) box.
EXAMPLES:
sage: PartitionsInBox(2,2) Integer partitions which fit in a 2 x 2 box sage: PartitionsInBox(2,2).list() [[], [1], [1, 1], [2], [2, 1], [2, 2]]
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: PartitionsInBox(2, 3).cardinality() 10
- list()¶
Return a list of all the partitions inside a box of height \(h\) and width \(w\).
EXAMPLES:
sage: PartitionsInBox(2,2).list() [[], [1], [1, 1], [2], [2, 1], [2, 2]] sage: PartitionsInBox(2,3).list() [[], [1], [1, 1], [2], [2, 1], [2, 2], [3], [3, 1], [3, 2], [3, 3]]
- class sage.combinat.partition.Partitions_all¶
Bases:
sage.combinat.partition.Partitions
Class of all partitions.
- from_beta_numbers(beta)¶
Return a partition corresponding to a sequence of beta numbers.
A sequence of beta numbers is a strictly increasing sequence \(0 \leq b_1 < \cdots < b_k\) of non-negative integers. The corresponding partition \(\mu = (\mu_k, \ldots, \mu_1)\) is given by \(\mu_i = [1,i) \setminus \{ b_1, \ldots, b_i \}\). This gives a bijection from the set of partitions with at most \(k\) non-zero parts to the set of strictly increasing sequences of non-negative integers of length \(k\).
EXAMPLES:
sage: Partitions().from_beta_numbers([0,1,2,4,5,8]) [3, 1, 1] sage: Partitions().from_beta_numbers([0,2,3,6]) [3, 1, 1]
- from_core_and_quotient(core, quotient)¶
Return a partition from its core and quotient.
Algorithm from mupad-combinat.
EXAMPLES:
sage: Partitions().from_core_and_quotient([2,1], [[2,1],[3],[1,1,1]]) [11, 5, 5, 3, 2, 2, 2]
- from_exp(exp)¶
Return a partition from its list of multiplicities.
EXAMPLES:
sage: Partitions().from_exp([2,2,1]) [3, 2, 2, 1, 1]
- from_frobenius_coordinates(frobenius_coordinates)¶
Return a partition from a pair of sequences of Frobenius coordinates.
EXAMPLES:
sage: Partitions().from_frobenius_coordinates(([],[])) [] sage: Partitions().from_frobenius_coordinates(([0],[0])) [1] sage: Partitions().from_frobenius_coordinates(([1],[1])) [2, 1] sage: Partitions().from_frobenius_coordinates(([6,3,2],[4,1,0])) [7, 5, 5, 1, 1]
- from_zero_one(seq)¶
Return a partition from its \(0-1\) sequence.
The full \(0-1\) sequence is the sequence (infinite in both directions) indicating the steps taken when following the outer rim of the diagram of the partition. We use the convention that in English convention, a 1 corresponds to an East step, and a 0 corresponds to a North step.
Note that every full \(0-1\) sequence starts with infinitely many 0’s and ends with infinitely many 1’s.
See also
INPUT:
The input should be a finite sequence of 0’s and 1’s. The heading 0’s and trailing 1’s will be discarded.
EXAMPLES:
sage: Partitions().from_zero_one([]) [] sage: Partitions().from_zero_one([1,0]) [1] sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0]) [5, 4]
Heading 0’s and trailing 1’s are correctly handled:
sage: Partitions().from_zero_one([0,0,1,1,1,1,0,1,0,1,1,1]) [5, 4]
- subset(size=None, **kwargs)¶
Return the subset of partitions of a given size and additional keyword arguments.
EXAMPLES:
sage: P = Partitions() sage: P.subset(4) Partitions of the integer 4
- class sage.combinat.partition.Partitions_all_bounded(k)¶
- class sage.combinat.partition.Partitions_constraints(*args, **kwds)¶
Bases:
sage.combinat.integer_lists.invlex.IntegerListsLex
For unpickling old constrained
Partitions_constraints
objects created with sage <= 3.4.1. SeePartitions
.
- class sage.combinat.partition.Partitions_ending(n, ending_partition)¶
Bases:
sage.combinat.partition.Partitions
All partitions with a given ending.
- first()¶
Return the first partition in
self
.EXAMPLES:
sage: Partitions(4, ending=[1,1,1,1]).first() [4]
- next(part)¶
Return the next partition after
part
inself
.EXAMPLES:
sage: Partitions(4, ending=[1,1,1,1]).next(Partition([4])) [3, 1] sage: Partitions(4, ending=[1,1,1,1]).next(Partition([1,1,1,1])) is None True
- class sage.combinat.partition.Partitions_n(n)¶
Bases:
sage.combinat.partition.Partitions
Partitions of the integer \(n\).
- cardinality(algorithm='flint')¶
Return the number of partitions of the specified size.
INPUT:
algorithm
- (default:'flint'
)'flint'
– use FLINT (currently the fastest)'gap'
– use GAP (VERY slow)'pari'
– use PARI. Speed seems the same as GAP until \(n\) is in the thousands, in which case PARI is faster.
It is possible to associate with every partition of the integer \(n\) a conjugacy class of permutations in the symmetric group on \(n\) points and vice versa. Therefore the number of partitions \(p_n\) is the number of conjugacy classes of the symmetric group on \(n\) points.
EXAMPLES:
sage: v = Partitions(5).list(); v [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]] sage: len(v) 7 sage: Partitions(5).cardinality(algorithm='gap') 7 sage: Partitions(5).cardinality(algorithm='pari') 7 sage: number_of_partitions(5, algorithm='flint') 7
The input must be a nonnegative integer or a
ValueError
is raised.sage: Partitions(10).cardinality() 42 sage: Partitions(3).cardinality() 3 sage: Partitions(10).cardinality() 42 sage: Partitions(3).cardinality(algorithm='pari') 3 sage: Partitions(10).cardinality(algorithm='pari') 42 sage: Partitions(40).cardinality() 37338 sage: Partitions(100).cardinality() 190569292
A generating function for \(p_n\) is given by the reciprocal of Euler’s function:
\[\sum_{n=0}^{\infty} p_n x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}.\]We use Sage to verify that the first several coefficients do indeed agree:
sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen() sage: prod([(1-q^k)^(-1) for k in range(1,9)]) ## partial product of 1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9) sage: [Partitions(k).cardinality() for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
Another consistency test for
n
up to 500:sage: len([n for n in [1..500] if Partitions(n).cardinality() != Partitions(n).cardinality(algorithm='pari')]) 0
REFERENCES:
- first()¶
Return the lexicographically first partition of a positive integer \(n\). This is the partition
[n]
.EXAMPLES:
sage: Partitions(4).first() [4]
- last()¶
Return the lexicographically last partition of the positive integer \(n\). This is the all-ones partition.
EXAMPLES:
sage: Partitions(4).last() [1, 1, 1, 1]
- next(p)¶
Return the lexicographically next partition after the partition
p
.EXAMPLES:
sage: Partitions(4).next([4]) [3, 1] sage: Partitions(4).next([1,1,1,1]) is None True
- random_element(measure='uniform')¶
Return a random partitions of \(n\) for the specified measure.
INPUT:
measure
–'uniform'
or'Plancherel'
(default:'uniform'
)
EXAMPLES:
sage: Partitions(5).random_element() # random [2, 1, 1, 1] sage: Partitions(5).random_element(measure='Plancherel') # random [2, 1, 1, 1]
- random_element_plancherel()¶
Return a random partition of \(n\) (for the Plancherel measure).
This probability distribution comes from the uniform distribution on permutations via the Robinson-Schensted correspondence.
See Wikipedia article Plancherel_measure and
Partition.plancherel_measure()
.EXAMPLES:
sage: Partitions(5).random_element_plancherel() # random [2, 1, 1, 1] sage: Partitions(20).random_element_plancherel() # random [9, 3, 3, 2, 2, 1]
ALGORITHM:
insert by Robinson-Schensted a uniform random permutations of n and returns the shape of the resulting tableau. The complexity is \(O(n\ln(n))\) which is likely optimal. However, the implementation could be optimized.
AUTHOR:
Florent Hivert (2009-11-23)
- random_element_uniform()¶
Return a random partition of \(n\) with uniform probability.
EXAMPLES:
sage: Partitions(5).random_element_uniform() # random [2, 1, 1, 1] sage: Partitions(20).random_element_uniform() # random [9, 3, 3, 2, 2, 1]
ALGORITHM:
It is a python Implementation of RANDPAR, see [NW1978]. The complexity is unknown, there may be better algorithms.
Todo
Check in Knuth AOCP4.
There is also certainly a lot of room for optimizations, see comments in the code.
AUTHOR:
Florent Hivert (2009-11-23)
- subset(**kwargs)¶
Return a subset of
self
with the additional optional arguments.EXAMPLES:
sage: P = Partitions(5); P Partitions of the integer 5 sage: P.subset(starting=[3,1]) Partitions of the integer 5 starting with [3, 1]
- class sage.combinat.partition.Partitions_nk(n, k)¶
Bases:
sage.combinat.partition.Partitions
Partitions of the integer \(n\) of length equal to \(k\).
- cardinality(algorithm='hybrid')¶
Return the number of partitions of the specified size with the specified length.
INPUT:
algorithm
– (default:'hybrid'
) the algorithm to compute the cardinality and can be one of the following:'hybrid'
- use a hybrid algorithm which uses heuristics to reduce the complexity'gap'
- use GAP
EXAMPLES:
sage: v = Partitions(5, length=2).list(); v [[4, 1], [3, 2]] sage: len(v) 2 sage: Partitions(5, length=2).cardinality() 2
More generally, the number of partitions of \(n\) of length \(2\) is \(\left\lfloor \frac{n}{2} \right\rfloor\):
sage: all( Partitions(n, length=2).cardinality() ....: == n // 2 for n in range(10) ) True
The number of partitions of \(n\) of length \(1\) is \(1\) for \(n\) positive:
sage: all( Partitions(n, length=1).cardinality() == 1 ....: for n in range(1, 10) ) True
Further examples:
sage: Partitions(5, length=3).cardinality() 2 sage: Partitions(6, length=3).cardinality() 3 sage: Partitions(8, length=4).cardinality() 5 sage: Partitions(8, length=5).cardinality() 3 sage: Partitions(15, length=6).cardinality() 26 sage: Partitions(0, length=0).cardinality() 1 sage: Partitions(0, length=1).cardinality() 0 sage: Partitions(1, length=0).cardinality() 0 sage: Partitions(1, length=4).cardinality() 0
- subset(**kwargs)¶
Return a subset of
self
with the additional optional arguments.EXAMPLES:
sage: P = Partitions(5, length=2); P Partitions of the integer 5 of length 2 sage: P.subset(max_part=3) Partitions of the integer 5 satisfying constraints length=2, max_part=3
- class sage.combinat.partition.Partitions_parts_in(n, parts)¶
Bases:
sage.combinat.partition.Partitions
Partitions of \(n\) with parts in a given set \(S\).
This is invoked indirectly when calling
Partitions(n, parts_in=parts)
, whereparts
is a list of pairwise distinct integers.- cardinality()¶
Return the number of partitions with parts in
self
. Wraps GAP’sNrRestrictedPartitions
.EXAMPLES:
sage: Partitions(15, parts_in=[2,3,7]).cardinality() 5
If you can use all parts 1 through \(n\), we’d better get \(p(n)\):
sage: Partitions(20, parts_in=[1..20]).cardinality() == Partitions(20).cardinality() True
- first()¶
Return the lexicographically first partition of a positive integer \(n\) with the specified parts, or
None
if no such partition exists.EXAMPLES:
sage: Partitions(9, parts_in=[3,4]).first() [3, 3, 3] sage: Partitions(6, parts_in=[1..6]).first() [6] sage: Partitions(30, parts_in=[4,7,8,10,11]).first() [11, 11, 8]
- last()¶
Return the lexicographically last partition of the positive integer \(n\) with the specified parts, or
None
if no such partition exists.EXAMPLES:
sage: Partitions(15, parts_in=[2,3]).last() [3, 2, 2, 2, 2, 2, 2] sage: Partitions(30, parts_in=[4,7,8,10,11]).last() [7, 7, 4, 4, 4, 4] sage: Partitions(10, parts_in=[3,6]).last() is None True sage: Partitions(50, parts_in=[11,12,13]).last() [13, 13, 12, 12] sage: Partitions(30, parts_in=[4,7,8,10,11]).last() [7, 7, 4, 4, 4, 4]
- class sage.combinat.partition.Partitions_starting(n, starting_partition)¶
Bases:
sage.combinat.partition.Partitions
All partitions with a given start.
- first()¶
Return the first partition in
self
.EXAMPLES:
sage: Partitions(3, starting=[2,1]).first() [2, 1]
- next(part)¶
Return the next partition after
part
inself
.EXAMPLES:
sage: Partitions(3, starting=[2,1]).next(Partition([2,1])) [1, 1, 1]
- class sage.combinat.partition.Partitions_with_constraints(*args, **kwds)¶
Bases:
sage.combinat.integer_lists.invlex.IntegerListsLex
Partitions which satisfy a set of constraints.
EXAMPLES:
sage: P = Partitions(6, inner=[1,1], max_slope=-1) sage: list(P) [[5, 1], [4, 2], [3, 2, 1]]
- options(*get_value, **set_value)¶
Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.
The
options
to partitions can be accessed as the methodPartitions.options
ofPartitions
and related parent classes.OPTIONS:
convention
– (default:English
) Sets the convention used for displaying tableaux and partitionsEnglish
– use the English conventionFrench
– use the French convention
diagram_str
– (default:*
) The character used for the cells when printing Ferrers diagramsdisplay
– (default:list
) Specifies how partitions should be printedarray
– alias fordiagram
compact
– alias forcompact_low
compact_high
– compact form ofexp_high
compact_low
– compact form ofexp_low
diagram
– as a Ferrers diagramexp
– alias forexp_low
exp_high
– in exponential form (highest first)exp_low
– in exponential form (lowest first)ferrers_diagram
– alias fordiagram
list
– displayed as a listyoung_diagram
– alias fordiagram
latex
– (default:young_diagram
) Specifies how partitions should be latexedarray
– alias fordiagram
diagram
– latex as a Ferrers diagramexp
– alias forexp_low
exp_high
– latex as a list in exponential notation (highest first)exp_low
– as a list latex in exponential notation (lowest first)ferrers_diagram
– alias fordiagram
list
– latex as a listyoung_diagram
– latex as a Young diagram
latex_diagram_str
– (default:\ast
) The character used for the cells when latexing Ferrers diagramsnotation
– alternative name forconvention
EXAMPLES:
sage: P = Partition([4,2,2,1]) sage: P [4, 2, 2, 1] sage: Partitions.options.display="exp" sage: P 1, 2^2, 4 sage: Partitions.options.display="exp_high" sage: P 4, 2^2, 1
It is also possible to use user defined functions for the
display
andlatex
options:sage: Partitions.options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P <4,2,2,1> sage: Partitions.options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P) \Diagram{4,2,2,1} sage: Partitions.options(display="diagram", diagram_str="#") sage: P #### ## ## # sage: Partitions.options(diagram_str="*", convention="french") sage: print(P.ferrers_diagram()) * ** ** ****
Changing the
convention
for partitions also changes theconvention
option for tableaux and vice versa:sage: T = Tableau([[1,2,3],[4,5]]) sage: T.pp() 4 5 1 2 3 sage: Tableaux.options.convention="english" sage: print(P.ferrers_diagram()) **** ** ** * sage: T.pp() 1 2 3 4 5 sage: Partitions.options._reset()
See
GlobalOptions
for more features of these options.
- class sage.combinat.partition.RegularPartitions(ell, is_infinite=False)¶
Bases:
sage.combinat.partition.Partitions
Base class for \(\ell\)-regular partitions.
Let \(\ell\) be a positive integer. A partition \(\lambda\) is \(\ell\)-regular if \(m_i < \ell\) for all \(i\), where \(m_i\) is the multiplicity of \(i\) in \(\lambda\).
Note
This is conjugate to the notion of \(\ell\)-restricted partitions, where the difference between any two consecutive parts is \(< \ell\).
INPUT:
ell
– the positive integer \(\ell\)is_infinite
– boolean; if the subset of \(\ell\)-regular partitions is infinite
- ell()¶
Return the value \(\ell\).
EXAMPLES:
sage: P = Partitions(regular=2) sage: P.ell() 2
- class sage.combinat.partition.RegularPartitions_all(ell)¶
Bases:
sage.combinat.partition.RegularPartitions
The class of all \(\ell\)-regular partitions.
INPUT:
ell
– the positive integer \(\ell\)
See also
- class sage.combinat.partition.RegularPartitions_bounded(ell, k)¶
Bases:
sage.combinat.partition.RegularPartitions
The class of \(\ell\)-regular \(k\)-bounded partitions.
INPUT:
ell
– the integer \(\ell\)k
– integer; the value \(k\)
See also
- class sage.combinat.partition.RegularPartitions_n(n, ell)¶
Bases:
sage.combinat.partition.RegularPartitions
,sage.combinat.partition.Partitions_n
The class of \(\ell\)-regular partitions of \(n\).
INPUT:
n
– the integer \(n\) to partitionell
– the integer \(\ell\)
See also
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: P = Partitions(5, regular=3) sage: P.cardinality() 5 sage: P = Partitions(5, regular=6) sage: P.cardinality() 7 sage: P.cardinality() == Partitions(5).cardinality() True
- class sage.combinat.partition.RegularPartitions_truncated(ell, max_len)¶
Bases:
sage.combinat.partition.RegularPartitions
The class of \(\ell\)-regular partitions with max length \(k\).
INPUT:
ell
– the integer \(\ell\)max_len
– integer; the maximum length
See also
- max_length()¶
Return the maximum length of the partitions of
self
.EXAMPLES:
sage: P = Partitions(regular=4, max_length=3) sage: P.max_length() 3
- class sage.combinat.partition.RestrictedPartitions_all(ell)¶
Bases:
sage.combinat.partition.RestrictedPartitions_generic
The class of all \(\ell\)-restricted partitions.
INPUT:
ell
– the positive integer \(\ell\)
See also
- class sage.combinat.partition.RestrictedPartitions_generic(ell, is_infinite=False)¶
Bases:
sage.combinat.partition.Partitions
Base class for \(\ell\)-restricted partitions.
Let \(\ell\) be a positive integer. A partition \(\lambda\) is \(\ell\)-restricted if \(\lambda_i - \lambda_{i+1} < \ell\) for all \(i\), including rows of length 0.
Note
This is conjugate to the notion of \(\ell\)-regular partitions, where the multiplicity of any parts is at most \(\ell\).
INPUT:
ell
– the positive integer \(\ell\)is_infinite
– boolean; if the subset of \(\ell\)-restricted partitions is infinite
- ell()¶
Return the value \(\ell\).
EXAMPLES:
sage: P = Partitions(restricted=2) sage: P.ell() 2
- class sage.combinat.partition.RestrictedPartitions_n(n, ell)¶
Bases:
sage.combinat.partition.RestrictedPartitions_generic
,sage.combinat.partition.Partitions_n
The class of \(\ell\)-restricted partitions of \(n\).
INPUT:
n
– the integer \(n\) to partitionell
– the integer \(\ell\)
See also
- cardinality()¶
Return the cardinality of
self
.EXAMPLES:
sage: P = Partitions(5, restricted=3) sage: P.cardinality() 5 sage: P = Partitions(5, restricted=6) sage: P.cardinality() 7 sage: P.cardinality() == Partitions(5).cardinality() True
- sage.combinat.partition.number_of_partitions(n, algorithm='default')¶
Return the number of partitions of \(n\) with, optionally, at most \(k\) parts.
The options of
number_of_partitions()
are being deprecated trac ticket #13072 in favour ofPartitions_n.cardinality()
so thatnumber_of_partitions()
can become a stripped down version of the fastest algorithm available (currently this is using FLINT).INPUT:
n
– an integeralgorithm
– (default: ‘default’) [Will be deprecated except in Partition().cardinality() ]'default'
– Ifk
is notNone
, then use Gap (very slow). Ifk
isNone
, use FLINT.'flint'
– use FLINT
EXAMPLES:
sage: v = Partitions(5).list(); v [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]] sage: len(v) 7
The input must be a nonnegative integer or a
ValueError
is raised.sage: number_of_partitions(-5) Traceback (most recent call last): ... ValueError: n (=-5) must be a nonnegative integer
sage: number_of_partitions(10) 42 sage: number_of_partitions(3) 3 sage: number_of_partitions(10) 42 sage: number_of_partitions(40) 37338 sage: number_of_partitions(100) 190569292 sage: number_of_partitions(100000) 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
A generating function for the number of partitions \(p_n\) is given by the reciprocal of Euler’s function:
\[\sum_{n=0}^{\infty} p_n x^n = \prod_{k=1}^{\infty} \left( \frac{1}{1-x^k} \right).\]We use Sage to verify that the first several coefficients do instead agree:
sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen() sage: prod([(1-q^k)^(-1) for k in range(1,9)]) ## partial product of 1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9) sage: [number_of_partitions(k) for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
REFERENCES:
- sage.combinat.partition.number_of_partitions_length(n, k, algorithm='hybrid')¶
Return the number of partitions of \(n\) with length \(k\).
This is a wrapper for GAP’s
NrPartitions
function.EXAMPLES:
sage: from sage.combinat.partition import number_of_partitions_length sage: number_of_partitions_length(5, 2) 2 sage: number_of_partitions_length(10, 2) 5 sage: number_of_partitions_length(10, 4) 9 sage: number_of_partitions_length(10, 0) 0 sage: number_of_partitions_length(10, 1) 1 sage: number_of_partitions_length(0, 0) 1 sage: number_of_partitions_length(0, 1) 0