# Partitions¶

A partition $$p$$ of a nonnegative integer $$n$$ is at non-increasing list of positive integers (the parts of the partition) with total sum $$n$$.

A partition can be depicted by a diagram made of rows of cells, where the number of cells in the $$i^{th}$$ row starting from the top is the $$i^{th}$$ part of the partition.

The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition $$[5, 3, 1]$$ are $$[[0,4], [1,2], [2,0]]$$.

For display options, see Partitions.global_options.

Note

• Boxes is a synonym for cells. All methods will use ‘cell’ and ‘cells’ instead of ‘box’ and ‘boxes’.
• Partitions are 0 based with coordinates in the form of (row-index, column-index).
• If given coordinates of the form (r, c), then use Python’s *-operator.
• Throughout this documentation, for a partition $$\lambda$$ we will denote its conjugate partition by $$\lambda^{\prime}$$. For more on conjugate partitions, see Partition.conjugate().
• The comparisons on partitions uses lexicographic order.

Note

We use the convention that lexicographic ordering is read from left-to-right. That is to say $$[1, 3, 7]$$ is smaller than $$[2, 3, 4]$$.

AUTHORS:

• Mike Hansen (2007): initial version
• Dan Drake (2009-03-28): deprecate RestrictedPartitions and implement Partitions_parts_in
• Travis Scrimshaw (2012-01-12): Implemented latex function to Partition_class
• Travis Scrimshaw (2012-05-09): Fixed Partitions(-1).list() infinite recursion loop by saying Partitions_n is the empty set.
• Travis Scrimshaw (2012-05-11): Fixed bug in inner where if the length was longer than the length of the inner partition, it would include 0’s.
• Andrew Mathas (2012-06-01): Removed depreciated functions and added compatibility with the PartitionTuple classes. See trac ticket #13072
• Travis Scrimshaw (2012-10-12): Added global options. Made Partition_class to the element Partition. Partitions* are now all in the category framework except PartitionsRestricted (which will eventually be removed). Cleaned up documentation.

EXAMPLES:

There are 5 partitions of the integer 4:

sage: Partitions(4).cardinality()
5
sage: Partitions(4).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]


We can use the method .first() to get the ‘first’ partition of a number:

sage: Partitions(4).first()
[4]


Using the method .next(), 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 to the type of partitions we want. For example, to get all of the partitions of 4 of length 2, we’d do the following:

sage: Partitions(4, length=2).list()
[[3, 1], [2, 2]]


Here is the list of partitions of length at least 2 and the list of ones with length at most 2:

sage: Partitions(4, min_length=2).list()
[[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: Partitions(4, max_length=2).list()
[[4], [3, 1], [2, 2]]


The options min_part and max_part can be used to set constraints on the sizes of all parts. Using max_part, we can select partitions having only ‘small’ entries. The following is the list of the partitions of 4 with parts at most 2:

sage: Partitions(4, max_part=2).list()
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]


The min_part options is complementary to max_part and selects partitions having only ‘large’ parts. Here is the list of all partitions of 4 with each part at least 2:

sage: Partitions(4, min_part=2).list()
[[4], [2, 2]]


The options inner and outer can be used to set part-by-part constraints. This is the list of partitions of 4 with [3, 1, 1] as an outer bound:

sage: Partitions(4, outer=[3,1,1]).list()
[[3, 1], [2, 1, 1]]


outer sets max_length to the length of its argument. Moreover, the parts of outer may be infinite to clear constraints on specific parts. Here is the list of the partitions of 4 of length at most 3 such that the second and third part are 1 when they exist:

sage: Partitions(4, outer=[oo,1,1]).list()
[[4], [3, 1], [2, 1, 1]]


Finally, here are the partitions of 4 with [1,1,1] as an inner bound. Note that inner sets min_length to the length of its argument:

sage: Partitions(4, inner=[1,1,1]).list()
[[2, 1, 1], [1, 1, 1, 1]]


The options min_slope and max_slope can be used to set constraints on the slope, that is on the difference p[i+1]-p[i] of two consecutive parts. Here is the list of the strictly decreasing partitions of 4:

sage: Partitions(4, max_slope=-1).list()
[[4], [3, 1]]


The constraints can be combined together in all reasonable ways. Here are all the partitions of 11 of length between 2 and 4 such that the difference between two consecutive parts is between -3 and -1:

sage: Partitions(11,min_slope=-3,max_slope=-1,min_length=2,max_length=4).list()
[[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]]


Partition objects can also be created individually with Partition:

sage: Partition([2,1])
[2, 1]


Once we have a partition object, then there are a variety of methods that we can use. For example, we can get the conjugate of a partition. Geometrically, the conjugate of a partition is the reflection of that partition through its main diagonal. Of course, this operation is an involution:

sage: Partition([4,1]).conjugate()
[2, 1, 1, 1]
sage: Partition([4,1]).conjugate().conjugate()
[4, 1]


If we create a partition with extra zeros at the end, they will be dropped:

sage: Partition([4,1,0,0])
[4, 1]


The idea of a partition being followed by infinitely many parts of size 0 is consistent with the get_part method:

sage: p = Partition([5, 2])
sage: p.get_part(0)
5
sage: p.get_part(10)
0


We can go back and forth between the 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 coordinates of the corners of a partition:

sage: Partition([4,3,1]).corners()
[(0, 3), (1, 2), (2, 0)]


We can compute the core and quotient of a partition and build the partition back up from them:

sage: Partition([6,3,2,2]).core(3)
[2, 1, 1]
sage: Partition([7,7,5,3,3,3,1]).quotient(3)
([2], [1], [2, 2, 2])
sage: p = Partition([11,5,5,3,2,2,2])
sage: p.core(3)
[]
sage: p.quotient(3)
([2, 1], [4], [1, 1, 1])
sage: Partition(core=[],quotient=([2, 1], [4], [1, 1, 1]))
[11, 5, 5, 3, 2, 2, 2]


We can compute the $$0-1$$ sequence and go back and forth:

sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0])
[5, 4]
sage: all(Partitions().from_zero_one(mu.zero_one_sequence()) == mu for n in range(5) for mu in Partitions(n))
True


We can compute the Frobenius coordinates and go back and forth:

sage: Partition([7,3,1]).frobenius_coordinates()
([6, 1], [2, 0])
sage: Partition(frobenius_coordinates=([6,1],[2,0]))
[7, 3, 1]
sage: all(mu == Partition(frobenius_coordinates=mu.frobenius_coordinates()) for n in range(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

class sage.combinat.partition.OrderedPartitions(n, k)

The class of ordered partitions of $$n$$. If $$k$$ is specified, then this contains only the ordered partitions of length $$k$$.

Note

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

cardinality()

Return the cardinality of self.

EXAMPLES:

sage: OrderedPartitions(3).cardinality()
4
sage: OrderedPartitions(3,2).cardinality()
2

list()

Return a list of partitions in self.

EXAMPLES:

sage: OrderedPartitions(3).list()
[[3], [2, 1], [1, 2], [1, 1, 1]]
sage: OrderedPartitions(3,2).list()
[[2, 1], [1, 2]]

sage.combinat.partition.OrderedPartitions_nk(n, k)

For unpickling OrderedPartitions_nk objects created before trac ticket #13605. See OrderedPartitions.

EXAMPLES:

sage: sage.combinat.partition.OrderedPartitions_nk(3, 2)
doctest:1: DeprecationWarning: this class is deprecated. Use OrderedPartitions instead
See http://trac.sagemath.org/13605 for details.
Ordered partitions of 3 of length 2

class sage.combinat.partition.Partition(parent, mu)

A partition $$p$$ of a nonnegative integer $$n$$ is a non-increasing list of positive integers (the parts of the partition) with total sum $$n$$.

A partition is often representation by a diagram consisting of cells, or boxes, placed in rows on top of each other with the number of cells in the $$i^{th}$$ row, reading from top to bottom, is the $$i^{th}$$ part of the partition.

The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition [5, 3, 1] are [[0,4], [1,2], [2,0]].

For display options, see Partitions.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:

• a list (the default)
• using exponential notation
• by Frobenius coordinates
• specifying its $$0-1$$ sequence
• specifying the core and the quotient

See the examples below.

EXAMPLES:

Creating partitions though parents:

sage: mu = Partitions(8)([3,2,1,1,1]); mu
[3, 2, 1, 1, 1]
sage: nu = Partition([3,2,1,1,1]); nu
[3, 2, 1, 1, 1]
sage: mu == nu
True
sage: mu is nu
False
sage: mu in Partitions()
True
sage: mu.parent()
Partitions of the integer 8
sage: mu.size()
8
sage: mu.category()
Category of elements of Partitions of the integer 8
sage: nu.parent()
Partitions
sage: nu.category()
Category of elements of Partitions
sage: mu[0]
3
sage: mu[1]
2
sage: mu[2]
1
sage: mu.pp()
***
**
*
*
*
sage: mu.removable_cells()
[(0, 2), (1, 1), (4, 0)]
sage: mu.down_list()
[[2, 2, 1, 1, 1], [3, 1, 1, 1, 1], [3, 2, 1, 1]]
[(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)
[[]]
[[2]]
[[2, 2, 2], [3, 2, 1], [4, 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)
[[]]
[[1, 1]]
[[3, 3], [3, 2, 1], [2, 2, 1, 1]]
[[4, 3, 2], [4, 2, 2, 1], [3, 3, 3], [3, 3, 2, 1], [3, 2, 2, 1, 1]]


Return a list of the positions where we can add a cell so that the shape is still a partition. Indices are of the form $$(i,j)$$.

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

arm_cells(i, j)

Return the list of the cells of the arm of cell $$(i,j)$$ in self.

The arm of cell $$c = (i,j)$$ is the boxes that appear to the right of $$c$$.

INPUT:

• i, j – two integers

OUTPUT:

A list of pairs of integers

EXAMPLES:

sage: Partition([4,4,3,1]).arm_cells(1,1)
[(1, 2), (1, 3)]

sage: Partition([]).arm_cells(0,0)
Traceback (most recent call last):
...
ValueError: The cell is not in the diagram

arm_length(i, j)

Return the length of the arm of cell $$(i,j)$$ in self.

The arm of cell $$(i,j)$$ is the cells that appear to the right of cell $$(i,j)$$.

INPUT:

• i, j – two integers

OUTPUT:

An integer or a ValueError

EXAMPLES:

sage: p = Partition([2,2,1])
sage: p.arm_length(0, 0)
1
sage: p.arm_length(0, 1)
0
sage: p.arm_length(2, 0)
0
sage: Partition([3,3]).arm_length(0, 0)
2
sage: Partition([3,3]).arm_length(*[0,0])
2

arm_lengths(flat=False)

Return a tableau of shape self where each cell is filled 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]

arms_legs_coeff(i, j)

This is a statistic on a cell $$c = (i,j)$$ in the diagram of partition $$p$$ given by

$\frac{ 1 - q^a * t^{\ell + 1} }{ 1 - q^{a + 1} * t^{\ell} }$

where $$a$$ is the arm length of $$c$$ and $$\ell$$ is the leg length of $$c$$.

EXAMPLES:

sage: Partition([3,2,1]).arms_legs_coeff(1,1)
(-t + 1)/(-q + 1)
sage: Partition([3,2,1]).arms_legs_coeff(0,0)
(-q^2*t^3 + 1)/(-q^3*t^2 + 1)
sage: Partition([3,2,1]).arms_legs_coeff(*[0,0])
(-q^2*t^3 + 1)/(-q^3*t^2 + 1)

atom()

Return a list of the standard tableaux of size self.size() whose atom is equal 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]]]

aut()

Return a factor for the number of permutations with cycle type self.

This method returns $$1^{j_1}j_1! \cdots n^{j_n}j_n!$$ where $$j_k$$ is the number of parts in self equal to $$k$$.

The number of permutations having self as a cycle type is given by

$\frac{n!}{1^{j_1}j_1! \cdots n^{j_n}j_n!} .$

EXAMPLES:

sage: Partition([2,1]).aut()
2

beta_numbers(length=None)

Return the set of beta numbers corresponding to self.

The optional argument length specifies the length of the beta set (which must be at least the length 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]

cells()

Return the coordinates of the cells of self.

EXAMPLES:

sage: Partition([2,2]).cells()
[(0, 0), (0, 1), (1, 0), (1, 1)]
sage: Partition([3,2]).cells()
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)]

centralizer_size(t=0, q=0)

Return the size of the centralizer of any permutation of cycle type self.

If $$m_i$$ is the multiplicity of $$i$$ as a part of $$p$$, this is given by

$\prod_i m_i! i^{m_i}.$

Including the optional parameters $$t$$ and $$q$$ gives the $$q - t$$ analog which is the former product times

$\prod_{i=1}^{\mathrm{length}(p)} \frac{1 - q^{p_i}}{1 - t^{p_i}}.$

See [Ker].

EXAMPLES:

sage: Partition([2,2,1]).centralizer_size()
8
sage: Partition([2,2,2]).centralizer_size()
48

character_polynomial()

Return the character polynomial associated to the partition self.

The character polynomial $$q_\mu$$ is defined by

$q_\mu(x_1, x_2, \ldots, x_k) = \downarrow \sum_{\alpha \vdash k} \frac{ \chi^\mu_\alpha }{1^{a_1}2^{a_2}\cdots k^{a_k}a_1!a_2!\cdots a_k!} \prod_{i=1}^{k} (ix_i-1)^{a_i}$

where $$a_i$$ is the multiplicity of $$i$$ in $$\alpha$$.

It is computed in the following manner:

1. Expand the Schur function $$s_\mu$$ in the power-sum basis,
2. Replace each $$p_i$$ with $$ix_i-1$$,
3. Apply the umbral operator $$\downarrow$$ to the resulting polynomial.

EXAMPLES:

sage: Partition([1]).character_polynomial()
x - 1
sage: Partition([1,1]).character_polynomial()
1/2*x0^2 - 3/2*x0 - x1 + 1
sage: Partition([2,1]).character_polynomial()
1/3*x0^3 - 2*x0^2 + 8/3*x0 - x2

components()

Return a list containing the shape of self.

This method exists only for compatibility with PartitionTuples.

EXAMPLES:

sage: Partition([3,2]).components()
[[3, 2]]

conjugacy_class_size()

Return the size of the conjugacy class of the symmetric group indexed by self.

EXAMPLES:

sage: Partition([2,2,2]).conjugacy_class_size()
15
sage: Partition([2,2,1]).conjugacy_class_size()
15
sage: Partition([2,1,1]).conjugacy_class_size()
6


REFERENCES:

 [Ker] Kerber, A. ‘Algebraic Combinatorics via Finite Group Action’ 1.3 p24
conjugate(*args, **kwds)

Return the conjugate partition of the partition self. This is also called the associated partition or the transpose in the literature.

EXAMPLES:

sage: Partition([2,2]).conjugate()
[2, 2]
sage: Partition([6,3,1]).conjugate()
[3, 2, 2, 1, 1, 1]


The conjugate partition is obtained by transposing the Ferrers diagram of the partition (see ferrers_diagram()):

sage: print Partition([6,3,1]).ferrers_diagram()
******
***
*
sage: print Partition([6,3,1]).conjugate().ferrers_diagram()
***
**
**
*
*
*

contains(x)

Return True 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

content(r, c, multicharge=[0])

Return the content of the cell at row $$r$$ and column $$c$$.

The content of a cell is $$c - r$$.

For consistency with partition tuples there is also an optional multicharge argument which is an offset to the usual content. By setting the multicharge equal to the 0-element the ring $$\ZZ/e\ZZ$$ the corresponding $$e$$-residue will be returned. This is the content modulo $$e$$.

The content (and residue) do not strictly depend on the partition, however, this method is included because it is often useful in the context of partitions.

EXAMPLES:

sage: Partition([2,1]).content(1,0)
-1
sage: p = Partition([3,2])
sage: sum([p.content(*c) for c in p.cells()])
2


and now we return the 3-residue of a cell:

sage: Partition([2,1]).content(1,0, multicharge=[IntegerModRing(3)(0)])
2

core(length)

Return the core of the partition – in the literature the core is commonly referred to as the $$k$$-core, $$p$$-core, $$r$$-core, ... . The construction of the core can be visualized by repeatedly removing border strips of size $$r$$ from self 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)
[]

corners()

Return a list of the corners of the partitions. These are the positions where we can remove a cell. Indices are of the form $$(i,j)$$.

EXAMPLES:

sage: Partition([3,2,1]).corners()
[(0, 2), (1, 1), (2, 0)]
sage: Partition([3,3,1]).corners()
[(1, 2), (2, 0)]

dimension(smaller=[], k=1)

This function computes the number of paths from the smaller partition to the partition self, where each step consists of adding a $$k$$-ribbon while keeping a partition.

Note that a 1-ribbon is just a single cell, so this gives path lengths in the Young graph when $$k = 1$$.

Note also that the defaut case ($$k = 1$$ and smaller = []) gives the dimension of characters of the symmetric groups.

INPUT:

• smaller – a partition (default: an empty list [])
• $$k$$ – a positive integer (default: 1)

OUTPUT:

The number of such paths

EXAMPLES:

Looks at the number of ways of getting from [5,4] to the empty partition, removing one cell at a time:

sage: mu = Partition([5,4])
sage: mu.dimension()
42


Same, but removing one 3-ribbon at a time. Note that the 3-core of mu is empty:

sage: mu.dimension(k=3)
3


The 2-core of mu is not the empty partition:

sage: mu.dimension(k=2)
0


Indeed, the 2-core of mu is [1]:

sage: mu.dimension(Partition([1]),k=2)
2


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 $$k$$-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 $$k=1$$ and smaller is empty, this function uses the hook formula. When $$k=1$$ and smaller is not empty, it uses a formula from [ORV].

When $$k \neq 1$$, we first check that both self and smaller have the same $$k$$-core, then use the $$k$$-quotients and the same algorithm on each of the $$k$$-quotients.

REFERENCES:

 [ORV] Olshanski, Regev, Vershik, “Frobenius-Schur functions”

AUTHORS:

• Paul-Olivier Dehaye (2011-06-07)
dominate(rows=None)

Old name for dominated_partitions().

EXAMPLES:

sage: Partition([3,2,1]).dominate()
doctest:1: DeprecationWarning: dominate is deprecated. Use dominated_partitions instead.
See http://trac.sagemath.org/13605 for details.
[[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]]

dominated_partitions(rows=None)

Return a list of the partitions dominated by $$n$$. If rows is specified, then it only returns the ones which has number of rows equal to 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]]

dominates(p2)

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

down()

Return a generator for partitions that can be obtained from self by removing a cell.

EXAMPLES:

sage: [p for p in Partition([2,1,1]).down()]
[[1, 1, 1], [2, 1]]
sage: [p for p in Partition([3,2]).down()]
[[2, 2], [3, 1]]
sage: [p for p in Partition([3,2,1]).down()]
[[2, 2, 1], [3, 1, 1], [3, 2]]


TESTS:

We check that trac ticket #11435 is fixed:

sage: Partition([]).down_list() #indirect doctest
[]

down_list()

Return a list of the partitions that can be obtained from self by removing a cell.

EXAMPLES:

sage: Partition([2,1,1]).down_list()
[[1, 1, 1], [2, 1]]
sage: Partition([3,2]).down_list()
[[2, 2], [3, 1]]
sage: Partition([3,2,1]).down_list()
[[2, 2, 1], [3, 1, 1], [3, 2]]
sage: Partition([]).down_list()  #checks :trac:11435
[]

evaluation()

Return the evaluation of self.

The commutative evaluation, often shortened to evaluation, of a word (we think of a partition as a word in $$\{0, 1, 2, \ldots\}$$) is its image in the free commutative monoid. In other words, this counts how many occurrances there are of each letter.

This is also is known as Parikh vector and abelianization and has the same output as to_exp().

EXAMPLES:

sage: Partition([4,3,1,1]).evaluation()
[2, 0, 1, 1]

ferrers_diagram()

Return the Ferrers diagram of self.

EXAMPLES:

sage: mu=Partition([5,5,2,1])
sage: Partitions.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: Partitions.global_options.reset()

frobenius_coordinates()

Return a pair of sequences of Frobenius coordinates aka beta numbers of the partition.

These are two strictly decreasing sequences of nonnegative integers of the same length.

EXAMPLES:

sage: Partition([]).frobenius_coordinates()
([], [])
sage: Partition([1]).frobenius_coordinates()
([0], [0])
sage: Partition([3,3,3]).frobenius_coordinates()
([2, 1, 0], [2, 1, 0])
sage: Partition([9,1,1,1,1,1,1]).frobenius_coordinates()
([8], [6])

frobenius_rank()

Return the Frobenius rank of the partition.

The Frobenius rank is the number of cells on the main diagonal.

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

from_kbounded_to_grassmannian(k)

Maps a $$k$$-bounded partition to a Grassmannian element in the affine Weyl group of type $$A_k^{(1)}$$.

For details, see the documentation of the method from_kbounded_to_reduced_word() .

EXAMPLES:

sage: p=Partition([2,1,1])
sage: p.from_kbounded_to_grassmannian(2)
[-1  1  1]
[-2  2  1]
[-2  1  2]
sage: p=Partition([])
sage: p.from_kbounded_to_grassmannian(2)
[1 0 0]
[0 1 0]
[0 0 1]

from_kbounded_to_reduced_word(k)

Maps a $$k$$-bounded partition to a reduced word for an element in the affine permutation group.

This uses the fact that there is a bijection between $$k$$-bounded partitions and $$(k+1)$$-cores and an action of the affine nilCoxeter algebra of type $$A_k^{(1)}$$ on $$(k+1)$$-cores as described in [LM2006].

REFERENCES:

 [LM2006] MR2167475 (2006j:05214) L. Lapointe, J. Morse. Tableaux on $$k+1$$-cores, reduced words for affine permutations, and $$k$$-Schur expansions. J. Combin. Theory Ser. A 112 (2005), no. 1, 44–81.

EXAMPLES:

sage: p=Partition([2,1,1])
sage: p.from_kbounded_to_reduced_word(2)
[2, 1, 2, 0]
sage: p=Partition([3,1])
sage: p.from_kbounded_to_reduced_word(3)
[3, 2, 1, 0]
sage: p.from_kbounded_to_reduced_word(2)
Traceback (most recent call last):
...
ValueError: the partition must be 2-bounded
sage: p=Partition([])
sage: p.from_kbounded_to_reduced_word(2)
[]

garnir_tableau(*cell)

Return the Garnir tableau of shape self corresponding to the cell cell. If cell $$= (a,c)$$ then $$(a+1,c)$$ 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 $$(a,c)$$ is a cell in the Young diagram of a partition, which is not at the bottom of its column, then the corresponding Garnir tableau has the integers $$1, 2, \ldots, n$$ entered in order from left to right along the rows of the diagram up to the cell $$(a,c-1)$$, then along the cells $$(a+1,1)$$ to $$(a+1,c)$$, then $$(a,c)$$ until the end of row $$a$$ and then continuing from left to right in the remaining positions. The examples below probably make this clearer!

Note

The function also sets g._garnir_cell, 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


generalized_pochhammer_symbol(a, alpha)

Return the generalized Pochhammer symbol $$(a)_{self}^{(\alpha)}$$. This is the product over all cells $$(i,j)$$ in self of $$a - (i-1) / \alpha + j - 1$$.

EXAMPLES:

sage: Partition([2,2]).generalized_pochhammer_symbol(2,1)
12

get_part(i, default=0)

Return the $$i^{th}$$ part of self, 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

hook_length(i, j)

Return the length of the hook of cell $$(i,j)$$ in self.

The hook of cell $$(i,j)$$ of a partition $$\lambda$$ is

$\lambda + \lambda^{\prime} - i - j + 1$

where $$\lambda^{\prime}$$ is the conjugate partition. In English convention, the hook length is the number cells to the right and below the cell $$(i,j)$$ (including that cell).

EXAMPLES:

sage: p = Partition([2,2,1])
sage: p.hook_length(0, 0)
4
sage: p.hook_length(0, 1)
2
sage: p.hook_length(2, 0)
1
sage: Partition([3,3]).hook_length(0, 0)
4
sage: cell = [0,0]; Partition([3,3]).hook_length(*cell)
4

hook_lengths()

Return a tableau of shape self with the cells filled in with the hook lengths.

In each cell, put the sum of one plus the number of cells horizontally to the right and vertically below the cell (the hook length).

For example, consider the partition [3,2,1] of 6 with Ferrers diagram:

# # #
# #
#


When we fill in the cells with the hook lengths, we obtain:

5 3 1
3 1
1

EXAMPLES:

sage: Partition([2,2,1]).hook_lengths()
[[4, 2], [3, 1], [1]]
sage: Partition([3,3]).hook_lengths()
[[4, 3, 2], [3, 2, 1]]
sage: Partition([3,2,1]).hook_lengths()
[[5, 3, 1], [3, 1], [1]]
sage: Partition([2,2]).hook_lengths()
[[3, 2], [2, 1]]
sage: Partition([5]).hook_lengths()
[[5, 4, 3, 2, 1]]


REFERENCES:

hook_polynomial(q, t)

Return the two-variable hook polynomial.

EXAMPLES:

sage: R.<q,t> = PolynomialRing(QQ)
sage: a = Partition([2,2]).hook_polynomial(q,t)
sage: a == (1 - t)*(1 - q*t)*(1 - t^2)*(1 - q*t^2)
True
sage: a = Partition([3,2,1]).hook_polynomial(q,t)
sage: a == (1 - t)^3*(1 - q*t^2)^2*(1 - q^2*t^3)
True

hook_product(a)

Return the Jack hook-product.

EXAMPLES:

sage: Partition([3,2,1]).hook_product(x)
(2*x + 3)*(x + 2)^2
sage: Partition([2,2]).hook_product(x)
2*(x + 2)*(x + 1)

hooks()

Return a sorted list of the hook lengths in self.

EXAMPLES:

sage: Partition([3,2,1]).hooks()
[5, 3, 3, 1, 1, 1]

initial_tableau(*args, **kwds)

Return the standard tableau which has the numbers $$1, 2, \ldots, n$$ where $$n$$ 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]]

inside_corners()

Return a list of the corners of the partitions. These are the positions where we can remove a cell. Indices are of the form $$(i,j)$$.

EXAMPLES:

sage: Partition([3,2,1]).corners()
[(0, 2), (1, 1), (2, 0)]
sage: Partition([3,3,1]).corners()
[(1, 2), (2, 0)]

is_core(k)

Tests whether the partition is a $$k$$-core or not. Visuallly, this can be checked by trying to remove border strips of size $$k$$ from self. If this is not possible, then self is a $$k$$-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

is_empty()

Return True if self is the empty partition.

EXAMPLES:

sage: Partition([]).is_empty()
True
sage: Partition([2,1,1]).is_empty()
False

jacobi_trudi()

Return the Jacobi-Trudi polynomial 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]

k_atom(k)

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

k_boundary(k)

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]

k_conjugate(k)

Return the k-conjugate of self.

The $$k$$-conjugate is the partition that is given by the columns of the $$k$$-skew diagram of the partition.

We can also define the $$k$$-conjugate in the following way. Let $$P$$ denote the bijection from $$(k+1)$$-cores to $$k$$-bounded partitions. The $$k$$-conjugate of a $$(k+1)$$-core $$\lambda$$ is

$\lambda^{(k)} = P^{-1}\left( (P(\lambda))^{\prime} \right).$

EXAMPLES:

sage: p = Partition([4,3,2,2,1,1])
sage: p.k_conjugate(4)
[3, 2, 2, 1, 1, 1, 1, 1, 1]

k_interior(k)

Return the partition consisting of the cells of self, whose hook lengths are greater 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)
[]

k_irreducible(k)

Return the partition with all $$r \times (k+1-r)$$ rectangles removed.

If self is a $$k$$-bounded partition, then this method will return the partition where all rectangles of dimension $$r \times (k+1-r)$$ for $$1 \leq r \leq k$$ have been deleted.

If self is not a $$k$$-bounded partition then the method will raise an error.

INPUT:

• k – a non-negative integer

OUTPUT:

• a partition

EXAMPLES:

sage: Partition([3,2,2,1,1,1]).k_irreducible(4)
[3, 2, 2, 1, 1, 1]
sage: Partition([3,2,2,1,1,1]).k_irreducible(3)
[]
sage: Partition([3,3,3,2,2,2,2,2,1,1,1,1]).k_irreducible(3)
[2, 1]

k_skew(k)

Return the $$k$$-skew partition.

The $$k$$-skew diagram of a $$k$$-bounded partition is the skew diagram denoted $$\lambda/^k$$ satisfying the conditions:

1. row $$i$$ of $$\lambda/^k$$ has length $$\lambda_i$$,
2. no cell in $$\lambda/^k$$ has hook-length exceeding $$k$$,
3. every square above the diagram of $$\lambda/^k$$ has hook length exceeding $$k$$.

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]

k_split(k)

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

larger_lex(rhs)

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

leg_cells(i, j)

Return the list of the cells of the leg of cell $$(i,j)$$ in self.

The leg of cell $$c = (i,j)$$ is defined to be the cells below $$c$$ (in English convention).

INPUT:

• i, j – two integers

OUTPUT:

A list of pairs of integers

EXAMPLES:

sage: Partition([4,4,3,1]).leg_cells(1,1)
[(2, 1)]
sage: Partition([4,4,3,1]).leg_cells(0,1)
[(1, 1), (2, 1)]

sage: Partition([]).leg_cells(0,0)
Traceback (most recent call last):
...
ValueError: The cell is not in the diagram

leg_length(i, j)

Return the length of the leg of cell $$(i,j)$$ in self.

The leg of cell $$c = (i,j)$$ is defined to be the cells below $$c$$ (in English convention).

INPUT:

• i, j – two integers

OUTPUT:

An integer or a ValueError

EXAMPLES:

sage: p = Partition([2,2,1])
sage: p.leg_length(0, 0)
2
sage: p.leg_length(0,1)
1
sage: p.leg_length(2,0)
0
sage: Partition([3,3]).leg_length(0, 0)
1
sage: cell = [0,0]; Partition([3,3]).leg_length(*cell)
1

leg_lengths(flat=False)

Return a tableau of shape self with each cell filled in with its leg length. The optional boolean 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]

length()

Return the number of parts in self.

EXAMPLES:

sage: Partition([3,2]).length()
2
sage: Partition([2,2,1]).length()
3
sage: Partition([]).length()
0

level()

Return the level of self, which is always 1.

This method exists only for compatibility with PartitionTuples.

EXAMPLE:

sage: Partition([4,3,2]).level()
1

lower_hook(i, j, alpha)

Return the lower hook length of the cell $$(i,j)$$ in self. When alpha = 1, this is just the normal hook length.

The lower hook length of a cell $$(i,j)$$ in a partition $$\kappa$$ is defined by

$h_*^\kappa(i,j) = \kappa_j^\prime-i+1+\alpha(\kappa_i - j).$

EXAMPLES:

sage: p = Partition([2,1])
sage: p.lower_hook(0,0,1)
3
sage: p.hook_length(0,0)
3
sage: [ p.lower_hook(i,j,x) for i,j in p.cells() ]
[x + 2, 1, 1]

lower_hook_lengths(alpha)

Return a tableau of shape self with the cells filled in with the lower hook lengths. When alpha = 1, these are just the normal hook lengths.

The lower hook length of a cell $$(i,j)$$ in a partition $$\kappa$$ is defined by

$h_\kappa^*(i,j) = \kappa_j^\prime-i+\alpha(\kappa_i - j + 1).$

EXAMPLES:

sage: Partition([3,2,1]).lower_hook_lengths(x)
[[2*x + 3, x + 2, 1], [x + 2, 1], [1]]
sage: Partition([3,2,1]).lower_hook_lengths(1)
[[5, 3, 1], [3, 1], [1]]
sage: Partition([3,2,1]).hook_lengths()
[[5, 3, 1], [3, 1], [1]]

next()

Return the partition that lexicographically follows self. If self is the last partition, then return False.

EXAMPLES:

sage: Partition([4]).next()
[3, 1]
sage: Partition([1,1,1,1]).next()
False

outer_rim()

Return the outer rim of self.

The outer rim of a partition $$\lambda$$ is defined as the cells which do not belong to $$\lambda$$ and which are adjacent to cells in $$\lambda$$.

EXAMPLES:

The outer rim of the partition $$[4,1]$$ consists of the cells marked with # below:

****#
*####
##
sage: Partition([4,1]).outer_rim()
[(2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)]

sage: Partition([2,2,1]).outer_rim()
[(3, 0), (3, 1), (2, 1), (2, 2), (1, 2), (0, 2)]
sage: Partition([2,2]).outer_rim()
[(2, 0), (2, 1), (2, 2), (1, 2), (0, 2)]
sage: Partition([6,3,3,1,1]).outer_rim()
[(5, 0), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 4), (1, 5), (1, 6), (0, 6)]
sage: Partition([]).outer_rim()
[(0, 0)]

outline(variable=x)

Return the outline of the partition self.

This is a piecewise linear function, normalized so that the area under the partition [1] is 2.

INPUT:

• variable – a variable (default: 'x' in the symbolic ring)

EXAMPLES:

sage: [Partition([5,4]).outline()(x=i) for i in range(-10,11)]
[10, 9, 8, 7, 6, 5, 6, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 10]

sage: Partition([]).outline()
abs(x)

sage: Partition([1]).outline()
abs(x + 1) + abs(x - 1) - abs(x)

sage: y=sage.symbolic.ring.var("y")
sage: Partition([6,5,1]).outline(variable=y)
abs(y + 6) - abs(y + 5) + abs(y + 4) - abs(y + 3) + abs(y - 1) - abs(y - 2) + abs(y - 3)


TESTS:

sage: integrate(Partition([1]).outline()-abs(x),(x,-10,10))
2

outside_corners()

Return a list of the positions where we can add a cell so that the shape is still a partition. Indices are of the form $$(i,j)$$.

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

plancherel_measure()

Return the probability of self under the Plancherel probability measure on partitions of the same size.

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

power(k)

Returns the cycle type of the $$k$$-th power of any permutation with cycle type self (thus describes the powermap of symmetric groups).

Wraps 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]
sage: Partition([3,2,1]).power(3)
[2, 1, 1, 1, 1]


Now let us compare this to the power map on $$S_8$$:

sage: G = SymmetricGroup(8)
sage: g = G([(1,2,3,4,5),(6,7,8)])
sage: g
(1,2,3,4,5)(6,7,8)
sage: g^2
(1,3,5,2,4)(6,8,7)
sage: g^3
(1,4,2,5,3)
sage: g^4
(1,5,4,3,2)(6,7,8)

pp()

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

quotient(length)

Return the quotient of the partition – in the literature the core is commonly referred to as the $$k$$-core, $$p$$-core, $$r$$-core, ... . The quotient is a list of $$r$$ partitions, constructed in the following way. Label each cell in $$p$$ with its content, modulo $$r$$. Let $$R_i$$ be the set of rows ending in a cell labelled $$i$$, and $$C_i$$ be the set of columns ending in a cell labelled $$i$$. Then the $$j$$-th component of the quotient of $$p$$ is the partition defined by intersecting $$R_j$$ with $$C_j+1$$.

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 $$T$$ labeled down (in English convention) each column to the shape of self.

For an example of the tableau $$T$$, consider the partition $$\lambda = (3,2,1)$$, then we have:

1 4 6
2 5
3

For more, see RSK().

EXAMPLES:

sage: Partition([3,2,1]).reading_tableau()
[[1, 3, 6], [2, 5], [4]]

removable_cells()

Return a list of the corners of the partitions. These are the positions where we can remove a cell. Indices are of the form $$(i,j)$$.

EXAMPLES:

sage: Partition([3,2,1]).corners()
[(0, 2), (1, 1), (2, 0)]
sage: Partition([3,3,1]).corners()
[(1, 2), (2, 0)]

remove_cell(i, j=None)

Return the partition obtained by removing a cell at the end of row i.

EXAMPLES:

sage: Partition([2,2]).remove_cell(1)
[2, 1]
sage: Partition([2,2,1]).remove_cell(2)
[2, 2]
sage: #Partition([2,2]).remove_cell(0)

sage: Partition([2,2]).remove_cell(1,1)
[2, 1]
sage: #Partition([2,2]).remove_cell(1,0)

remove_horizontal_border_strip(k)

Return the partitions obtained from self by removing an horizontal border strip of 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()
[]

rim()

Return the rim of self.

The rim of a partition $$\lambda$$ is defined as the cells which belong to $$\lambda$$ and which are adjacent to cells not in $$\lambda$$.

EXAMPLES:

The rim of the partition $$[5,5,2,1]$$ consists of the cells marked with # below:

****#
*####
##
#

sage: Partition([5,5,2,1]).rim()
[(3, 0), (2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)]

sage: Partition([2,2,1]).rim()
[(2, 0), (1, 0), (1, 1), (0, 1)]
sage: Partition([2,2]).rim()
[(1, 0), (1, 1), (0, 1)]
sage: Partition([6,3,3,1,1]).rim()
[(4, 0), (3, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4), (0, 5)]
sage: Partition([]).rim()
[]
sign()

Return the sign of any permutation with cycle type self.

This function corresponds to a homomorphism from the symmetric group $$S_n$$ into the cyclic group of order 2, whose kernel is exactly the alternating group $$A_n$$. Partitions of sign $$1$$ are called even partitions while partitions of sign $$-1$$ are called odd.

EXAMPLES:

sage: Partition([5,3]).sign()
1
sage: Partition([5,2]).sign()
-1


Zolotarev’s lemma states that the Legendre symbol $$\left(\frac{a}{p}\right)$$ for an integer $$a \pmod p$$ ($$p$$ a prime number), can be computed as sign(p_a), where sign denotes the sign of a permutation and p_a the permutation of the residue classes $$\pmod p$$ induced by modular multiplication by $$a$$, provided $$p$$ does not divide $$a$$.

We verify this in some examples.

sage: F = GF(11)
sage: a = F.multiplicative_generator();a
2
sage: plist = [int(a*F(x)) for x in range(1,11)]; plist
[2, 4, 6, 8, 10, 1, 3, 5, 7, 9]


This corresponds to the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6) (acting the set $$\{1,2,...,10\}$$) and to the partition [10].

sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)')
sage: p.sign()
-1
sage: Partition([10]).sign()
-1
sage: kronecker_symbol(11,2)
-1


Now replace $$2$$ by $$3$$:

sage: plist = [int(F(3*x)) for x in range(1,11)]; plist
[3, 6, 9, 1, 4, 7, 10, 2, 5, 8]
sage: 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:

Wikipedia article Zolotarev’s_lemma

size()

Return the size of self.

EXAMPLES:

sage: Partition([2,2]).size()
4
sage: Partition([3,2,1]).size()
6

standard_tableaux()

Return the standard tableaux of this shape.

EXAMPLE:

sage: Partition([3,2,2,1]).standard_tableaux()
Standard tableaux of shape [3, 2, 2, 1]

suter_diagonal_slide(n, exp=1)

Return the image of self in $$Y_n$$ under Suter’s diagonal slide $$\sigma_n$$, where the notations used are those defined in [Sut2002].

The set $$Y_n$$ is defined as the set of all partitions $$\lambda$$ such that the hook length of the $$(0, 0)$$-cell (i.e. the northwestern most cell in English notation) of $$\lambda$$ is less than $$n$$, including the empty partition.

The map $$\sigma_n$$ sends a partition (with non-zero entries) $$(\lambda_1, \lambda_2, \ldots, \lambda_m) \in Y_n$$ to the partition $$(\lambda_2 + 1, \lambda_3 + 1, \ldots, \lambda_m + 1, \underbrace{1, 1, \ldots, 1}_{n - m - \lambda_1\text{ ones}})$$. In other words, it pads the partition with trailing zeroes until it has length $$n - \lambda_1$$, then removes its first part, and finally adds $$1$$ to each part.

By Theorem 2.1 of [Sut2002], the dihedral group $$D_n$$ with $$2n$$ elements acts on $$Y_n$$ by letting the primitive rotation act as $$\sigma_n$$ and the reflection act as conjugation of partitions (conjugate()). This action is faithful if $$n \geq 3$$.

Note

There are two non-equivalent definitions for $$\sigma_n$$ in [Sut2002]. Here are using the formulaic one, not the one using the four steps which actually defines $$\sigma_n^{-1}$$ instead.

INPUT:

• n – nonnegative integer
• exp – (default: 1) how many times $$\sigma_n$$ should be applied

OUTPUT:

The result of applying Suter’s diagonal slide $$\sigma_n$$ to self, assuming that self lies in $$Y_n$$. If the optional argument exp is set, then the slide $$\sigma_n$$ 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 $$\sigma_n\bigl( \sigma_n( \lambda^{\prime})^{\prime} \bigr) = \lambda$$:

sage: all( p.suter_diagonal_slide(8).conjugate()
....:      == p.conjugate().suter_diagonal_slide(8, exp=-1)
....:      for p in P7 )
True


Check of Claim 1 in [Sut2002]:

sage: P5 = Partitions(5)
sage: all( all( (p.suter_diagonal_slide(6) in q.suter_diagonal_slide(6).down())
....:           or (q.suter_diagonal_slide(6) in p.suter_diagonal_slide(6).down())
....:           for p in q.down() )
....:      for q in P5 )
True


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, 5) Ruedi Suter. Young’s Lattice and Dihedral Symmetries. Europ. J. Combinatorics (2002) 23, 233–238. http://www.sciencedirect.com/science/article/pii/S0195669801905414
to_core(k)

Maps the $$k$$-bounded partition self to its corresponding $$k+1$$-core.

EXAMPLES:

sage: p = Partition([4,3,2,2,1,1])
sage: c = p.to_core(4); c
[9, 5, 3, 2, 1, 1]
sage: type(c)
<class 'sage.combinat.core.Cores_length_with_category.element_class'>
sage: c.to_bounded_partition() == p
True

to_dyck_word(*args, **kwds)

Returns the smallest Dyck word whose corresponding partition is self. This corresponds to the unique Dyck path whose complement is the partition is self for which the partition touches the diagonal.

EXAMPLES:

sage: Partition([2,2]).to_dyck_word()
[1, 1, 0, 0, 1, 1, 0, 0]
sage: Partition([6,3,1]).to_dyck_word()
[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]

to_exp(k=0)

Return a list of the multiplicities of the parts of a partition. Use the optional parameter k to get a return list of length at 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]

to_exp_dict()

Return a dictionary containing the multiplicities of the parts of self.

EXAMPLES:

sage: p = Partition([4,2,2,1])
sage: d = p.to_exp_dict()
sage: d[4]
1
sage: d[2]
2
sage: d[1]
1
sage: 5 in d
False

to_list()

Return self as a list.

EXAMPLES:

sage: p = Partition([2,1]).to_list(); p
[2, 1]
sage: type(p)
<type 'list'>


TESTS:

sage: p = Partition([2,1])
sage: pl = p.to_list()
sage: pl[0] = 0; p
[2, 1]

top_garnir_tableau(e, cell)

Return the most dominant standard tableau which dominates the corresponding Garnir tableau and has the same e-residue.

The Garnir tableau play an important role in integral and non-semisimple representation theory because they determine the “straightening” rules for the Specht modules. The top Garnir tableaux arise in the graded representation theory of the symmetric groups and higher level Hecke algebras. They were introduced in [KMR].

If the Garnir node is cell=(r,c) and $$m$$ and $$M$$ are the entries in the cells (r,c) and (r+1,c), respectively, in the initial tableau then the top e-Garnir tableau is obtained by inserting the numbers $$m, m+1, \ldots, M$$ 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:

up()

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

up_list()

Return a list of the partitions that can be formed from self by adding a cell.

EXAMPLES:

sage: Partition([2,1,1]).up_list()
[[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]
sage: Partition([3,2]).up_list()
[[4, 2], [3, 3], [3, 2, 1]]
sage: Partition([]).up_list()
[[1]]

upper_hook(i, j, alpha)

Return the upper hook length of the cell $$(i,j)$$ in self. When alpha = 1, this is just the normal hook length.

The upper hook length of a cell $$(i,j)$$ in a partition $$\kappa$$ is defined by

$h_*^\kappa(i,j) = \kappa_j^\prime-i+\alpha(\kappa_i - j+1).$

EXAMPLES:

sage: p = Partition([2,1])
sage: p.upper_hook(0,0,1)
3
sage: p.hook_length(0,0)
3
sage: [ p.upper_hook(i,j,x) for i,j in p.cells() ]
[2*x + 1, x, x]

upper_hook_lengths(alpha)

Return a tableau of shape self with the cells filled in with the upper hook lengths. When alpha = 1, these are just the normal hook lengths.

The upper hook length of a cell $$(i,j)$$ in a partition $$\kappa$$ is defined by

$h_*^\kappa(i,j) = \kappa_j^\prime-i+1+\alpha(\kappa_i - j).$

EXAMPLES:

sage: Partition([3,2,1]).upper_hook_lengths(x)
[[3*x + 2, 2*x + 1, x], [2*x + 1, x], [x]]
sage: Partition([3,2,1]).upper_hook_lengths(1)
[[5, 3, 1], [3, 1], [1]]
sage: Partition([3,2,1]).hook_lengths()
[[5, 3, 1], [3, 1], [1]]

weighted_size()

Return the weighted size of self.

The weighted size of a partition $$\lambda$$ is

$\sum_i i * \lambda_i.$

This also the sum of the leg length of every cell in $$\lambda$$, or

$\sum_i \binom{\lambda^{\prime}_i}{2}$

where $$\lambda^{\prime}$$ the conjugate partition of $$\lambda$$.

EXAMPLES:

sage: Partition([2,2]).weighted_size()
2
sage: Partition([3,3,3]).weighted_size()
9
sage: Partition([5,2]).weighted_size()
2

young_subgroup()

Return the corresponding Young, or parabolic, subgroup of the symmetric group.

EXAMPLES:

sage: Partition([4,2]).young_subgroup()
Permutation Group with generators [(), (5,6), (3,4), (2,3), (1,2)]

young_subgroup_generators()

Return an indexing set for the generators of the corresponding Young subgroup.

EXAMPLES:

sage: Partition([4,2]).young_subgroup_generators()
[1, 2, 3, 5]

zero_one_sequence()

Computes the finite $$0-1$$ sequence of the partition.

The full $$0-1$$ sequence is the sequence (infinite in both directions) indicating the steps taken when following the outer rim of the diagram of the partition. We use the convention that in English convention, a 1 corresponds to an East step, and a 0 corresponds to a North step.

Note that every full $$0-1$$ sequence starts with infinitely many 0’s and ends with infinitely many 1’s.

One place where these arise is in the affine symmetric group where one takes an affine permutation $$w$$ and every $$i$$ such that $$w(i) \leq 0$$ corresponds to a 1 and $$w(i) > 0$$ corresponds to a 0. See pages 24-25 of [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 [Sta1999], among others.

OUTPUT:

The finite $$0-1$$ sequence is obtained from the full $$0-1$$ sequence by omitting all heading 0’s and trailing 1’s. The output sequence is finite, starts with a 1 and ends with a 0 (unless it is empty, for the empty partition).

REFERENCES:

 [LLMMSZ13] Thomas Lam, Luc Laponte, Jennifer Morse, Anne Schilling, Mark Shimozono, and Mike Zabrocki. $$k$$-Schur Functions and Affine Schubert Calculus. 2013. Arxiv 1301.3569.

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

sage.combinat.partition.PartitionTuples_nk(n, k)

EXAMPLES:

sage: sage.combinat.partition.PartitionTuples_nk(3, 2)
doctest:...: DeprecationWarning: this class is deprecated. Use sage.combinat.partition_tuple.PartitionTuples_level_size instead
See http://trac.sagemath.org/13072 for details.
Partition tuples of level 2 and size 3

class sage.combinat.partition.Partitions(is_infinite=False)

Partitions(n, **kwargs) returns the combinatorial class of integer partitions of $$n$$, and 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:

• starting=p specifies that the partitions should all be less than or equal to $$p$$ in lex order.
• ending=p specifies that the partitions should all be greater than or equal to $$p$$ in lex order.
• length=k specifies that the partitions have exactly $$k$$ parts.
• min_length=k specifies that the partitions have at least $$k$$ parts.
• min_part=k specifies that all parts of the partitions are at least $$k$$.
• inner=p specifies that the partitions must contain the partition $$p$$.
• outer=p specifies that the partitions be contained inside the partition $$p$$.
• min_slope=k specifies that the partitions have slope at least $$k$$; the slope is the difference between successive parts.
• parts_in=S specifies that the partitions have parts in the set $$S$$, which can be any sequence of positive integers.

The max_* versions, along with inner and ending, work analogously.

Right now, the parts_in, starting, and ending keyword arguments are mutually exclusive, both of each other and of other keyword arguments. If you specify, say, parts_in, all other keyword arguments will be ignored; starting and ending work the same way.

EXAMPLES:

If no arguments are passed, then the combinatorial class of all integer partitions is returned:

sage: Partitions()
Partitions
sage: [2,1] in Partitions()
True


If an integer $$n$$ is passed, then the combinatorial class of integer partitions of $$n$$ is returned:

sage: Partitions(3)
Partitions of the integer 3
sage: Partitions(3).list()
[[3], [2, 1], [1, 1, 1]]


If starting=p is passed, then the combinatorial class of partitions greater than or equal to $$p$$ in lexicographic order is returned:

sage: Partitions(3, starting=[2,1])
Partitions of the integer 3 starting with [2, 1]
sage: Partitions(3, starting=[2,1]).list()
[[2, 1], [1, 1, 1]]


If ending=p is passed, then the combinatorial class of partitions at most $$p$$ in lexicographic order is returned:

sage: Partitions(3, ending=[2,1])
Partitions of the integer 3 ending with [2, 1]
sage: Partitions(3, ending=[2,1]).list()
[[3], [2, 1]]


Using max_slope=-1 yields partitions into distinct parts – each part differs from the next by at least 1. Use a 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 $$n$$ into odd parts equals the number of partitions into distinct parts. Let’s test that for $$n$$ from 10 to 20:

sage: test = lambda n: Partitions(n, max_slope=-1).cardinality() == Partitions(n, parts_in=[1,3..n]).cardinality()
sage: all(test(n) for n in [10..20])
True


The number of partitions of $$n$$ into distinct parts that differ by at least 2 equals the number of partitions into parts that equal 1 or 4 modulo 5; this is one of the Rogers-Ramanujan identities:

sage: test = lambda n: Partitions(n, max_slope=-2).cardinality() == Partitions(n, parts_in=([1,6..n] + [4,9..n])).cardinality()
sage: all(test(n) for n in [10..20])
True


Here are some more examples illustrating min_part, max_part, 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=[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:$$14145$$ has been fixed:

sage: 1 in Partitions()
False

Element

alias of Partition

from_beta_numbers(beta)

Return a partition corresponding to a sequence of beta numbers.

A sequence of beta numbers is a strictly increasing sequence $$0 \leq b_1 < \cdots < b_k$$ of non-negative integers. The corresponding partition $$\mu = (\mu_k, \ldots, \mu_1)$$ is given by $$\mu_i = [1,i) \setminus \{ b_1, \ldots, b_i \}$$. This gives a bijection from the set of partitions with at most $$k$$ non-zero parts to the set of strictly increasing sequences of non-negative integers of length $$k$$.

EXAMPLES:

sage: Partitions().from_beta_numbers([0,1,2,4,5,8])
[3, 1, 1]
sage: Partitions().from_beta_numbers([0,2,3,6])
[3, 1, 1]

from_core_and_quotient(core, quotient)

Returns a partition from its core and quotient.

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

from_exp(exp)

Returns a partition from its list of multiplicities.

EXAMPLES:

sage: Partitions().from_exp([2,2,1])
[3, 2, 2, 1, 1]

from_frobenius_coordinates(frobenius_coordinates)

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]

from_zero_one(seq)

Return a partition from its $$0-1$$ sequence.

The full $$0-1$$ sequence is the sequence (infinite in both directions) indicating the steps taken when following the outer rim of the diagram of the partition. We use the convention that in English convention, a 1 corresponds to an East step, and a 0 corresponds to a North step.

Note that every full $$0-1$$ sequence starts with infinitely many 0’s and ends with infinitely many 1’s.

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

global_options(*get_value, **set_value)

Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.

The options to partitions can be accessed as the method Partitions.global_options of Partitions and related parent classes.

OPTIONS:

• convention – (default: English) Sets the convention used for displaying tableaux and partitions
• English – use the English convention
• French – use the French convention
• diagram_str – (default: *) The character used for the cells when printing Ferrers diagrams
• display – (default: list) Specifies how partitions should be printed
• array – alias for diagram
• compact – alias for compact_low
• compact_high – compact form of exp_high
• compact_low – compact form of exp_low
• diagram – as a Ferrers diagram
• exp – alias for exp_low
• exp_high – in exponential form (highest first)
• exp_low – in exponential form (lowest first)
• ferrers_diagram – alias for diagram
• list – displayed as a list
• young_diagram – alias for diagram
• latex – (default: young_diagram) Specifies how partitions should be latexed
• array – alias for diagram
• diagram – latex as a Ferrers diagram
• exp – alias for exp_low
• exp_high – latex as a list in exponential notation (highest first)
• exp_low – as a list latex in exponential notation (lowest first)
• ferrers_diagram – alias for diagram
• list – latex as a list
• young_diagram – latex as a Young diagram
• latex_diagram_str – (default: \ast) The character used for the cells when latexing Ferrers diagrams
• notation – alternative name for convention

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.

subset(*args, **kwargs)

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

class sage.combinat.partition.PartitionsGreatestEQ(n, k)

The class of all (unordered) “restricted” partitions of the integer $$n$$ having its greatest part equal to the integer $$k$$.

EXAMPLES:

sage: PartitionsGreatestEQ(10,2)
Partitions of 10 having greatest part equal to 2
sage: PartitionsGreatestEQ(10,2).list()
[[2, 2, 2, 2, 2],
[2, 2, 2, 2, 1, 1],
[2, 2, 2, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 1, 1, 1],
[2, 1, 1, 1, 1, 1, 1, 1, 1]]

sage: [4,3,2,1] in PartitionsGreatestEQ(10,2)
False
sage: [2,2,2,2,2] in PartitionsGreatestEQ(10,2)
True
sage: [1]*10 in PartitionsGreatestEQ(10,2)
False

sage: PartitionsGreatestEQ(10,2).first().parent()
Partitions...

Element

alias of Partition

global_options(*get_value, **set_value)

Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.

The options to partitions can be accessed as the method Partitions.global_options of Partitions and related parent classes.

OPTIONS:

• convention – (default: English) Sets the convention used for displaying tableaux and partitions
• English – use the English convention
• French – use the French convention
• diagram_str – (default: *) The character used for the cells when printing Ferrers diagrams
• display – (default: list) Specifies how partitions should be printed
• array – alias for diagram
• compact – alias for compact_low
• compact_high – compact form of exp_high
• compact_low – compact form of exp_low
• diagram – as a Ferrers diagram
• exp – alias for exp_low
• exp_high – in exponential form (highest first)
• exp_low – in exponential form (lowest first)
• ferrers_diagram – alias for diagram
• list – displayed as a list
• young_diagram – alias for diagram
• latex – (default: young_diagram) Specifies how partitions should be latexed
• array – alias for diagram
• diagram – latex as a Ferrers diagram
• exp – alias for exp_low
• exp_high – latex as a list in exponential notation (highest first)
• exp_low – as a list latex in exponential notation (lowest first)
• ferrers_diagram – alias for diagram
• list – latex as a list
• young_diagram – latex as a Young diagram
• latex_diagram_str – (default: \ast) The character used for the cells when latexing Ferrers diagrams
• notation – alternative name for convention

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.

sage.combinat.partition.PartitionsGreatestEQ_nk(n, k)

EXAMPLES:

sage: sage.combinat.partition.PartitionsGreatestEQ_nk(10, 2)
doctest:1: DeprecationWarning: this class is deprecated. Use PartitionsGreatestEQ instead
See http://trac.sagemath.org/13605 for details.
Partitions of 10 having greatest part equal to 2

class sage.combinat.partition.PartitionsGreatestLE(n, k)

The class of all (unordered) “restricted” partitions of the integer $$n$$ having parts less than or equal to the integer $$k$$.

EXAMPLES:

sage: PartitionsGreatestLE(10,2)
Partitions of 10 having parts less than or equal to 2
sage: PartitionsGreatestLE(10,2).list()
[[2, 2, 2, 2, 2],
[2, 2, 2, 2, 1, 1],
[2, 2, 2, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 1, 1, 1],
[2, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

sage: [4,3,2,1] in PartitionsGreatestLE(10,2)
False
sage: [2,2,2,2,2] in PartitionsGreatestLE(10,2)
True
sage: PartitionsGreatestLE(10,2).first().parent()
Partitions...

Element

alias of Partition

global_options(*get_value, **set_value)

Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.

The options to partitions can be accessed as the method Partitions.global_options of Partitions and related parent classes.

OPTIONS:

• convention – (default: English) Sets the convention used for displaying tableaux and partitions
• English – use the English convention
• French – use the French convention
• diagram_str – (default: *) The character used for the cells when printing Ferrers diagrams
• display – (default: list) Specifies how partitions should be printed
• array – alias for diagram
• compact – alias for compact_low
• compact_high – compact form of exp_high
• compact_low – compact form of exp_low
• diagram – as a Ferrers diagram
• exp – alias for exp_low
• exp_high – in exponential form (highest first)
• exp_low – in exponential form (lowest first)
• ferrers_diagram – alias for diagram
• list – displayed as a list
• young_diagram – alias for diagram
• latex – (default: young_diagram) Specifies how partitions should be latexed
• array – alias for diagram
• diagram – latex as a Ferrers diagram
• exp – alias for exp_low
• exp_high – latex as a list in exponential notation (highest first)
• exp_low – as a list latex in exponential notation (lowest first)
• ferrers_diagram – alias for diagram
• list – latex as a list
• young_diagram – latex as a Young diagram
• latex_diagram_str – (default: \ast) The character used for the cells when latexing Ferrers diagrams
• notation – alternative name for convention

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.

sage.combinat.partition.PartitionsGreatestLE_nk(n, k)

For unpickling PartitionsGreatestLE objects created with sage <= 3.4.1. See PartitionsGreatestLE.

EXAMPLES:

sage: sage.combinat.partition.PartitionsGreatestLE_nk(10, 2)
doctest:1: DeprecationWarning: this class is deprecated. Use PartitionsGreatestLE instead
See http://trac.sagemath.org/13605 for details.
Partitions of 10 having parts less than or equal to 2

class sage.combinat.partition.PartitionsInBox(h, w)

All partitions with fit in a $$h \times w$$ box.

EXAMPLES:

sage: PartitionsInBox(2,2)
Integer partitions which fit in a 2 x 2 box
sage: PartitionsInBox(2,2).list()
[[], [1], [1, 1], [2], [2, 1], [2, 2]]

list()

Return a list of all the partitions inside a box of height $$h$$ and width $$w$$.

EXAMPLES:

sage: PartitionsInBox(2,2).list()
[[], [1], [1, 1], [2], [2, 1], [2, 2]]


TESTS:

Check trac ticket #10890:

sage: type(PartitionsInBox(0,0)[0])
<class 'sage.combinat.partition.PartitionsInBox_with_category.element_class'>

sage.combinat.partition.PartitionsInBox_hw(h, w)

For unpickling PartitionsInBox_hw objects created before trac ticket #13605. See OrderedPartitions.

EXAMPLES:

sage: sage.combinat.partition.PartitionsInBox_hw(3, 2)
doctest:1: DeprecationWarning: this class is deprecated. Use PartitionsInBox instead
See http://trac.sagemath.org/13605 for details.
Integer partitions which fit in a 3 x 2 box

class sage.combinat.partition.Partitions_all

Class of all partitions.

TESTS:

sage: TestSuite( sage.combinat.partition.Partitions_all() ).run()

subset(size=None, **kwargs)

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

class sage.combinat.partition.Partitions_all_bounded(k)

TESTS:

sage: TestSuite( sage.combinat.partition.Partitions_all_bounded(3) ).run()

class sage.combinat.partition.Partitions_constraints(n, length=None, min_length=0, max_length=inf, floor=None, ceiling=None, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, name=None, element_constructor=None, element_class=None, global_options=None)

For unpickling old constrained Partitions_constraints objects created with sage <= 3.4.1. See Partitions.

class sage.combinat.partition.Partitions_ending(n, ending_partition)

All partitions with a given ending.

first()

Return the first partition in self.

EXAMPLES:

sage: Partitions(4, ending=[1,1,1,1]).first()
[4]

next(part)

Return the next partition after part 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

class sage.combinat.partition.Partitions_n(n)

Partitions of the integer $$n$$.

TESTS:

sage: TestSuite( sage.combinat.partition.Partitions_n(0) ).run()
sage: TestSuite( sage.combinat.partition.Partitions_n(0) ).run()

cardinality(algorithm='flint')

Returns the number of partitions of the specified size.

INPUT:

• algorithm - (default: 'flint')
• 'flint' – use FLINT (currently the fastest)
• 'bober' – Use Jonathan Bober’s implementation (very fast)
• 'gap' – use GAP (VERY slow)
• 'pari' – use PARI. Speed seems the same as GAP until $$n$$ is in the thousands, in which case PARI is faster.

Use the function partitions() to return a generator over all partitions of $$n$$.

It is possible to associate with every partition of the integer $$n$$ a conjugacy class of permutations in the symmetric group on $$n$$ points and vice versa. Therefore the number of partitions $$p_n$$ is the number of conjugacy classes of the symmetric group on $$n$$ points.

EXAMPLES:

sage: v = Partitions(5).list(); v
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
sage: len(v)
7
sage: Partitions(5).cardinality(algorithm='gap')
7
sage: Partitions(5).cardinality(algorithm='pari')
7
sage: 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 $$p_n$$ is given by the reciprocal of Euler’s function:

$\sum_{n=0}^{\infty} p_n x^n = \prod_{k=1}^{\infty} \left( \frac{1}{1-x^k} \right).$

We use Sage to verify that the first several coefficients do instead agree:

sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen()
sage: prod([(1-q^k)^(-1) for k in range(1,9)])  ## partial product of
1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9)
sage: [Partitions(k).cardinality() for k in range(2,10)]
[2, 3, 5, 7, 11, 15, 22, 30]


REFERENCES:

first()

Returns the lexicographically first partition of a positive integer $$n$$. This is the partition [n].

EXAMPLES:

sage: Partitions(4).first()
[4]

last()

Return the lexicographically last partition of the positive integer $$n$$. This is the all-ones partition.

EXAMPLES:

sage: Partitions(4).last()
[1, 1, 1, 1]

next(p)

Return the lexicographically next partition after the partition p.

EXAMPLES:

sage: Partitions(4).next([4])
[3, 1]
sage: Partitions(4).next([1,1,1,1]) is None
True

random_element(measure='uniform')

Return a random partitions of $$n$$ for the specified measure.

INPUT:

• measure'uniform' or 'Plancherel' (default: 'uniform')

EXAMPLES:

sage: Partitions(5).random_element() # random
[2, 1, 1, 1]
sage: Partitions(5).random_element(measure='Plancherel') # random
[2, 1, 1, 1]

random_element_plancherel()

Returns a random partitions of $$n$$.

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:

• insert by Robinson-Schensted a uniform random permutations of n and returns the shape of the resulting tableau. The complexity is $$O(n\ln(n))$$ which is likely optimal. However, the implementation could be optimized.

AUTHOR:

• Florent Hivert (2009-11-23)
random_element_uniform()

Return a random partitions of $$n$$ with uniform probability.

EXAMPLES:

sage: Partitions(5).random_element_uniform()  # random
[2, 1, 1, 1]
sage: Partitions(20).random_element_uniform() # random
[9, 3, 3, 2, 2, 1]


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:

• Florent Hivert (2009-11-23)
subset(**kwargs)

Return a subset of self with the additional optional arguments.

EXAMPLES:

sage: P = Partitions(5); P
Partitions of the integer 5
sage: P.subset(starting=[3,1])
Partitions of the integer 5 starting with [3, 1]

class sage.combinat.partition.Partitions_parts_in(n, parts)

Partitions of $$n$$ with parts in a given set $$S$$.

TESTS:

sage: TestSuite( sage.combinat.partition.Partitions_parts_in(6, parts=[2,1]) ).run()

cardinality()

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 $$n$$, we’d better get $$p(n)$$:

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

first()

Return the lexicographically first partition of a positive integer $$n$$ with the specified parts, or None if no such partition exists.

EXAMPLES:

sage: Partitions(9, parts_in=[3,4]).first()
[3, 3, 3]
sage: Partitions(6, parts_in=[1..6]).first()
[6]
sage: Partitions(30, parts_in=[4,7,8,10,11]).first()
[11, 11, 8]

last()

Return the lexicographically last partition of the positive integer $$n$$ with the specified parts, or None if no such partition exists.

EXAMPLES:

sage: Partitions(15, parts_in=[2,3]).last()
[3, 2, 2, 2, 2, 2, 2]
sage: Partitions(30, parts_in=[4,7,8,10,11]).last()
[7, 7, 4, 4, 4, 4]
sage: Partitions(10, parts_in=[3,6]).last() is None
True
sage: Partitions(50, parts_in=[11,12,13]).last()
[13, 13, 12, 12]
sage: Partitions(30, parts_in=[4,7,8,10,11]).last()
[7, 7, 4, 4, 4, 4]


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

class sage.combinat.partition.Partitions_starting(n, starting_partition)

All partitions with a given start.

first()

Return the first partition in self.

EXAMPLES:

sage: Partitions(3, starting=[2,1]).first()
[2, 1]

next(part)

Return the next partition after part in self.

EXAMPLES:

sage: Partitions(3, starting=[2,1]).next(Partition([2,1]))
[1, 1, 1]

sage.combinat.partition.RestrictedPartitions(n, S, k=None)

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 $$n = p_1+p_2+\ldots+p_k$$ of positive integers and is represented by the list $$p = [p_1,p_2,\ldots,p_k]$$, in nonincreasing order. The difference is that here the $$p_i$$ must be elements from the set $$S$$, while for ordinary partitions they may be elements from $$[1..n]$$.

Returns the list of all restricted partitions of the positive integer n into sums with $$k$$ summands with the summands of the partition coming from the set $$S$$. If $$k$$ is not given all restricted partitions for all $$k$$ are returned.

Wraps GAP’s RestrictedPartitions.

EXAMPLES:

sage: RestrictedPartitions(5,[3,2,1])
doctest:1: 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]]

class sage.combinat.partition.RestrictedPartitions_nsk(n, S, k=None)

We are deprecating RestrictedPartitions(), so this class should be deprecated too. See trac ticket #13072.

Element

alias of Partition

cardinality()

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

global_options(*get_value, **set_value)

Sets and displays the global options for elements of the partition, skew partition, and partition tuple classes. If no parameters are set, then the function returns a copy of the options dictionary.

The options to partitions can be accessed as the method Partitions.global_options of Partitions and related parent classes.

OPTIONS:

• convention – (default: English) Sets the convention used for displaying tableaux and partitions
• English – use the English convention
• French – use the French convention
• diagram_str – (default: *) The character used for the cells when printing Ferrers diagrams
• display – (default: list) Specifies how partitions should be printed
• array – alias for diagram
• compact – alias for compact_low
• compact_high – compact form of exp_high
• compact_low – compact form of exp_low
• diagram – as a Ferrers diagram
• exp – alias for exp_low
• exp_high – in exponential form (highest first)
• exp_low – in exponential form (lowest first)
• ferrers_diagram – alias for diagram
• list – displayed as a list
• young_diagram – alias for diagram
• latex – (default: young_diagram) Specifies how partitions should be latexed
• array – alias for diagram
• diagram – latex as a Ferrers diagram
• exp – alias for exp_low
• exp_high – latex as a list in exponential notation (highest first)
• exp_low – as a list latex in exponential notation (lowest first)
• ferrers_diagram – alias for diagram
• list – latex as a list
• young_diagram – latex as a Young diagram
• latex_diagram_str – (default: \ast) The character used for the cells when latexing Ferrers diagrams
• notation – alternative name for convention

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.

list()

Returns the list of all restricted partitions of the positive integer $$n$$ into sums with $$k$$ summands with the summands of the partition coming from the set $$S$$. If $$k$$ is not given all restricted partitions for all $$k$$ 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]]

sage.combinat.partition.cyclic_permutations_of_partition(partition)

Return all combinations of cyclic permutations of each cell of the partition.

AUTHORS:

• Robert L. Miller

EXAMPLES:

sage: from sage.combinat.partition import cyclic_permutations_of_partition
sage: cyclic_permutations_of_partition([[1,2,3,4],[5,6,7]])
doctest:...: DeprecationWarning: cyclic_permutations_of_partition is being removed from the global namespace. Use sage.combinat.set_partition.cyclic_permutations_of_set_partition instead.
See http://trac.sagemath.org/13072 for details.
doctest:...: DeprecationWarning: cyclic_permutations_of_partition_iterator is being removed from the global namespace. Please use sage.combinat.set_partition.cyclic_permutations_of_set_partition_iterator instead.
See http://trac.sagemath.org/13072 for details.
doctest:...: DeprecationWarning: cyclic_permutations_of_partition_iterator is being removed from the global namespace. Please use sage.combinat.set_partition.cyclic_permutations_of_set_partition_iterator instead.
See http://trac.sagemath.org/13072 for details.
doctest:...: DeprecationWarning: Use the CyclicPermutations object instead.
See http://trac.sagemath.org/14772 for details.
doctest:...: DeprecationWarning: Use the CyclicPermutations object instead.
See http://trac.sagemath.org/14772 for details.
[[[1, 2, 3, 4], [5, 6, 7]],
[[1, 2, 4, 3], [5, 6, 7]],
[[1, 3, 2, 4], [5, 6, 7]],
[[1, 3, 4, 2], [5, 6, 7]],
[[1, 4, 2, 3], [5, 6, 7]],
[[1, 4, 3, 2], [5, 6, 7]],
[[1, 2, 3, 4], [5, 7, 6]],
[[1, 2, 4, 3], [5, 7, 6]],
[[1, 3, 2, 4], [5, 7, 6]],
[[1, 3, 4, 2], [5, 7, 6]],
[[1, 4, 2, 3], [5, 7, 6]],
[[1, 4, 3, 2], [5, 7, 6]]]

sage.combinat.partition.cyclic_permutations_of_partition_iterator(partition)

Iterates over all combinations of cyclic permutations of each cell of the partition.

AUTHORS:

• Robert L. Miller

EXAMPLES:

sage: from sage.combinat.partition import cyclic_permutations_of_partition_iterator
sage: list(cyclic_permutations_of_partition_iterator([[1,2,3,4],[5,6,7]]))
doctest:...: DeprecationWarning: cyclic_permutations_of_partition_iterator is being removed from the global namespace. Please use sage.combinat.set_partition.cyclic_permutations_of_set_partition_iterator instead.
See http://trac.sagemath.org/13072 for details.
[[[1, 2, 3, 4], [5, 6, 7]],
[[1, 2, 4, 3], [5, 6, 7]],
[[1, 3, 2, 4], [5, 6, 7]],
[[1, 3, 4, 2], [5, 6, 7]],
[[1, 4, 2, 3], [5, 6, 7]],
[[1, 4, 3, 2], [5, 6, 7]],
[[1, 2, 3, 4], [5, 7, 6]],
[[1, 2, 4, 3], [5, 7, 6]],
[[1, 3, 2, 4], [5, 7, 6]],
[[1, 3, 4, 2], [5, 7, 6]],
[[1, 4, 2, 3], [5, 7, 6]],
[[1, 4, 3, 2], [5, 7, 6]]]

sage.combinat.partition.from_beta_numbers(beta)

This function has been deprecated in trac ticket #13605. Use Partitions.from_beta_numbers() instead.

EXAMPLES:

sage: sage.combinat.partition.from_beta_numbers([0,1,2,4,5,8])
doctest:1: DeprecationWarning: from_beta_numbers is deprecated. Use Partitions().from_beta_numbers instead.
See http://trac.sagemath.org/13605 for details.
[3, 1, 1]

sage.combinat.partition.from_core_and_quotient(core, quotient)

This has been deprecated in trac ticket #13605. Use Partitions.from_core_and_quotient() instead.

EXAMPLES:

sage: sage.combinat.partition.from_core_and_quotient([2,1], [[2,1],[3],[1,1,1]])
doctest:1: DeprecationWarning: from_core_and_quotient is deprecated. Use Partitions().from_core_and_quotient instead.
See http://trac.sagemath.org/13605 for details.
[11, 5, 5, 3, 2, 2, 2]

sage.combinat.partition.from_exp(exp)

This has been deprecated in trac ticket #13605. Use Partitions.from_exp() instead.

EXAMPLES:

sage: sage.combinat.partition.from_exp([2,2,1])
doctest:1: DeprecationWarning: from_exp is deprecated. Use Partitions().from_exp instead.
See http://trac.sagemath.org/13605 for details.
[3, 2, 2, 1, 1]

sage.combinat.partition.from_frobenius_coordinates(coords)

This function has been deprecated in trac ticket #13605. Use Partitions.from_frobenius_coordinates() instead.

EXAMPLES:

sage: sage.combinat.partition.from_frobenius_coordinates(([],[]))
doctest:1: DeprecationWarning: from_frobenius_coordinates is deprecated. Use Partitions().from_frobenius_coordinates instead.
See http://trac.sagemath.org/13605 for details.
[]

sage.combinat.partition.number_of_ordered_partitions(n, k=None)

Returns the size of ordered_partitions(n,k). Wraps GAP’s NrOrderedPartitions.

It is possible to associate with every partition of the integer n a conjugacy class of permutations in the symmetric group on n points and vice versa. Therefore p(n) = NrPartitions(n) is the number of conjugacy classes of the symmetric group on $$n$$ points.

EXAMPLES:

sage: from sage.combinat.partition import number_of_ordered_partitions
sage: number_of_ordered_partitions(10,2)
doctest:...: DeprecationWarning: number_of_ordered_partitions is deprecated. Use OrderedPartitions().cardinality instead.
See http://trac.sagemath.org/13072 for details.
9
sage: number_of_ordered_partitions(15)
16384

sage.combinat.partition.number_of_partitions(n, k=None, algorithm='default')

Returns the number of partitions of $$n$$ with, optionally, at most $$k$$ parts.

The options of number_of_partitions() are being deprecated trac ticket #13072 in favour 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:

• n – an integer
• k – (default: None); if specified, instead returns the cardinality of the set of all (unordered) partitions of the positive integer n into sums with k summands. [Will be deprecated: please use PartitionTuples(level, size).cardinality() ]
• algorithm – (default: ‘default’) [Will be deprecated except in Partition().cardinality() ]
• 'default' – If k is not None, then use Gap (very slow). If k is None, use FLINT.
• 'flint' – use FLINT
• 'bober' – use Jonathan Bober’s implementation
• 'gap' – use GAP (VERY slow)
• 'pari' – use PARI. Speed seems the same as GAP until $$n$$ is in the thousands, in which case PARI is faster. But PARI has a bug, e.g., on 64-bit Linux PARI-2.3.2 outputs numbpart(147007)%1000 as 536 when it should be 533!. So do not use this option.

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='gap')
doctest:1: DeprecationWarning: sage.combinat.number_of_partitions is deprecated. Use  Partitions().cardinality(algorithm='gap')
See http://trac.sagemath.org/13072 for details.
7
sage: number_of_partitions(5, algorithm='pari')
doctest:1: DeprecationWarning: sage.combinat.number_of_partitions is deprecated. Use  Partitions().cardinality(algorithm='pari')
See http://trac.sagemath.org/13072 for details.
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,2)
doctest:1: DeprecationWarning: sage.combinat.number_of_partitions(size, level) is deprecated. Use PartitionTuples(level, size).cardinality() instead.
See http://trac.sagemath.org/13072 for details.
5

sage: number_of_partitions(10)
42
sage: number_of_partitions(3)
3
sage: number_of_partitions(10)
42
sage: number_of_partitions(3, algorithm='pari')
3
sage: number_of_partitions(10, algorithm='pari')
42
sage: number_of_partitions(40)
37338
sage: number_of_partitions(100)
190569292
sage: number_of_partitions(100000)
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519


A generating function for the number of partitions $$p_n$$ is given by the reciprocal of Euler’s function:

$\sum_{n=0}^{\infty} p_n x^n = \prod_{k=1}^{\infty} \left( \frac{1}{1-x^k} \right).$

We use Sage to verify that the first several coefficients do instead agree:

sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen()
sage: prod([(1-q^k)^(-1) for k in range(1,9)])  ## partial product of
1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9)
sage: [number_of_partitions(k) for k in range(2,10)]
[2, 3, 5, 7, 11, 15, 22, 30]


REFERENCES:

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


Another consistency test for n up to 500:

sage: len([n for n in [1..500] if number_of_partitions(n) != number_of_partitions(n,algorithm='pari')])
0

sage.combinat.partition.number_of_partitions_set(S, k)

Return the size of partitions_set(S,k). Wraps GAP’s NrPartitionsSet.

The Stirling number of the second kind is the number of partitions of a set of size $$n$$ into $$k$$ blocks.

REFERENCES:

Wikipedia article Partition_of_a_set

EXAMPLES:

sage: mset = [1,2,3,4]
sage: from sage.combinat.partition import number_of_partitions_set
sage: number_of_partitions_set(mset,2)
doctest:...: DeprecationWarning: number_of_partitions_set is deprecated. Use SetPartitions().cardinality() instead.
See http://trac.sagemath.org/13072 for details.
7
sage: stirling_number2(4,2)
7

sage.combinat.partition.number_of_partitions_tuples(n, k)

number_of_partition_tuples( n, k ) returns the number of partition_tuples(n,k).

Wraps GAP’s NrPartitionTuples.

EXAMPLES:

sage: from sage.combinat.partition import number_of_partitions_tuples
sage: number_of_partitions_tuples(3,2)
doctest:...: DeprecationWarning: number_of_partition_tuples(size, level) is deprecated. Use PartitionTuples(level, size).cardinality() instead.
See http://trac.sagemath.org/13072 for details.
10
sage: number_of_partitions_tuples(8,2)
185


Now we compare that with the result of the following GAP computation:

gap> S8:=Group((1,2,3,4,5,6,7,8),(1,2));
Group([ (1,2,3,4,5,6,7,8), (1,2) ])
gap> C2:=Group((1,2));
Group([ (1,2) ])
gap> W:=WreathProduct(C2,S8);
<permutation group of size 10321920 with 10 generators>
gap> Size(W);
10321920     ## = 2^8*Factorial(8), which is good:-)
gap> Size(ConjugacyClasses(W));
185
sage.combinat.partition.ordered_partitions(n, k=None)

An ordered partition of $$n$$ is an ordered sum

$n = p_1+p_2 + \cdots + p_k$

of positive integers and is represented by the list $$p = [p_1,p_2,\cdots ,p_k]$$. If $$k$$ is omitted then all ordered partitions are returned.

ordered_partitions(n,k) returns the list of all (ordered) partitions of the positive integer n into sums with $$k$$ summands.

Do not call ordered_partitions with an $$n$$ much larger than 15, since the list will simply become too large.

Wraps GAP’s OrderedPartitions.

The number of ordered partitions $$T_n$$ of $$\{ 1, 2, ..., n \}$$ has the generating function is

$\sum_n {T_n \over n!} x^n = {1 \over 2-e^x}.$

EXAMPLES:

sage: from sage.combinat.partition import ordered_partitions
sage: ordered_partitions(10,2)
doctest:1: DeprecationWarning: ordered_partitions is deprecated. Use OrderedPartitions instead.
See http://trac.sagemath.org/13072 for details.
[[1, 9], [2, 8], [3, 7], [4, 6], [5, 5], [6, 4], [7, 3], [8, 2], [9, 1]]

sage: ordered_partitions(4)
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]


REFERENCES:

sage.combinat.partition.partition_power(pi, k)

partition_power( pi, k ) returns the partition corresponding to the $$k$$-th power of a permutation with cycle structure pi (thus describes the powermap of symmetric groups).

Wraps GAP’s PowerPartition.

EXAMPLES:

sage: from sage.combinat.partition import partition_power
sage: partition_power([5,3],1)
doctest:...: DeprecationWarning: partition_power is deprecated. Use Partition(mu).power() instead.
See http://trac.sagemath.org/13072 for details.
[5, 3]
sage: partition_power([5,3],2)
[5, 3]
sage: partition_power([5,3],3)
[5, 1, 1, 1]
sage: partition_power([5,3],4)
[5, 3]


Now let us compare this to the power map on $$S_8$$:

sage: G = SymmetricGroup(8)
sage: g = G([(1,2,3,4,5),(6,7,8)])
sage: g
(1,2,3,4,5)(6,7,8)
sage: g^2
(1,3,5,2,4)(6,8,7)
sage: g^3
(1,4,2,5,3)
sage: g^4
(1,5,4,3,2)(6,7,8)

sage.combinat.partition.partitions(n)

Generator of all the partitions of the integer $$n$$.

To compute the number of partitions of $$n$$ use Partitions_n.cardinality() or number_of_partitions().

INPUT:

• n – An integer

EXAMPLES:

sage: partitions(3)
<generator object partitions at 0x...>
sage: list(partitions(3))
doctest:1: DeprecationWarning: partitions is deprecated. Use Partitions() instead.
See http://trac.sagemath.org/13072 for details.
doctest:...: DeprecationWarning: partitions is deprecated. Use Partitions() instead.
See http://trac.sagemath.org/13072 for details.
[(1, 1, 1), (1, 2), (3,)]


AUTHORS:

• Adapted from David Eppstein, Jan Van lent, George Yoshida; Python Cookbook 2, Recipe 19.16.
sage.combinat.partition.partitions_greatest(n, k)

Returns the list of all (unordered) “restricted” partitions of the integer $$n$$ having parts less than or equal to the integer $$k$$.

Wraps GAP’s PartitionsGreatestLE.

EXAMPLES:

sage: from sage.combinat.partition import partitions_greatest
sage: partitions_greatest(10,2)
doctest:...: DeprecationWarning: partitions_greatest is deprecated. Use PartitionsGreatestLE instead.
See http://trac.sagemath.org/13072 for details.
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[2, 1, 1, 1, 1, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 1, 1, 1],
[2, 2, 2, 1, 1, 1, 1],
[2, 2, 2, 2, 1, 1],
[2, 2, 2, 2, 2]]

sage.combinat.partition.partitions_greatest_eq(n, k)

Returns the list of all (unordered) “restricted” partitions of the integer $$n$$ having at least one part equal to the integer $$k$$.

Wraps GAP’s PartitionsGreatestEQ.

EXAMPLES:

sage: from sage.combinat.partition import partitions_greatest_eq
sage: partitions_greatest_eq(10,2)
doctest:...: DeprecationWarning: partitions_greatest_eq is deprecated. Use PartitionsGreatestEQ instead.
See http://trac.sagemath.org/13072 for details.
[[2, 1, 1, 1, 1, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 1, 1, 1],
[2, 2, 2, 1, 1, 1, 1],
[2, 2, 2, 2, 1, 1],
[2, 2, 2, 2, 2]]

sage.combinat.partition.partitions_set(S, k=None, use_file=True)

An unordered partition of a set $$S$$ is a set of pairwise disjoint nonempty subsets with union $$S$$ and is represented by a sorted list of such subsets.

partitions_set returns the list of all unordered partitions of the list $$S$$ of increasing positive integers into k pairwise disjoint nonempty sets. If k is omitted then all partitions are returned.

The Bell number $$B_n$$, named in honor of Eric Temple Bell, is the number of different partitions of a set with n elements.

Warning

Wraps GAP - hence $$S$$ must be a list of objects that have string representations that can be interpreted by the GAP interpreter. If mset consists of at all complicated Sage objects, this function does not do what you expect. See SetPartitions in combinat/set_partition.

Warning

This function is inefficient. The runtime is dominated by parsing the output from GAP.

Wraps GAP’s PartitionsSet.

REFERENCES:

Wikipedia article Partition_of_a_set

EXAMPLES:

sage: S = [1,2,3,4]
sage: from sage.combinat.partition import partitions_set
sage: partitions_set(S,2)
doctest:1: DeprecationWarning: partitions_set is deprecated. Use SetPartitions instead.
See http://trac.sagemath.org/13072 for details.
Set partitions of {1, 2, 3, 4} with 2 parts

sage.combinat.partition.partitions_tuples(n, k)

partition_tuples( n, k ) returns the list of all $$k$$-tuples of partitions which together form a partition of $$n$$.

$$k$$-tuples of partitions describe the classes and the characters of wreath products of groups with $$k$$ conjugacy classes with the symmetric group $$S_n$$.

Wraps GAP’s PartitionTuples.

EXAMPLES:

sage: from sage.combinat.partition import partitions_tuples
sage: partitions_tuples(3,2)
doctest:...: DeprecationWarning: partition_tuples is deprecated. Use PartitionTuples(level, size) instead.
See http://trac.sagemath.org/13072 for details.
[[[1, 1, 1], []],
[[1, 1], [1]],
[[1], [1, 1]],
[[], [1, 1, 1]],
[[2, 1], []],
[[1], [2]],
[[2], [1]],
[[], [2, 1]],
[[3], []],
[[], [3]]]


#### Previous topic

Partitions and Partition-like Objects

Partition tuples