Integer partitions¶
A partition \(p\) of a nonnegative integer \(n\) is a non-increasing list of positive integers (the parts of the partition) with total sum \(n\).
A partition can be depicted by a diagram made of rows of cells, where the number of cells in the \(i^{th}\) row starting from the top is the \(i^{th}\) part of the partition.
The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition \([5, 3, 1]\) are \([[0,4], [1,2], [2,0]]\).
For display options, see Partitions.options
.
Note
- Boxes is a synonym for cells. All methods will use ‘cell’ and ‘cells’ instead of ‘box’ and ‘boxes’.
- Partitions are 0 based with coordinates in the form of (row-index, column-index).
- If given coordinates of the form
(r, c)
, then use Python’s *-operator. - Throughout this documentation, for a partition \(\lambda\) we will denote
its conjugate partition by \(\lambda^{\prime}\). For more on conjugate
partitions, see
Partition.conjugate()
. - The comparisons on partitions use lexicographic order.
Note
We use the convention that lexicographic ordering is read from left-to-right. That is to say \([1, 3, 7]\) is smaller than \([2, 3, 4]\).
AUTHORS:
- Mike Hansen (2007): initial version
- Dan Drake (2009-03-28): deprecate RestrictedPartitions and implement Partitions_parts_in
- Travis Scrimshaw (2012-01-12): Implemented latex function to Partition_class
- Travis Scrimshaw (2012-05-09): Fixed Partitions(-1).list() infinite recursion loop by saying Partitions_n is the empty set.
- Travis Scrimshaw (2012-05-11): Fixed bug in inner where if the length was longer than the length of the inner partition, it would include 0’s.
- Andrew Mathas (2012-06-01): Removed deprecated functions and added compatibility with the PartitionTuple classes. See trac ticket #13072
- Travis Scrimshaw (2012-10-12): Added options. Made
Partition_class
to the elementPartition
.Partitions*
are now all in the category framework exceptPartitionsRestricted
(which will eventually be removed). Cleaned up documentation.
EXAMPLES:
There are \(5\) partitions of the integer \(4\):
sage: Partitions(4).cardinality()
5
sage: Partitions(4).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
We can use the method .first()
to get the ‘first’ partition of a
number:
sage: Partitions(4).first()
[4]
Using the method .next(p)
, we can calculate the ‘next’ partition
after \(p\). When we are at the last partition, None
will be returned:
sage: Partitions(4).next([4])
[3, 1]
sage: Partitions(4).next([1,1,1,1]) is None
True
We can use iter
to get an object which iterates over the partitions
one by one to save memory. Note that when we do something like
for part in Partitions(4)
this iterator is used in the background:
sage: g = iter(Partitions(4))
sage: next(g)
[4]
sage: next(g)
[3, 1]
sage: next(g)
[2, 2]
sage: for p in Partitions(4): print(p)
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
We can add constraints to the type of partitions we want. For example, to get all of the partitions of \(4\) of length \(2\), we’d do the following:
sage: Partitions(4, length=2).list()
[[3, 1], [2, 2]]
Here is the list of partitions of length at least \(2\) and the list of ones with length at most \(2\):
sage: Partitions(4, min_length=2).list()
[[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: Partitions(4, max_length=2).list()
[[4], [3, 1], [2, 2]]
The options min_part
and max_part
can be used to set constraints
on the sizes of all parts. Using max_part
, we can select
partitions having only ‘small’ entries. The following is the list
of the partitions of \(4\) with parts at most \(2\):
sage: Partitions(4, max_part=2).list()
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]
The min_part
options is complementary to max_part
and selects
partitions having only ‘large’ parts. Here is the list of all
partitions of \(4\) with each part at least \(2\):
sage: Partitions(4, min_part=2).list()
[[4], [2, 2]]
The options inner
and outer
can be used to set part-by-part
constraints. This is the list of partitions of \(4\) with [3, 1, 1]
as
an outer bound (that is, partitions of \(4\) contained in the partition
[3, 1, 1]
):
sage: Partitions(4, outer=[3,1,1]).list()
[[3, 1], [2, 1, 1]]
outer
sets max_length
to the length of its argument. Moreover, the
parts of outer
may be infinite to clear constraints on specific
parts. Here is the list of the partitions of \(4\) of length at most \(3\)
such that the second and third part are \(1\) when they exist:
sage: Partitions(4, outer=[oo,1,1]).list()
[[4], [3, 1], [2, 1, 1]]
Finally, here are the partitions of \(4\) with [1,1,1]
as an inner
bound (i. e., the partitions of \(4\) containing the partition [1,1,1]
).
Note that inner
sets min_length
to the length of its argument:
sage: Partitions(4, inner=[1,1,1]).list()
[[2, 1, 1], [1, 1, 1, 1]]
The options min_slope
and max_slope
can be used to set
constraints on the slope, that is on the difference p[i+1]-p[i]
of
two consecutive parts. Here is the list of the strictly decreasing
partitions of \(4\):
sage: Partitions(4, max_slope=-1).list()
[[4], [3, 1]]
The constraints can be combined together in all reasonable ways. Here are all the partitions of \(11\) of length between \(2\) and \(4\) such that the difference between two consecutive parts is between \(-3\) and \(-1\):
sage: Partitions(11,min_slope=-3,max_slope=-1,min_length=2,max_length=4).list()
[[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]]
Partition objects can also be created individually with Partition
:
sage: Partition([2,1])
[2, 1]
Once we have a partition object, then there are a variety of methods that we can use. For example, we can get the conjugate of a partition. Geometrically, the conjugate of a partition is the reflection of that partition through its main diagonal. Of course, this operation is an involution:
sage: Partition([4,1]).conjugate()
[2, 1, 1, 1]
sage: Partition([4,1]).conjugate().conjugate()
[4, 1]
If we create a partition with extra zeros at the end, they will be dropped:
sage: Partition([4,1,0,0])
[4, 1]
sage: Partition([0])
[]
sage: Partition([0,0])
[]
The idea of a partition being followed by infinitely many parts of size
\(0\) is consistent with the get_part
method:
sage: p = Partition([5, 2])
sage: p.get_part(0)
5
sage: p.get_part(10)
0
We can go back and forth between the standard and the exponential notations of a partition. The exponential notation can be padded with extra zeros:
sage: Partition([6,4,4,2,1]).to_exp()
[1, 1, 0, 2, 0, 1]
sage: Partition(exp=[1,1,0,2,0,1])
[6, 4, 4, 2, 1]
sage: Partition([6,4,4,2,1]).to_exp(5)
[1, 1, 0, 2, 0, 1]
sage: Partition([6,4,4,2,1]).to_exp(7)
[1, 1, 0, 2, 0, 1, 0]
sage: Partition([6,4,4,2,1]).to_exp(10)
[1, 1, 0, 2, 0, 1, 0, 0, 0, 0]
We can get the (zero-based!) coordinates of the corners of a partition:
sage: Partition([4,3,1]).corners()
[(0, 3), (1, 2), (2, 0)]
We can compute the core and quotient of a partition and build the partition back up from them:
sage: Partition([6,3,2,2]).core(3)
[2, 1, 1]
sage: Partition([7,7,5,3,3,3,1]).quotient(3)
([2], [1], [2, 2, 2])
sage: p = Partition([11,5,5,3,2,2,2])
sage: p.core(3)
[]
sage: p.quotient(3)
([2, 1], [4], [1, 1, 1])
sage: Partition(core=[],quotient=([2, 1], [4], [1, 1, 1]))
[11, 5, 5, 3, 2, 2, 2]
We can compute the \(0-1\) sequence and go back and forth:
sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0])
[5, 4]
sage: all(Partitions().from_zero_one(mu.zero_one_sequence())
....: == mu for n in range(5) for mu in Partitions(n))
True
We can compute the Frobenius coordinates and go back and forth:
sage: Partition([7,3,1]).frobenius_coordinates()
([6, 1], [2, 0])
sage: Partition(frobenius_coordinates=([6,1],[2,0]))
[7, 3, 1]
sage: all(mu == Partition(frobenius_coordinates=mu.frobenius_coordinates())
....: for n in range(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
-
sage.combinat.partition.
OrderedPartitions
¶ The class of ordered partitions of \(n\). If \(k\) is specified, then this contains only the ordered partitions of length \(k\).
An ordered partition of a nonnegative integer \(n\) means a list of positive integers whose sum is \(n\). This is the same as a composition of \(n\).
Note
It is recommended that you use
Compositions()
instead asOrderedPartitions()
wraps GAP.EXAMPLES:
sage: OrderedPartitions(3) Ordered partitions of 3 sage: OrderedPartitions(3).list() [[3], [2, 1], [1, 2], [1, 1, 1]] sage: OrderedPartitions(3,2) Ordered partitions of 3 of length 2 sage: OrderedPartitions(3,2).list() [[2, 1], [1, 2]] sage: OrderedPartitions(10,k=2).list() [[9, 1], [8, 2], [7, 3], [6, 4], [5, 5], [4, 6], [3, 7], [2, 8], [1, 9]] sage: OrderedPartitions(4).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
-
sage.combinat.partition.
Partition
¶ A partition \(p\) of a nonnegative integer \(n\) is a non-increasing list of positive integers (the parts of the partition) with total sum \(n\).
A partition is often represented as a diagram consisting of cells, or boxes, placed in rows on top of each other such that the number of cells in the \(i^{th}\) row, reading from top to bottom, is the \(i^{th}\) part of the partition. The rows are left-justified (and become shorter and shorter the farther down one goes). This diagram is called the Young diagram of the partition, or more precisely its Young diagram in English notation. (French and Russian notations are variations on this representation.)
The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition
[5, 3, 1]
are[[0,4], [1,2], [2,0]]
.For display options, see
Partitions.options()
.Note
Partitions are 0 based with coordinates in the form of (row-index, column-index). For example consider the partition
mu=Partition([4,3,2,2])
, the first part ismu[0]
(which is 4), the second ismu[1]
, and so on, and the upper-left cell in English convention is(0, 0)
.A partition can be specified in one of the following ways:
- a list (the default)
- using exponential notation
- by Frobenius coordinates
- specifying its \(0-1\) sequence
- specifying the core and the quotient
See the examples below.
EXAMPLES:
Creating partitions though parents:
sage: mu = Partitions(8)([3,2,1,1,1]); mu [3, 2, 1, 1, 1] sage: nu = Partition([3,2,1,1,1]); nu [3, 2, 1, 1, 1] sage: mu == nu True sage: mu is nu False sage: mu in Partitions() True sage: mu.parent() Partitions of the integer 8 sage: mu.size() 8 sage: mu.category() Category of elements of Partitions of the integer 8 sage: nu.parent() Partitions sage: nu.category() Category of elements of Partitions sage: mu[0] 3 sage: mu[1] 2 sage: mu[2] 1 sage: mu.pp() *** ** * * * sage: mu.removable_cells() [(0, 2), (1, 1), (4, 0)] sage: mu.down_list() [[2, 2, 1, 1, 1], [3, 1, 1, 1, 1], [3, 2, 1, 1]] sage: mu.addable_cells() [(0, 3), (1, 2), (2, 1), (5, 0)] sage: mu.up_list() [[4, 2, 1, 1, 1], [3, 3, 1, 1, 1], [3, 2, 2, 1, 1], [3, 2, 1, 1, 1, 1]] sage: mu.conjugate() [5, 2, 1] sage: mu.dominates(nu) True sage: nu.dominates(mu) True
Creating partitions using
Partition
:sage: Partition([3,2,1]) [3, 2, 1] sage: Partition(exp=[2,1,1]) [3, 2, 1, 1] sage: Partition(core=[2,1], quotient=[[2,1],[3],[1,1,1]]) [11, 5, 5, 3, 2, 2, 2] sage: Partition(frobenius_coordinates=([3,2],[4,0])) [4, 4, 1, 1, 1] sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0]) [5, 4] sage: [2,1] in Partitions() True sage: [2,1,0] in Partitions() True sage: Partition([1,2,3]) Traceback (most recent call last): ... ValueError: [1, 2, 3] is not an element of Partitions
Sage ignores trailing zeros at the end of partitions:
sage: Partition([3,2,1,0]) [3, 2, 1] sage: Partitions()([3,2,1,0]) [3, 2, 1] sage: Partitions(6)([3,2,1,0]) [3, 2, 1]
-
sage.combinat.partition.
Partitions
¶ Partitions(n, **kwargs)
returns the combinatorial class of integer partitions of \(n\) subject to the constraints given by the keywords.Valid keywords are:
starting
,ending
,min_part
,max_part
,max_length
,min_length
,length
,max_slope
,min_slope
,inner
,outer
,parts_in
,regular
, andrestricted
. They have the following meanings:starting=p
specifies that the partitions should all be less than or equal to \(p\) in lex order. This argument cannot be combined with any other (see trac ticket #15467).ending=p
specifies that the partitions should all be greater than or equal to \(p\) in lex order. This argument cannot be combined with any other (see trac ticket #15467).length=k
specifies that the partitions have exactly \(k\) parts.min_length=k
specifies that the partitions have at least \(k\) parts.min_part=k
specifies that all parts of the partitions are at least \(k\).inner=p
specifies that the partitions must contain the partition \(p\).outer=p
specifies that the partitions be contained inside the partition \(p\).min_slope=k
specifies that the partitions have slope at least \(k\); the slope at position \(i\) is the difference between the \((i+1)\)-th part and the \(i\)-th part.parts_in=S
specifies that the partitions have parts in the set \(S\), which can be any sequence of pairwise distinct positive integers. This argument cannot be combined with any other (see trac ticket #15467).regular=ell
specifies that the partitions are \(\ell\)-regular, and can only be combined with themax_length
ormax_part
, but not both, keywords if \(n\) is not specifiedrestricted=ell
specifies that the partitions are \(\ell\)-restricted, and cannot be combined with any other keywords
The
max_*
versions, along withinner
andending
, work analogously.Right now, the
parts_in
,starting
,ending
,regular
, andrestricted
keyword arguments are mutually exclusive, both of each other and of other keyword arguments. If you specify, say,parts_in
, all other keyword arguments will be ignored;starting
,ending
,regular
, andrestricted
work the same way.EXAMPLES:
If no arguments are passed, then the combinatorial class of all integer partitions is returned:
sage: Partitions() Partitions sage: [2,1] in Partitions() True
If an integer \(n\) is passed, then the combinatorial class of integer partitions of \(n\) is returned:
sage: Partitions(3) Partitions of the integer 3 sage: Partitions(3).list() [[3], [2, 1], [1, 1, 1]]
If
starting=p
is passed, then the combinatorial class of partitions greater than or equal to \(p\) in lexicographic order is returned:sage: Partitions(3, starting=[2,1]) Partitions of the integer 3 starting with [2, 1] sage: Partitions(3, starting=[2,1]).list() [[2, 1], [1, 1, 1]]
If
ending=p
is passed, then the combinatorial class of partitions at most \(p\) in lexicographic order is returned:sage: Partitions(3, ending=[2,1]) Partitions of the integer 3 ending with [2, 1] sage: Partitions(3, ending=[2,1]).list() [[3], [2, 1]]
Using
max_slope=-1
yields partitions into distinct parts – each part differs from the next by at least 1. Use a differentmax_slope
to get parts that differ by, say, 2:sage: Partitions(7, max_slope=-1).list() [[7], [6, 1], [5, 2], [4, 3], [4, 2, 1]] sage: Partitions(15, max_slope=-1).cardinality() 27
The number of partitions of \(n\) into odd parts equals the number of partitions into distinct parts. Let’s test that for \(n\) from 10 to 20:
sage: test = lambda n: Partitions(n, max_slope=-1).cardinality() == Partitions(n, parts_in=[1,3..n]).cardinality() sage: all(test(n) for n in [10..20]) True
The number of partitions of \(n\) into distinct parts that differ by at least 2 equals the number of partitions into parts that equal 1 or 4 modulo 5; this is one of the Rogers-Ramanujan identities:
sage: test = lambda n: Partitions(n, max_slope=-2).cardinality() == Partitions(n, parts_in=([1,6..n] + [4,9..n])).cardinality() sage: all(test(n) for n in [10..20]) True
Here are some more examples illustrating
min_part
,max_part
, andlength
:sage: Partitions(5,min_part=2) Partitions of the integer 5 satisfying constraints min_part=2 sage: Partitions(5,min_part=2).list() [[5], [3, 2]]
sage: Partitions(3,max_length=2).list() [[3], [2, 1]]
sage: Partitions(10, min_part=2, length=3).list() [[6, 2, 2], [5, 3, 2], [4, 4, 2], [4, 3, 3]]
Some examples using the
regular
keyword:sage: Partitions(regular=4) 4-Regular Partitions sage: Partitions(regular=4, max_length=3) 4-Regular Partitions with max length 3 sage: Partitions(regular=4, max_part=3) 4-Regular 3-Bounded Partitions sage: Partitions(3, regular=4) 4-Regular Partitions of the integer 3
Some examples using the
restricted
keyword:sage: Partitions(restricted=4) 4-Restricted Partitions sage: Partitions(3, restricted=4) 4-Restricted Partitions of the integer 3
Here are some further examples using various constraints:
sage: [x for x in Partitions(4)] [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, length=2)] [[3, 1], [2, 2]] sage: [x for x in Partitions(4, min_length=2)] [[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, max_length=2)] [[4], [3, 1], [2, 2]] sage: [x for x in Partitions(4, min_length=2, max_length=2)] [[3, 1], [2, 2]] sage: [x for x in Partitions(4, max_part=2)] [[2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, min_part=2)] [[4], [2, 2]] sage: [x for x in Partitions(4, outer=[3,1,1])] [[3, 1], [2, 1, 1]] sage: [x for x in Partitions(4, outer=[infinity, 1, 1])] [[4], [3, 1], [2, 1, 1]] sage: [x for x in Partitions(4, inner=[1,1,1])] [[2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(4, max_slope=-1)] [[4], [3, 1]] sage: [x for x in Partitions(4, min_slope=-1)] [[4], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: [x for x in Partitions(11, max_slope=-1, min_slope=-3, min_length=2, max_length=4)] [[7, 4], [6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2], [5, 3, 2, 1]] sage: [x for x in Partitions(11, max_slope=-1, min_slope=-3, min_length=2, max_length=4, outer=[6,5,2])] [[6, 5], [6, 4, 1], [6, 3, 2], [5, 4, 2]]
Note that if you specify
min_part=0
, then it will treat the minimum part as being 1 (see trac ticket #13605):sage: [x for x in Partitions(4, length=3, min_part=0)] [[2, 1, 1]] sage: [x for x in Partitions(4, min_length=3, min_part=0)] [[2, 1, 1], [1, 1, 1, 1]]
Except for very special cases, counting is done by brute force iteration through all the partitions. However the iteration itself has a reasonable complexity (see
IntegerListsLex
), which allows for manipulating large partitions:sage: Partitions(1000, max_length=1).list() [[1000]]
In particular, getting the first element is also constant time:
sage: Partitions(30, max_part=29).first() [29, 1]
-
sage.combinat.partition.
PartitionsGreatestEQ
¶ 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...
-
sage.combinat.partition.
PartitionsGreatestLE
¶ 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...
-
sage.combinat.partition.
PartitionsInBox
¶ All partitions which fit in an \(h \times w\) box.
EXAMPLES:
sage: PartitionsInBox(2,2) Integer partitions which fit in a 2 x 2 box sage: PartitionsInBox(2,2).list() [[], [1], [1, 1], [2], [2, 1], [2, 2]]
-
sage.combinat.partition.
Partitions_all
¶ Class of all partitions.
-
class
sage.combinat.partition.
Partitions_all_bounded
(k)¶
-
sage.combinat.partition.
Partitions_constraints
¶ For unpickling old constrained
Partitions_constraints
objects created with sage <= 3.4.1. SeePartitions
.
-
sage.combinat.partition.
Partitions_ending
¶ All partitions with a given ending.
-
sage.combinat.partition.
Partitions_n
¶ Partitions of the integer \(n\).
-
sage.combinat.partition.
Partitions_nk
¶ Partitions of the integer \(n\) of length equal to \(k\).
-
sage.combinat.partition.
Partitions_parts_in
¶ Partitions of \(n\) with parts in a given set \(S\).
This is invoked indirectly when calling
Partitions(n, parts_in=parts)
, whereparts
is a list of pairwise distinct integers.
-
sage.combinat.partition.
Partitions_starting
¶ All partitions with a given start.
-
sage.combinat.partition.
Partitions_with_constraints
¶ Partitions which satisfy a set of constraints.
EXAMPLES:
sage: P = Partitions(6, inner=[1,1], max_slope=-1) sage: list(P) [[5, 1], [4, 2], [3, 2, 1]]
-
sage.combinat.partition.
RegularPartitions
¶ Base class for \(\ell\)-regular partitions.
Let \(\ell\) be a positive integer. A partition \(\lambda\) is \(\ell\)-regular if \(m_i < \ell\) for all \(i\), where \(m_i\) is the multiplicity of \(i\) in \(\lambda\).
Note
This is conjugate to the notion of \(\ell\)-restricted partitions, where the difference between any two consecutive parts is \(< \ell\).
INPUT:
ell
– the positive integer \(\ell\)is_infinite
– boolean; if the subset of \(\ell\)-regular partitions is infinite
-
sage.combinat.partition.
RegularPartitions_all
¶ The class of all \(\ell\)-regular partitions.
INPUT:
ell
– the positive integer \(\ell\)
See also
-
sage.combinat.partition.
RegularPartitions_bounded
¶ The class of \(\ell\)-regular \(k\)-bounded partitions.
INPUT:
ell
– the integer \(\ell\)k
– integer; the value \(k\)
See also
-
sage.combinat.partition.
RegularPartitions_n
¶ The class of \(\ell\)-regular partitions of \(n\).
INPUT:
n
– the integer \(n\) to partitionell
– the integer \(\ell\)
See also
-
sage.combinat.partition.
RegularPartitions_truncated
¶ The class of \(\ell\)-regular partitions with max length \(k\).
INPUT:
ell
– the integer \(\ell\)max_len
– integer; the maximum length
See also
-
sage.combinat.partition.
RestrictedPartitions_all
¶ The class of all \(\ell\)-restricted partitions.
INPUT:
ell
– the positive integer \(\ell\)
See also
-
sage.combinat.partition.
RestrictedPartitions_generic
¶ Base class for \(\ell\)-restricted partitions.
Let \(\ell\) be a positive integer. A partition \(\lambda\) is \(\ell\)-restricted if \(\lambda_i - \lambda_{i+1} < \ell\) for all \(i\), including rows of length 0.
Note
This is conjugate to the notion of \(\ell\)-regular partitions, where the multiplicity of any parts is at most \(\ell\).
INPUT:
ell
– the positive integer \(\ell\)is_infinite
– boolean; if the subset of \(\ell\)-restricted partitions is infinite
-
sage.combinat.partition.
RestrictedPartitions_n
¶ The class of \(\ell\)-restricted partitions of \(n\).
INPUT:
n
– the integer \(n\) to partitionell
– the integer \(\ell\)
See also
-
sage.combinat.partition.
conjugate
(p)¶ Return the conjugate partition associated to the partition
p
as a list.EXAMPLES:
sage: from sage.combinat.partition import conjugate sage: conjugate([2,2]) [2, 2] sage: conjugate([6,3,1]) [3, 2, 2, 1, 1, 1]
-
sage.combinat.partition.
number_of_partitions
(n, 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 ofPartitions_n.cardinality()
so thatnumber_of_partitions()
can become a stripped down version of the fastest algorithm available (currently this is using FLINT).INPUT:
n
– an integeralgorithm
– (default: ‘default’) [Will be deprecated except in Partition().cardinality() ]'default'
– Ifk
is notNone
, then use Gap (very slow). Ifk
isNone
, use FLINT.'flint'
– use FLINT'bober'
– use Jonathan Bober’s implementation
EXAMPLES:
sage: v = Partitions(5).list(); v [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]] sage: len(v) 7 sage: number_of_partitions(5, algorithm='bober') 7
The input must be a nonnegative integer or a
ValueError
is raised.sage: number_of_partitions(-5) Traceback (most recent call last): ... ValueError: n (=-5) must be a nonnegative integer
sage: number_of_partitions(10) 42 sage: number_of_partitions(3) 3 sage: number_of_partitions(10) 42 sage: number_of_partitions(40) 37338 sage: number_of_partitions(100) 190569292 sage: number_of_partitions(100000) 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
A generating function for the number of partitions \(p_n\) is given by the reciprocal of Euler’s function:
\[\sum_{n=0}^{\infty} p_n x^n = \prod_{k=1}^{\infty} \left( \frac{1}{1-x^k} \right).\]We use Sage to verify that the first several coefficients do instead agree:
sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen() sage: prod([(1-q^k)^(-1) for k in range(1,9)]) ## partial product of 1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9) sage: [number_of_partitions(k) for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
REFERENCES:
-
sage.combinat.partition.
number_of_partitions_length
(n, k, algorithm='hybrid')¶ Return the number of partitions of \(n\) with length \(k\).
This is a wrapper for GAP’s
NrPartitions
function.EXAMPLES:
sage: from sage.combinat.partition import number_of_partitions_length sage: number_of_partitions_length(5, 2) 2 sage: number_of_partitions_length(10, 2) 5 sage: number_of_partitions_length(10, 4) 9 sage: number_of_partitions_length(10, 0) 0 sage: number_of_partitions_length(10, 1) 1 sage: number_of_partitions_length(0, 0) 1 sage: number_of_partitions_length(0, 1) 0