A partition of a nonnegative integer
is a
non-increasing list of positive integers (the parts of the
partition) with total sum
.
A partition can be depicted by a diagram made of rows of cells,
where the number of cells in the row starting from
the top is the
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 are
.
For display options, see Partitions.global_options.
Note
Note
We use the convention that lexicographic ordering is read from
left-to-right. That is to say is smaller than
.
AUTHORS:
EXAMPLES:
There are partitions of the integer
:
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(), we can calculate the ‘next’ partition. 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: g.next()
[4]
sage: g.next()
[3, 1]
sage: g.next()
[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 of length
, 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 and the list of
ones with length at most
:
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 with parts at most
:
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 with each part at least
:
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 with [3, 1, 1] as
an outer bound (that is, partitions of
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 of length at most
such that the second and third part are
when they exist:
sage: Partitions(4, outer=[oo,1,1]).list()
[[4], [3, 1], [2, 1, 1]]
Finally, here are the partitions of with [1,1,1] as an inner
bound (i. e., the partitions of
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 :
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 of length between
and
such
that the difference between two consecutive parts is between
and
:
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
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 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(30) 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
Bases: sage.combinat.partition.Partitions
The class of ordered partitions of . If
is specified, then this
contains only the ordered partitions of length
.
An ordered partition of a nonnegative integer means a list of
positive integers whose sum is
. This is the same as a composition
of
.
Note
It is recommended that you use Compositions() instead as OrderedPartitions() 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]]
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
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]]
Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element
A partition of a nonnegative integer
is a
non-increasing list of positive integers (the parts of the
partition) with total sum
.
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 row, reading from top to bottom, is the
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.global_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 is mu[0] (which is 4), the second is mu[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:
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]
TESTS:
Check that only trailing zeros are stripped:
sage: TestSuite( Partition([]) ).run()
sage: TestSuite( Partition([4,3,2,2,2,1]) ).run()
sage: Partition([3,2,2,2,1,0,0,0])
[3, 2, 2, 2, 1]
sage: Partition([3,0,2,2,2,1,0])
Traceback (most recent call last):
...
ValueError: [3, 0, 2, 2, 2, 1, 0] is not an element of Partitions
sage: Partition([0,7,3])
Traceback (most recent call last):
...
ValueError: [0, 7, 3] is not an element of Partitions
Return a partition corresponding to self with a cell added in row i. (This does not change self.)
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]
Return a list of all the partitions that can be obtained by adding a horizontal border strip of length k to self.
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 using IntegerListsLex
Return a list of all the partitions that can be obtained by adding a vertical border strip of length k to self.
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]]
Return a list of the outside corners of the partition self.
An outside corner (also called a cocorner) of a partition
is a cell on
which does not belong to
the Young diagram of
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 ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Return a list of the outside corners of the partition self having l-residue i.
An outside corner (also called a cocorner) of a partition
is a cell on
which does not belong to
the Young diagram of
but can be added to this Young
diagram to still form a straight-shape Young diagram. See
residue() for the definition of the l-residue.
The entries of the list returned are pairs of the form ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Return the list of the cells of the arm of cell in self.
The arm of cell is the boxes that appear to the right of
.
The cell coordinates are zero-based, i. e., the northwesternmost
cell is .
INPUT:
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
Return the length of the arm of cell in self.
The arm of cell is the cells that appear to the right of
cell
.
The cell coordinates are zero-based, i. e., the northwesternmost
cell is .
INPUT:
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
Return a tableau of shape self where each cell is filled with its arm length. The optional boolean parameter flat 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]
This is a statistic on a cell in the diagram of partition
given by
where is the arm length of
and
is the leg length of
.
The coordinates i and j of the cell are understood to be
-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)
Return a list of the standard tableaux of size self.size() whose atom is equal to self.
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]]]
Return a list of the attacking pairs of the Young diagram of self.
A pair of cells of a Young diagram (in English notation) is
said to be attacking if one of the following conditions holds:
This particular method returns each pair as a tuple,
where each of
and
is given as a tuple
with
and
zero-based (so
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()
[]
Return a factor for the number of permutations with cycle type self.
This method returns where
is the number of parts in self equal to
.
The number of permutations having self as a cycle type is given by
(where is the size of self).
EXAMPLES:
sage: Partition([2,1]).aut()
2
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 of self).
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]
Return the Young diagram of self as a poset. The optional keyword variable orientation determines the order relation of the poset.
The poset always uses the set of cells of the Young diagram
of self as its ground set. The order relation of the poset
depends on the orientation variable (which defaults to
"SE"). Concretely, orientation has to be specified to
one of the strings "NW", "NE", "SW", and "SE",
standing for “northwest”, “northeast”, “southwest” and
“southeast”, respectively. If orientation is "SE", then
the order relation of the poset is such that a cell is
greater or equal to a cell
in the poset if and only if
lies weakly southeast of
(this means that
can be
reached from
by a sequence of south and east steps; the
sequence is allowed to consist of south steps only, or of east
steps only, or even be empty). Similarly the order relation is
defined for the other three orientations. The Young diagram is
supposed to be drawn in English notation.
The elements of the poset are the cells of the Young diagram
of self, written as tuples of zero-based coordinates (so
that stands for the
-th cell of the
-th row,
etc.).
EXAMPLES:
sage: p = 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 :
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
TESTS:
We check that the posets are really what they should be for size
up to :
sage: def check_NW(n):
....: for p in Partitions(n):
....: P = p.cell_poset(orientation="NW")
....: for c in p.cells():
....: for d in p.cells():
....: if P.le(c, d) != (c[0] >= d[0]
....: and c[1] >= d[1]):
....: return False
....: return True
sage: all( check_NW(n) for n in range(8) )
True
sage: def check_NE(n):
....: for p in Partitions(n):
....: P = p.cell_poset(orientation="NE")
....: for c in p.cells():
....: for d in p.cells():
....: if P.le(c, d) != (c[0] >= d[0]
....: and c[1] <= d[1]):
....: return False
....: return True
sage: all( check_NE(n) for n in range(8) )
True
sage: def test_duality(n, ori1, ori2):
....: for p in Partitions(n):
....: P = p.cell_poset(orientation=ori1)
....: Q = p.cell_poset(orientation=ori2)
....: for c in p.cells():
....: for d in p.cells():
....: if P.lt(c, d) != Q.lt(d, c):
....: return False
....: return True
sage: all( test_duality(n, "NW", "SE") for n in range(8) )
True
sage: all( test_duality(n, "NE", "SW") for n in range(8) )
True
sage: all( test_duality(n, "NE", "SE") for n in range(4) )
False
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)]
Return the size of the centralizer of any permutation of cycle type self.
If is the multiplicity of
as a part of
, this is given by
Including the optional parameters and
gives the
analog
which is the former product times
See [Ker].
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
Return the character polynomial associated to the partition self.
The character polynomial associated to a partition
is defined by
where is the size of
, and
is the multiplicity of
in
.
It is computed in the following manner:
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
Return a list containing the shape of self.
This method exists only for compatibility with PartitionTuples.
EXAMPLES:
sage: Partition([3,2]).components()
[[3, 2]]
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
REFERENCES:
[Ker] | Kerber, A. ‘Algebraic Combinatorics via Finite Group Actions’ 1.3 p24 |
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()
***
**
**
*
*
*
Return True if x is a partition whose Ferrers diagram is contained in the Ferrers diagram of self.
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
Return the content of the cell at row and column
.
The content of a cell is .
For consistency with partition tuples there is also an optional
multicharge argument which is an offset to the usual content. By
setting the multicharge equal to the 0-element of the ring
, the corresponding
-residue will be returned. This is
the content modulo
.
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
Return the length-core of the partition – in the literature
the core is commonly referred to as the -core,
-core,
-core, ... .
The -core of a partition
can be obtained by
repeatedly removing rim hooks of size
from (the Young diagram
of)
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]
TESTS:
sage: Partition([3,3,3,2,1]).core(3)
[]
sage: Partition([10,8,7,7]).core(4)
[]
sage: Partition([21,15,15,9,6,6,6,3,3]).core(3)
[]
Return a list of the corners of the partition self.
A corner of a partition is a cell of the Young diagram
of
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 ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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()
[]
Return a list of the corners of the partition self having l-residue i.
A corner of a partition is a cell of the Young diagram
of
which can be removed from the Young diagram while
still leaving a straight shape behind. See residue() for
the definition of the l-residue.
The entries of the list returned are pairs of the form ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Return the Dyson crank of self.
The Dyson crank of a partition is defined as follows:
If
contains at least one
, then the crank is
, where
is the
number of
, and
is the number of
parts of
larger than
. If
contains no
, then the crank is simply the largest part of
.
REFERENCES:
[AG1988] | George E. Andrews, F. G. Garvan, Dyson’s crank of a partition. Bull. Amer. Math. Soc. (N.S.) Volume 18, Number 2 (1988), 167-171. http://projecteuclid.org/euclid.bams/1183554533 |
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
Return the number of paths from the smaller partition to
the partition self, where each step consists of adding a
-ribbon while keeping a partition.
Note that a 1-ribbon is just a single cell, so this counts paths
in the Young graph when .
Note also that the default case ( and smaller = [])
gives the dimension of the irreducible representation of the
symmetric group corresponding to self.
INPUT:
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
TESTS:
Checks that the sum of squares of dimensions of characters of the symmetric group is the order of the group:
sage: all(sum(mu.dimension()^2 for mu in Partitions(i))==factorial(i) for i in range(10))
True
A check coming from the theory of -differentiable posets:
sage: k=2; core = Partition([2,1])
sage: all(sum(mu.dimension(core,k=2)^2
....: for mu in Partitions(3+i*2) if mu.core(2) == core)
....: == 2^i*factorial(i) for i in range(10))
True
Checks that the dimension satisfies the obvious recursion relation:
sage: test = lambda larger, smaller: larger.dimension(smaller) == sum(mu.dimension(smaller) for mu in larger.down())
sage: all(test(larger,smaller) for l in xrange(1,10) for s in xrange(0,10)
....: for larger in Partitions(l) for smaller in Partitions(s) if smaller != larger)
True
ALGORITHM:
Depending on the parameters given, different simplifications
occur. When and smaller is empty, this function uses
the hook formula. When
and smaller is not empty, it
uses a formula from [ORV].
When , we first check that both self and
smaller have the same
-core, then use the
-quotients
and the same algorithm on each of the
-quotients.
REFERENCES:
[ORV] | Grigori Olshanski, Amitai Regev, Anatoly Vershik, Frobenius-Schur functions, Arxiv math/0110077v1. Possibly newer version at http://www.wisdom.weizmann.ac.il/~regev/papers/FrobeniusSchurFunctions.ps |
AUTHORS:
Return a list of the partitions dominated by . If rows is
specified, then it only returns the ones whose number of rows
is at most rows.
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]]
Return True if self dominates the partition p2. Otherwise it returns False.
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
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]]
TESTS:
We check that trac ticket #11435 is fixed:
sage: Partition([]).down_list() #indirect doctest
[]
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`
[]
Return the evaluation of self.
The commutative evaluation, often shortened to evaluation, of
a word (we think of a partition as a word in )
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]
Return the Ferrers diagram of self.
EXAMPLES:
sage: mu=Partition([5,5,2,1])
sage: Partitions.global_options(diagram_str='*', convention="english")
sage: print mu.ferrers_diagram()
*****
*****
**
*
sage: Partitions.global_options(diagram_str='#')
sage: print mu.ferrers_diagram()
#####
#####
##
#
sage: Partitions.global_options(convention="french")
sage: print mu.ferrers_diagram()
#
##
#####
#####
sage: print Partition([]).ferrers_diagram()
-
sage: Partitions.global_options(diagram_str='-')
sage: print Partition([]).ferrers_diagram()
(/)
sage: Partitions.global_options.reset()
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])
Return the Frobenius rank of the partition self.
The Frobenius rank of a partition
is
defined to be the largest
such that
.
In other words, it is the number of cells on the main diagonal
of
. In yet other words, it is the size of the largest
square fitting into the Young diagram of
.
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
Maps a -bounded partition to a Grassmannian element in
the affine Weyl group of type
.
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]
Maps a -bounded partition to a reduced word for an element in
the affine permutation group.
This uses the fact that there is a bijection between -bounded
partitions and
-cores and an action of the affine nilCoxeter
algebra of type
on
-cores as described in [LM2006].
REFERENCES:
[LM2006] | MR2167475 (2006j:05214)
L. Lapointe, J. Morse. Tableaux on ![]() ![]() |
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)
[]
Return the Garnir tableau of shape self corresponding to the cell
cell. If cell then
must belong to the
diagram of self.
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 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
entered in order from left to right along the rows
of the diagram up to the cell
, then along the cells
to
, then
until the end of row
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, where g is the resulting Garnir tableau, equal to cell 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
Return the generalized Pochhammer symbol
. This is the product over all
cells
in self of
.
EXAMPLES:
sage: Partition([2,2]).generalized_pochhammer_symbol(2,1)
12
Return the part of self, or default 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
Return the length of the hook of cell in self.
The (length of the) hook of cell of a partition
is
where is the conjugate partition. In English
convention, the hook length is the number of cells horizontally
to the right and vertically below the cell
(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
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:
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
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)
Return a sorted list of the hook lengths in self.
EXAMPLES:
sage: Partition([3,2,1]).hooks()
[5, 3, 3, 1, 1, 1]
Return the standard tableau which has the
numbers where
is the size() of self
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]]
Return a list of the corners of the partition self.
A corner of a partition is a cell of the Young diagram
of
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 ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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()
[]
Return a list of the corners of the partition self having l-residue i.
A corner of a partition is a cell of the Young diagram
of
which can be removed from the Young diagram while
still leaving a straight shape behind. See residue() for
the definition of the l-residue.
The entries of the list returned are pairs of the form ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Tests whether the partition is a -core or not. Visuallly, this can
be checked by trying to remove border strips of size
from self.
If this is not possible, then self is a
-core.
A partition is said to be a `k`-core if it has no hooks of length
. Equivalently, a partition is said to be a
-core if it is its
own
-core (where the latter is defined as in core()).
EXAMPLES:
sage: p = Partition([12,8,5,5,2,2,1])
sage: p.is_core(4)
False
sage: p.is_core(5)
True
sage: p.is_core(0)
True
Return True if self is the empty partition.
EXAMPLES:
sage: Partition([]).is_empty()
True
sage: Partition([2,1,1]).is_empty()
False
Return the Jacobi-Trudi matrix of self thought of as a skew partition. See SkewPartition.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]
Return a list of the standard tableaux of size self.size() whose k-atom is equal to self.
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]]]
TESTS:
sage: Partition([1]).k_atom(1)
[[[1]]]
sage: Partition([1]).k_atom(2)
[[[1]]]
sage: Partition([]).k_atom(1)
[[]]
Return the skew partition formed by removing the cells of the k-interior, see k_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]
Return the k-conjugate of self.
The -conjugate is the partition that is given by the columns of
the
-skew diagram of the partition.
We can also define the -conjugate in the following way. Let
denote the bijection from
-cores to
-bounded partitions. The
-conjugate of a
-core
is
EXAMPLES:
sage: p = Partition([4,3,2,2,1,1])
sage: p.k_conjugate(4)
[3, 2, 2, 1, 1, 1, 1, 1, 1]
Return the partition consisting of the cells of self whose hook lengths are greater than k.
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)
[]
Return the partition with all rectangles removed.
If self is a -bounded partition, then this method will return the partition
where all rectangles of dimension
for
have been deleted.
If self is not a -bounded partition then the method will raise an error.
INPUT:
OUTPUT:
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]
Return the -skew partition.
The -skew diagram of a
-bounded partition is the skew diagram
denoted
satisfying the conditions:
REFERENCES:
[LM2004] | Lapointe, L. and Morse, J. ‘Order Ideals in Weak Subposets of Young’s Lattice and Associated Unimodality Conjectures’. Ann. Combin. (2004) |
EXAMPLES:
sage: p = Partition([4,3,2,2,1,1])
sage: p.k_skew(4)
[9, 5, 3, 2, 1, 1] / [5, 2, 1]
Return the k-split of self.
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]]
Return True if self is larger than rhs in lexicographic order. Otherwise return False.
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
Return the list of the cells of the leg of cell in self.
The leg of cell is defined to be the cells below
(in
English convention).
The cell coordinates are zero-based, i. e., the northwesternmost
cell is .
INPUT:
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
Return the length of the leg of cell in self.
The leg of cell is defined to be the cells below
(in English convention).
The cell coordinates are zero-based, i. e., the northwesternmost
cell is .
INPUT:
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
Return a tableau of shape self with each cell filled in with its leg length. The optional boolean parameter flat 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]
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
Return the level of self, which is always 1.
This method exists only for compatibility with PartitionTuples.
EXAMPLE:
sage: Partition([4,3,2]).level()
1
Return the lower hook length of the cell in self.
When alpha = 1, this is just the normal hook length.
The lower hook length of a cell in a partition
is defined by
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]
Return a tableau of shape self with the cells filled in with the lower hook lengths. When alpha = 1, these are just the normal hook lengths.
The lower hook length of a cell in a partition
is defined by
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]]
Return the partition that lexicographically follows self. If self is the last partition, then return False.
EXAMPLES:
sage: Partition([4]).next()
[3, 1]
sage: Partition([1,1,1,1]).next()
False
Return the outer rim of self.
The outer rim of a partition is defined as the cells which do
not belong to
and which are adjacent to cells in
.
EXAMPLES:
The outer rim of the partition 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)]
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:
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)
TESTS:
sage: integrate(Partition([1]).outline()-abs(x),(x,-10,10))
2
Return a list of the outside corners of the partition self.
An outside corner (also called a cocorner) of a partition
is a cell on
which does not belong to
the Young diagram of
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 ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Return a list of the outside corners of the partition self having l-residue i.
An outside corner (also called a cocorner) of a partition
is a cell on
which does not belong to
the Young diagram of
but can be added to this Young
diagram to still form a straight-shape Young diagram. See
residue() for the definition of the l-residue.
The entries of the list returned are pairs of the form ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
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
TESTS:
sage: all(sum(mu.plancherel_measure() for mu in Partitions(n))==1 for n in range(10))
True
Return the cycle type of the -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 :
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]
Prints the Ferrers diagram.
See ferrers_diagram() for more on the Ferrers diagram.
EXAMPLES:
sage: Partition([5,5,2,1]).pp()
*****
*****
**
*
sage: Partitions.global_options(convention='French')
sage: Partition([5,5,2,1]).pp()
*
**
*****
*****
sage: Partitions.global_options.reset()
Return the quotient of the partition – in the literature the
quotient is commonly referred to as the -quotient,
-quotient,
-quotient, ... .
The -quotient of a partition
is a list of
partitions (labelled from
to
), constructed in the following
way. Label each cell in the Young diagram of
with its
content modulo
. Let
be the set of rows ending in a cell
labelled
, and
be the set of columns ending in a cell
labelled
. Then the
-th component of the quotient of
is the partition defined by intersecting
with
. (See Theorem 2.7.37 in [JamesKerber].)
REFERENCES:
[JamesKerber] | Gordon James, Adalbert Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley 1981. |
EXAMPLES:
sage: Partition([7,7,5,3,3,3,1]).quotient(3)
([2], [1], [2, 2, 2])
TESTS:
sage: Partition([8,7,7,4,1,1,1,1,1]).quotient(3)
([2, 1], [2, 2], [2])
sage: Partition([10,8,7,7]).quotient(4)
([2], [3], [2], [1])
sage: Partition([6,3,3]).quotient(3)
([1], [1], [2])
sage: Partition([3,3,3,2,1]).quotient(3)
([1], [1, 1], [1])
sage: Partition([6,6,6,3,3,3]).quotient(3)
([2, 1], [2, 1], [2, 1])
sage: Partition([21,15,15,9,6,6,6,3,3]).quotient(3)
([5, 2, 1], [5, 2, 1], [7, 3, 2])
sage: Partition([21,15,15,9,6,6,3,3]).quotient(3)
([5, 2], [5, 2, 1], [7, 3, 1])
sage: Partition([14,12,11,10,10,10,10,9,6,4,3,3,2,1]).quotient(5)
([3, 3], [2, 2, 1], [], [3, 3, 3], [1])
sage: all(p == Partition(core=p.core(k), quotient=p.quotient(k))
....: for i in range(10) for p in Partitions(i)
....: for k in range(1,6))
True
Return the RSK recording tableau of the reading word of the
(standard) tableau labeled down (in English convention)
each column to the shape of self.
For an example of the tableau , consider the partition
, 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]]
Return a list of the corners of the partition self.
A corner of a partition is a cell of the Young diagram
of
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 ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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()
[]
Return a list of the corners of the partition self having l-residue i.
A corner of a partition is a cell of the Young diagram
of
which can be removed from the Young diagram while
still leaving a straight shape behind. See residue() for
the definition of the l-residue.
The entries of the list returned are pairs of the form ,
where
and
are the coordinates of the respective corner.
The coordinates are counted from
.
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)]
Return the partition obtained by removing a cell at the end of row i of self.
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)
Return the partitions obtained from self by removing an horizontal border strip of length k.
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 IntegerListsLex:
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
TESTS:
sage: Partition([3,2,2]).remove_horizontal_border_strip(2).list()
[[3, 2], [2, 2, 1]]
sage: Partition([3,2,2]).remove_horizontal_border_strip(2).first().parent()
The subpartitions of [3, 2, 2] obtained by removing an horizontal border strip of length 2
sage: Partition([]).remove_horizontal_border_strip(0).list()
[[]]
sage: Partition([]).remove_horizontal_border_strip(6).list()
[]
Return the l-residue of the cell at row r and column c.
The -residue of a cell is
modulo
.
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
Return the rim of self.
The rim of a partition is defined as the cells which belong
to
and which are adjacent to cells not in
.
EXAMPLES:
The rim of the partition 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()
[]
Return the sign of any permutation with cycle type self.
This function corresponds to a homomorphism from the symmetric
group into the cyclic group of order 2, whose kernel
is exactly the alternating group
. Partitions of sign
are called even partitions while partitions of sign
are called odd.
EXAMPLES:
sage: Partition([5,3]).sign()
1
sage: Partition([5,2]).sign()
-1
Zolotarev’s lemma states that the Legendre symbol
for an integer
(
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
induced by modular multiplication by
, provided
does not divide
.
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 ) 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 by
:
sage: plist = [int(F(3*x)) for x in range(1,11)]; plist
[3, 6, 9, 1, 4, 7, 10, 2, 5, 8]
sage: 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:
Return the size of self.
EXAMPLES:
sage: Partition([2,2]).size()
4
sage: Partition([3,2,1]).size()
6
Return the standard tableaux of this shape.
EXAMPLE:
sage: Partition([3,2,2,1]).standard_tableaux()
Standard tableaux of shape [3, 2, 2, 1]
Return the image of self in under Suter’s diagonal slide
, where the notations used are those defined in [Sut2002].
The set is defined as the set of all partitions
such that the hook length of the
-cell (i.e. the
northwestern most cell in English notation) of
is less
than
, including the empty partition.
The map sends a partition (with non-zero entries)
to the partition
.
In other words, it pads the partition with trailing zeroes
until it has length
, then removes its first
part, and finally adds
to each part.
By Theorem 2.1 of [Sut2002], the dihedral group with
elements acts on
by letting the primitive rotation
act as
and the reflection act as conjugation of
partitions (conjugate()). This action is faithful if
.
INPUT:
OUTPUT:
The result of applying Suter’s diagonal slide to
self, assuming that self lies in
. If the
optional argument exp is set, then the slide
is applied not just once, but exp times
(note that exp 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 :
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
TESTS:
Check for exp = 0:
sage: P = Partitions(4)
sage: all(p == p.suter_diagonal_slide(7, 0) for p in P)
True
Check for invalid input:
sage: p = Partition([2,1])
sage: p.hook_length(0, 0)
3
sage: p.suter_diagonal_slide(2)
Traceback (most recent call last):
...
ValueError: the hook length must be less than n
REFERENCES:
[Sut2002] | (1, 2, 3, 4) Ruedi Suter. Young’s Lattice and Dihedral Symmetries. Europ. J. Combinatorics (2002) 23, 233–238. http://www.sciencedirect.com/science/article/pii/S0195669801905414 |
Return the t-completion of the partition self.
If is a
partition and
is an integer greater or equal to
, then the
-completion of
is defined as the partition
of
. This partition is denoted by
in [BOR09], by
in [BdVO12], and by
in [CO10].
REFERENCES:
[BOR09] | Emmanuel Briand, Rosa Orellana, Mercedes Rosas. The stability of the Kronecker products of Schur functions. Arxiv 0907.4652v2. |
[CO10] | Jonathan Comes, Viktor Ostrik.
On blocks of Deligne’s category
![]() |
[BdVO12] | Christopher Bowman, Maud De Visscher, Rosa Orellana. The partition algebra and the Kronecker coefficients. Arxiv 1210.5579v6. |
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
Maps the -bounded partition self to its corresponding
-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
Return the n-Dyck word whose corresponding partition is
self (or, if n is not specified, the -Dyck word with
smallest
to satisfy this property).
If is an
-Dyck word (that is, a Dyck word with
open
symbols and
close symbols), then the Dyck path corresponding
to
can be regarded as a lattice path in the northeastern
half of an
-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
. (See
to_partition().)
For every partition and every nonnegative integer
,
there exists at most one
-Dyck word
such that the
partition corresponding to
is
(in fact, such
exists if and only if
for every
,
where
is written in the form
with
).
This method computes this
for a given
and
.
If
is not specified, this method computes the
for the
smallest possible
for which such an
exists.
(The minimality of
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() is self indeed:
sage: all( p.to_dyck_word().to_partition() == p
....: for p in Partitions(5) )
True
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 least k.
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]
TESTS:
sage: [parent(x) for x in Partition([3,2,2,1]).to_exp(5)]
[Integer Ring, Integer Ring, Integer Ring, Integer Ring, Integer Ring]
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
Return self as a list.
EXAMPLES:
sage: p = Partition([2,1]).to_list(); p
[2, 1]
sage: type(p)
<type 'list'>
TESTS:
sage: p = Partition([2,1])
sage: pl = p.to_list()
sage: pl[0] = 0; p
[2, 1]
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 [KMR].
If the Garnir node is cell=(r,c) and and
are the entries
in the cells (r,c) and (r+1,c), respectively, in the initial
tableau then the top e-Garnir tableau is obtained by inserting the
numbers
in order from left to right first in the
cells in row r+1 which are not in the e-Garnir belt, then in
the cell in rows r and r+1 which are in the Garnir belt and
then, finally, in the remaining cells in row r which are not in
the Garnir belt. All other entries in the tableau remain unchanged.
If e = 0, or if there are no e-bricks in either row r or r+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
TESTS:
sage: Partition([5,4,3,2]).top_garnir_tableau(0,(3,2)).pp()
Traceback (most recent call last):
...
ValueError: (4,2)=(row+1,col) must be inside the diagram
REFERENCE:
Returns a generator for partitions that can be obtained from self by adding a cell.
EXAMPLES:
sage: [p for p in Partition([2,1,1]).up()]
[[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]
sage: [p for p in Partition([3,2]).up()]
[[4, 2], [3, 3], [3, 2, 1]]
sage: [p for p in Partition([]).up()]
[[1]]
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]]
Return the upper hook length of the cell in self.
When alpha = 1, this is just the normal hook length.
The upper hook length of a cell in a partition
is defined by
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]
Return a tableau of shape self with the cells filled in with the upper hook lengths. When alpha = 1, these are just the normal hook lengths.
The upper hook length of a cell in a partition
is defined by
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]]
Return the weighted size of self.
The weighted size of a partition is
where .
This also the sum of the leg length of every cell in , or
where is the conjugate partition of
.
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
Return the corresponding Young, or parabolic, subgroup of the symmetric group.
The Young subgroup of a partition
of
is
the group:
embedded into in the standard way (i.e.,
the
factor acts on the numbers from
to
).
EXAMPLES:
sage: Partition([4,2]).young_subgroup()
Permutation Group with generators [(), (5,6), (3,4), (2,3), (1,2)]
Return an indexing set for the generators of the corresponding Young
subgroup. Here the generators correspond to the simple adjacent
transpositions .
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]
Compute the finite sequence of the partition.
The full 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 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 and every
such that
corresponds to a 1 and
corresponds to a 0.
See pages 24-25 of [LLMMSZ13] 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 sequence is obtained from the full
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.
REFERENCES:
[LLMMSZ13] | Thomas Lam, Luc Laponte, Jennifer Morse, Anne Schilling,
Mark Shimozono, and Mike Zabrocki. ![]() |
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]
TESTS:
sage: all(Partitions().from_zero_one(mu.zero_one_sequence()) == mu for n in range(10) for mu in Partitions(n))
True
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Partitions(n, **kwargs) returns the combinatorial class of
integer partitions of 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, and parts_in. They have the following meanings:
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 is passed, then the combinatorial class of integer
partitions of
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 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 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 different max_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 into odd parts equals the number of
partitions into distinct parts. Let’s test that for
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 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, and length:
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]]
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 (constant memory, constant amortized time), which allow 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]
TESTS:
sage: TestSuite(Partitions(0)).run()
sage: TestSuite(Partitions(5)).run()
sage: TestSuite(Partitions(5, min_part=2)).run() # Not tested: todo - IntegerListsLex needs to pickle properly
sage: repr( Partitions(5, min_part=2) )
'Partitions of the integer 5 satisfying constraints min_part=2'
sage: P = Partitions(5, min_part=2)
sage: P.first().parent()
Partitions...
sage: [2,1] in P
False
sage: [2,2,1] in P
False
sage: [3,2] in P
True
sage: Partitions(5, inner=[2,1], min_length=3).list()
[[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]
sage: Partitions(5, inner=Partition([2,2]), min_length=3).list()
[[2, 2, 1]]
sage: Partitions(7, inner=(2, 2), min_length=3).list()
[[4, 2, 1], [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [2, 2, 2, 1], [2, 2, 1, 1, 1]]
sage: Partitions(5, inner=[2,0,0,0,0,0]).list()
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]
sage: Partitions(6, length=2, max_slope=-1).list()
[[5, 1], [4, 2]]
sage: Partitions(length=2, max_slope=-1).list()
Traceback (most recent call last):
...
ValueError: the size must be specified with any keyword argument
sage: Partitions(max_part = 3)
3-Bounded Partitions
Check that trac ticket #14145 has been fixed:
sage: 1 in Partitions()
False
Check trac ticket #15467:
sage: Partitions(5,parts_in=[1,2,3,4], length=4)
Traceback (most recent call last):
...
ValueError: The parameters 'parts_in', 'starting' and 'ending' cannot be combined with anything else.
sage: Partitions(5,starting=[3,2], length=2)
Traceback (most recent call last):
...
ValueError: The parameters 'parts_in', 'starting' and 'ending' cannot be combined with anything else.
sage: Partitions(5,ending=[3,2], length=2)
Traceback (most recent call last):
...
ValueError: The parameters 'parts_in', 'starting' and 'ending' cannot be combined with anything else.
sage: Partitions(NN, length=2)
Traceback (most recent call last):
...
ValueError: the size must be specified with any keyword argument
sage: Partitions(('la','la','laaaa'), max_part=8)
Traceback (most recent call last):
...
ValueError: n must be an integer or be equal to one of None, NN, NonNegativeIntegers()
Check that calling Partitions with outer=a no longer mutates a (trac ticket #16234):
sage: a = [4,2,1,1,1,1,1]
sage: for p in Partitions(8, outer=a, min_slope=-1):
....: print p
....:
[3, 2, 1, 1, 1]
[2, 2, 1, 1, 1, 1]
[2, 1, 1, 1, 1, 1, 1]
sage: a
[4, 2, 1, 1, 1, 1, 1]
Return a partition corresponding to a sequence of beta numbers.
A sequence of beta numbers is a strictly increasing sequence
of non-negative integers. The
corresponding partition
is
given by
. This gives
a bijection from the set of partitions with at most
non-zero parts
to the set of strictly increasing sequences of non-negative integers
of length
.
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]
Returns 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]
TESTS:
sage: Partitions().from_core_and_quotient([2,1], [[2,1],[2,3,1],[1,1,1]]) Traceback (most recent call last): ... ValueError: the quotient [[2, 1], [2, 3, 1], [1, 1, 1]] must be a tuple of partitions
We check that trac ticket #11412 is actually fixed:
sage: test = lambda x, k: x == Partition(core=x.core(k),
... quotient=x.quotient(k))
sage: all(test(mu,k) for k in range(1,5)
... for n in range(10) for mu in Partitions(n))
True
sage: test2 = lambda core, mus: (
... Partition(core=core, quotient=mus).core(mus.level()) == core
... and
... Partition(core=core, quotient=mus).quotient(mus.level()) == mus)
sage: all(test2(core,mus) # long time (5s on sage.math, 2011)
... for k in range(1,10)
... for n_core in range(10-k)
... for core in Partitions(n_core)
... if core.core(k) == core
... for n_mus in range(10-k)
... for mus in PartitionTuples(k,n_mus))
True
Returns a partition from its list of multiplicities.
EXAMPLES:
sage: Partitions().from_exp([2,2,1])
[3, 2, 2, 1, 1]
Returns 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]
Return a partition from its sequence.
The full 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 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]
TESTS:
sage: all(Partitions().from_zero_one(mu.zero_one_sequence()) == mu for n in range(10) for mu in Partitions(n))
True
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 method Partitions.global_options of Partitions and related parent classes.
OPTIONS:
EXAMPLES:
sage: P = Partition([4,2,2,1])
sage: P
[4, 2, 2, 1]
sage: Partitions.global_options(display="exp")
sage: P
1, 2^2, 4
sage: Partitions.global_options(display="exp_high")
sage: P
4, 2^2, 1
It is also possible to use user defined functions for the display and latex options:
sage: Partitions.global_options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P
<4,2,2,1>
sage: Partitions.global_options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P)
\Diagram{4,2,2,1}
sage: Partitions.global_options(display="diagram", diagram_str="#")
sage: P
####
##
##
#
sage: Partitions.global_options(diagram_str="*", convention="french")
sage: print P.ferrers_diagram()
*
**
**
****
Changing the convention for partitions also changes the convention option for tableaux and vice versa:
sage: T = Tableau([[1,2,3],[4,5]])
sage: T.pp()
4 5
1 2 3
sage: Tableaux.global_options(convention="english")
sage: print P.ferrers_diagram()
****
**
**
*
sage: T.pp()
1 2 3
4 5
sage: Partitions.global_options.reset()
See GlobalOptions for more features of these options.
Return self if no arguments are given, otherwise raises a ValueError.
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
Bases: sage.combinat.integer_list.IntegerListsLex, sage.structure.unique_representation.UniqueRepresentation
The class of all (unordered) “restricted” partitions of the integer
having its greatest part equal to the integer
.
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
sage: [1]*10 in PartitionsGreatestEQ(10,2)
False
sage: PartitionsGreatestEQ(10,2).first().parent()
Partitions...
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 method Partitions.global_options of Partitions and related parent classes.
OPTIONS:
EXAMPLES:
sage: P = Partition([4,2,2,1])
sage: P
[4, 2, 2, 1]
sage: Partitions.global_options(display="exp")
sage: P
1, 2^2, 4
sage: Partitions.global_options(display="exp_high")
sage: P
4, 2^2, 1
It is also possible to use user defined functions for the display and latex options:
sage: Partitions.global_options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P
<4,2,2,1>
sage: Partitions.global_options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P)
\Diagram{4,2,2,1}
sage: Partitions.global_options(display="diagram", diagram_str="#")
sage: P
####
##
##
#
sage: Partitions.global_options(diagram_str="*", convention="french")
sage: print P.ferrers_diagram()
*
**
**
****
Changing the convention for partitions also changes the convention option for tableaux and vice versa:
sage: T = Tableau([[1,2,3],[4,5]])
sage: T.pp()
4 5
1 2 3
sage: Tableaux.global_options(convention="english")
sage: print P.ferrers_diagram()
****
**
**
*
sage: T.pp()
1 2 3
4 5
sage: Partitions.global_options.reset()
See GlobalOptions for more features of these options.
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.combinat.integer_list.IntegerListsLex
The class of all (unordered) “restricted” partitions of the integer
having parts less than or equal to the integer
.
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...
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 method Partitions.global_options of Partitions and related parent classes.
OPTIONS:
EXAMPLES:
sage: P = Partition([4,2,2,1])
sage: P
[4, 2, 2, 1]
sage: Partitions.global_options(display="exp")
sage: P
1, 2^2, 4
sage: Partitions.global_options(display="exp_high")
sage: P
4, 2^2, 1
It is also possible to use user defined functions for the display and latex options:
sage: Partitions.global_options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P
<4,2,2,1>
sage: Partitions.global_options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P)
\Diagram{4,2,2,1}
sage: Partitions.global_options(display="diagram", diagram_str="#")
sage: P
####
##
##
#
sage: Partitions.global_options(diagram_str="*", convention="french")
sage: print P.ferrers_diagram()
*
**
**
****
Changing the convention for partitions also changes the convention option for tableaux and vice versa:
sage: T = Tableau([[1,2,3],[4,5]])
sage: T.pp()
4 5
1 2 3
sage: Tableaux.global_options(convention="english")
sage: print P.ferrers_diagram()
****
**
**
*
sage: T.pp()
1 2 3
4 5
sage: Partitions.global_options.reset()
See GlobalOptions for more features of these options.
Bases: sage.combinat.partition.Partitions
All partitions which fit in an 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]]
Return a list of all the partitions inside a box of height and
width
.
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]]
TESTS:
Check trac ticket #10890:
sage: type(PartitionsInBox(0,0)[0])
<class 'sage.combinat.partition.PartitionsInBox_with_category.element_class'>
Bases: sage.combinat.partition.Partitions
Class of all partitions.
TESTS:
sage: TestSuite( sage.combinat.partition.Partitions_all() ).run()
Returns 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
Bases: sage.combinat.partition.Partitions
TESTS:
sage: TestSuite( sage.combinat.partition.Partitions_all_bounded(3) ).run()
Bases: sage.combinat.integer_list.IntegerListsLex
For unpickling old constrained Partitions_constraints objects created with sage <= 3.4.1. See Partitions.
Bases: sage.combinat.partition.Partitions
All partitions with a given ending.
Return the first partition in self.
EXAMPLES:
sage: Partitions(4, ending=[1,1,1,1]).first()
[4]
Return the next partition after part in self.
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
Bases: sage.combinat.partition.Partitions
Partitions of the integer .
TESTS:
sage: TestSuite( sage.combinat.partition.Partitions_n(0) ).run()
sage: TestSuite( sage.combinat.partition.Partitions_n(0) ).run()
Return the number of partitions of the specified size.
INPUT:
It is possible to associate with every partition of the integer a
conjugacy class of permutations in the symmetric group on
points
and vice versa. Therefore the number of partitions
is the number
of conjugacy classes of the symmetric group on
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: Partitions(5).cardinality(algorithm='bober')
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 is given by the reciprocal of
Euler’s function:
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:
Returns the lexicographically first partition of a positive integer
. This is the partition [n].
EXAMPLES:
sage: Partitions(4).first()
[4]
Return the lexicographically last partition of the positive
integer . This is the all-ones partition.
EXAMPLES:
sage: Partitions(4).last()
[1, 1, 1, 1]
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
Return a random partitions of for the specified measure.
INPUT:
EXAMPLES:
sage: Partitions(5).random_element() # random
[2, 1, 1, 1]
sage: Partitions(5).random_element(measure='Plancherel') # random
[2, 1, 1, 1]
Return a random partition of (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]
TESTS:
sage: all(Part.random_element_plancherel() in Part
... for Part in map(Partitions, range(10)))
True
ALGORITHM:
AUTHOR:
Return a random partition of 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]
TESTS:
sage: all(Part.random_element_uniform() in Part
....: for Part in map(Partitions, range(10)))
True
ALGORITHM:
It is a python Implementation of RANDPAR, see [nw]. 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.
REFERENCES:
[nw] | Nijenhuis, Wilf, Combinatorial Algorithms, Academic Press (1978). |
AUTHOR:
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]
Bases: sage.combinat.partition.Partitions
Partitions of the integer of length equal to
.
TESTS:
sage: TestSuite( sage.combinat.partition.Partitions_nk(0,0) ).run()
sage: TestSuite( sage.combinat.partition.Partitions_nk(0,0) ).run()
Return the number of partitions of the specified size with the specified length.
INPUT:
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 of length
is
:
sage: all( Partitions(n, length=2).cardinality()
....: == n // 2 for n in range(10) )
True
The number of partitions of of length
is
for
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
TESTS:
We check the hybrid approach gives the same results as GAP:
sage: N = [0, 1, 2, 3, 5, 10, 20, 500, 850]
sage: K = [0, 1, 2, 3, 5, 10, 11, 20, 21, 250, 499, 500]
sage: all(Partitions(n,length=k).cardinality() == Partitions(n,length=k).cardinality('gap')
....: for n in N for k in K)
True
sage: P = Partitions(4562, length=2800)
sage: P.cardinality() == P.cardinality('gap')
True
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
Bases: sage.combinat.partition.Partitions
Partitions of with parts in a given set
.
This is invoked indirectly when calling Partitions(n, parts_in=parts), where parts is a list of pairwise distinct integers.
TESTS:
sage: TestSuite( sage.combinat.partition.Partitions_parts_in(6, parts=[2,1]) ).run()
Return the number of partitions with parts in self. Wraps GAP’s NrRestrictedPartitions.
EXAMPLES:
sage: Partitions(15, parts_in=[2,3,7]).cardinality()
5
If you can use all parts 1 through , we’d better get
:
sage: Partitions(20, parts_in=[1..20]).cardinality() == Partitions(20).cardinality()
True
TESTS:
Let’s check the consistency of GAP’s function and our own algorithm that actually generates the partitions:
sage: ps = Partitions(15, parts_in=[1,2,3])
sage: ps.cardinality() == len(ps.list())
True
sage: ps = Partitions(15, parts_in=[])
sage: ps.cardinality() == len(ps.list())
True
sage: ps = Partitions(3000, parts_in=[50,100,500,1000])
sage: ps.cardinality() == len(ps.list())
True
sage: ps = Partitions(10, parts_in=[3,6,9])
sage: ps.cardinality() == len(ps.list())
True
sage: ps = Partitions(0, parts_in=[1,2])
sage: ps.cardinality() == len(ps.list())
True
Return the lexicographically first partition of a positive
integer 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]
Return the lexicographically last partition of the positive
integer 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]
TESTS:
sage: Partitions(6, parts_in=[1..6]).last()
[1, 1, 1, 1, 1, 1]
sage: Partitions(0, parts_in=[]).last()
[]
sage: Partitions(50, parts_in=[11,12]).last() is None
True
Bases: sage.combinat.partition.Partitions
All partitions with a given start.
Return the first partition in self.
EXAMPLES:
sage: Partitions(3, starting=[2,1]).first()
[2, 1]
Return the next partition after part in self.
EXAMPLES:
sage: Partitions(3, starting=[2,1]).next(Partition([2,1]))
[1, 1, 1]
This function has been deprecated and will be removed in a future version of Sage; use Partitions with the parts_in keyword. Note, however, that the current implementation of Partitions does not allow the parts_in keyword to be combined with keywords such as max_length; see trac ticket #13072 and trac ticket #12278 for more details. This class should not be removed until this problem has been fixed.
Original docstring follows.
A restricted partition is, like an ordinary partition, an unordered
sum of positive integers and is
represented by the list
, in
nonincreasing order. The difference is that here the
must be elements from the set
, while for ordinary
partitions they may be elements from
.
Returns the list of all restricted partitions of the positive
integer n into sums with summands with the summands of the
partition coming from the set
. If
is not given all restricted
partitions for all
are returned.
Wraps GAP’s RestrictedPartitions.
EXAMPLES:
sage: RestrictedPartitions(5,[3,2,1])
doctest:...: DeprecationWarning: RestrictedPartitions is deprecated; use Partitions with the parts_in keyword instead.
See http://trac.sagemath.org/13072 for details.
doctest:...: DeprecationWarning: RestrictedPartitions_nsk is deprecated; use Partitions with the parts_in keyword instead.
See http://trac.sagemath.org/13072 for details.
Partitions of 5 restricted to the values [1, 2, 3]
sage: RestrictedPartitions(5,[3,2,1]).list()
[[3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
sage: RestrictedPartitions(5,[3,2,1],4)
Partitions of 5 restricted to the values [1, 2, 3] of length 4
sage: RestrictedPartitions(5,[3,2,1],4).list()
[[2, 1, 1, 1]]
Bases: sage.combinat.combinat.CombinatorialClass
We are deprecating RestrictedPartitions(), so this class should be deprecated too. See trac ticket #13072.
Returns the size of self.
Wraps GAP’s NrRestrictedPartitions.
EXAMPLES:
sage: RestrictedPartitions(8,[1,3,5,7]).cardinality()
doctest:...: DeprecationWarning: RestrictedPartitions is deprecated; use Partitions with the parts_in keyword instead.
See http://trac.sagemath.org/13072 for details.
6
sage: RestrictedPartitions(8,[1,3,5,7],2).cardinality()
2
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 method Partitions.global_options of Partitions and related parent classes.
OPTIONS:
EXAMPLES:
sage: P = Partition([4,2,2,1])
sage: P
[4, 2, 2, 1]
sage: Partitions.global_options(display="exp")
sage: P
1, 2^2, 4
sage: Partitions.global_options(display="exp_high")
sage: P
4, 2^2, 1
It is also possible to use user defined functions for the display and latex options:
sage: Partitions.global_options(display=lambda mu: '<%s>' % ','.join('%s'%m for m in mu._list)); P
<4,2,2,1>
sage: Partitions.global_options(latex=lambda mu: '\\Diagram{%s}' % ','.join('%s'%m for m in mu._list)); latex(P)
\Diagram{4,2,2,1}
sage: Partitions.global_options(display="diagram", diagram_str="#")
sage: P
####
##
##
#
sage: Partitions.global_options(diagram_str="*", convention="french")
sage: print P.ferrers_diagram()
*
**
**
****
Changing the convention for partitions also changes the convention option for tableaux and vice versa:
sage: T = Tableau([[1,2,3],[4,5]])
sage: T.pp()
4 5
1 2 3
sage: Tableaux.global_options(convention="english")
sage: print P.ferrers_diagram()
****
**
**
*
sage: T.pp()
1 2 3
4 5
sage: Partitions.global_options.reset()
See GlobalOptions for more features of these options.
Returns the list of all restricted partitions of the positive
integer into sums with
summands with the summands of the
partition coming from the set
. If
is not given all
restricted partitions for all
are returned.
Wraps GAP’s RestrictedPartitions.
EXAMPLES:
sage: RestrictedPartitions(8,[1,3,5,7]).list()
doctest:...: DeprecationWarning: RestrictedPartitions is deprecated; use Partitions with the parts_in keyword instead.
See http://trac.sagemath.org/13072 for details.
[[7, 1], [5, 3], [5, 1, 1, 1], [3, 3, 1, 1], [3, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]]
sage: RestrictedPartitions(8,[1,3,5,7],2).list()
[[7, 1], [5, 3]]
Returns the number of partitions of with, optionally, at most
parts.
The options of number_of_partitions() are being deprecated trac ticket #13072 in favour of Partitions_n.cardinality() so that number_of_partitions() can become a stripped down version of the fastest algorithm available (currently this is using FLINT).
INPUT:
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: number_of_partitions(5, algorithm='bober')
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 is given by the
reciprocal of Euler’s function:
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:
TESTS:
sage: n = 500 + randint(0,500)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1500 + randint(0,1500)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 100000000 + randint(0,100000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 # long time (4s on sage.math, 2011)
True
Return the number of partitions of with length
.
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