Module: sage.combinat.partition
Partitions
A partition
of a nonnegative integer
is a non-increasing list of
positive integers (the parts of the partition) with total sum
.
A partition can be depicted by a diagram made of rows of boxes, where the
number of boxes in the
row starting from the top is the
part of the partition.
The coordinate system related to a partition applies from the top to the bottom and from left to right. So, the corners of the partition are [[0,4], [1,2], [2,0]].
There are 5 partitions of the integer 4.
sage: Partitions(4).count() 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 calculute 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 the .iterator() method 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)' an iterator is used in the background.
sage: g = Partitions(4).iterator() 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 the Partition function.
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]
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 r-core and r-quotient of a partition and build the partition back up from them.
sage: Partition([6,3,2,2]).r_core(3) [2, 1, 1] sage: Partition([7,7,5,3,3,3,1]).r_quotient(3) [[2], [1], [2, 2, 2]] sage: p = Partition([11,5,5,3,2,2,2]) sage: p.r_core(3) [] sage: p.r_quotient(3) [[2, 1], [4], [1, 1, 1]] sage: Partition(core_and_quotient=([],[[2, 1], [4], [1, 1, 1]])) [11, 5, 5, 3, 2, 2, 2]
Module-level Functions
n, [k=None]) |
Returns the combinatoiral class of ordered partitions of n. If k is specified, then only the ordered partitions of length k are returned.
NOTE: It is recommended that you use Compositions instead as OrderedPartitions wraps GAP. See also ordered_partitions.
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]]
[l=None], [exp=None], [core_and_quotient=None]) |
Returns a partition object.
Note that Sage uses the English convention for partitions and tableaux.
sage: Partition(exp=[2,1,1]) [3, 2, 1, 1] sage: Partition(core_and_quotient=([2,1], [[2,1],[3],[1,1,1]])) [11, 5, 5, 3, 2, 2, 2] sage: Partition([3,2,1]) [3, 2, 1] sage: [2,1] in Partitions() True sage: [2,1,0] in Partitions() False sage: Partition([2,1,0]) [2, 1] sage: Partition([1,2,3]) Traceback (most recent call last): ... ValueError: [1, 2, 3] is not a valid partition
n, k) |
Returns the combinatorial class of k-tuples of partitions of n. These are are ordered list of k partitions whose sizes add up to n.
These describe the classes and the characters of wreath products of
groups with k conjugacy classes with the symmetric group
.
sage: PartitionTuples(4,2) 2-tuples of partitions of 4 sage: PartitionTuples(3,2).list() [[[3], []], [[2, 1], []], [[1, 1, 1], []], [[2], [1]], [[1, 1], [1]], [[1], [2]], [[1], [1, 1]], [[], [3]], [[], [2, 1]], [[], [1, 1, 1]]]
[n=None]) |
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. They have the following meanings:
'starting=p' specifies that the partitions should all be >= p in reverse 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. 'outer=p' specifies that the partitions be contained inside the partition p. 'min_slope=k' specifies that the partition have slope at least k; the slope is the difference between successive parts.
The 'max_*' versions, along with 'inner' and 'ending', work analogously.
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 intger 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 is passed, then the combinatorial class of partitions starting with starting 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 is passed, then the combinatorial class of partitions starting with ending 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]]
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]]
n, k) |
Returns combinatorial class of all (unordered) ``restricted'' partitions of the integer n having its greatest part equal to the integer k.
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]]
n, k) |
Returns the combinatorial class of all (unordered) ``restricted'' partitions of the integer n having parts less than or equal to the integer k.
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]]
h, w) |
Returns the combinatorial class of partitions that fit in a h by w box.
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]]
n, S, [k=None]) |
A restricted partition is, like an ordinary partition, an
unordered sum
of positive integers and is
represented by the list
, in nonincreasing
order. The difference is that here the
must be elements
from the set
, while for ordinary partitions they may be
elements from
.
Returns the list of all restricted partitions of the positive integer n into sums with 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.
sage: RestrictedPartitions(5,[3,2,1]) 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]]
partition) |
Returns all combinations of cyclic permutations of each cell of the partition.
Author: Robert L. Miller
sage: from sage.combinat.partition import cyclic_permutations_of_partition sage: cyclic_permutations_of_partition([[1,2,3,4],[5,6,7]]) [[[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]]]
Note that repeated elements are not considered equal:
sage: cyclic_permutations_of_partition([[1,2,3],[4,4,4]]) [[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]], [[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
partition) |
Iterates over all combinations of cyclic permutations of each cell of the partition.
Author: Robert L. Miller
sage: from sage.combinat.partition import cyclic_permutations_of_partition sage: list(cyclic_permutations_of_partition_iterator([[1,2,3,4],[5,6,7]])) [[[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]]]
Note that repeated elements are not considered equal:
sage: list(cyclic_permutations_of_partition_iterator([[1,2,3],[4,4,4]])) [[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]], [[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
pi) |
Return the Ferrers diagram of pi.
Input:
sage: print ferrers_diagram([5,5,2,1]) ***** ***** ** * sage: pi = partitions_list(10)[30] ## [6,1,1,1,1] sage: print ferrers_diagram(pi) ****** * * * * sage: pi = partitions_list(10)[33] ## [6, 3, 1] sage: print ferrers_diagram(pi) ****** *** *
core, quotient) |
Returns a partition from its r-core and r-quotient.
Algorithm from mupad-combinat.
sage: partition.from_core_and_quotient([2,1], [[2,1],[3],[1,1,1]]) [11, 5, 5, 3, 2, 2, 2]
a) |
Returns a partition from its list of multiplicities.
sage: partition.from_exp([1,2,1]) [3, 2, 2, 1]
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.
sage: number_of_ordered_partitions(10,2) 9 sage: number_of_ordered_partitions(15) 16384
n, [k=None], [algorithm=default]) |
Returns the size of partitions_list(n,k).
Input:
IMPLEMENTATION: Wraps GAP's NrPartitions or PARI's numbpart function.
Use the function partitions(n)
to return a generator over
all partitions of
.
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.
sage: v = list(partitions(5)); v [(1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2), (1, 1, 3), (2, 3), (1, 4), (5,)] sage: len(v) 7 sage: number_of_partitions(5, algorithm='gap') 7 sage: number_of_partitions(5, algorithm='pari') 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) 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) 274935105697756965126775163209863526881734293159800547582031259843021473281 149641730550507416607366215901578447742962489404930630702004617927644930335 101160793424571901557189435097253124661084520063695589344642487168287898321 823450092628538314045970213071306745106244192273112389997022844086093709355 31629697851569569892196108480158600569421098519
A generating function for p(n) is given by the reciprocal of Euler's function:
We use SAGE to verify that the first several coefficients do instead agree:
sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen() sage: prod([(1-q^k)^(-1) for k in range(1,9)]) ## partial product of 1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9) sage: [number_of_partitions(k) for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
REFERENCES: http://en.wikipedia.org/wiki/Partition_ 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 True sage: n = 1000000000 + randint(0,1000000000) sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 # takes a long time 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
n, [k=None]) |
This function will be deprecated in a future version of Sage and eventually removed. Use Partitions(n).count() or Partitions(n, length=k).count() instead.
Original docstring follows.
Returns the size of partitions_list(n,k).
Wraps GAP's NrPartitions.
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.
number_of_partitions(n)
is also available in PARI, however
the speed seems the same until
is in the thousands (in which
case PARI is faster).
sage: partition.number_of_partitions_list(10,2) 5 sage: partition.number_of_partitions_list(10) 42
A generating function for p(n) is given by the reciprocal of Euler's function:
SAGE verifies 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: [partition.number_of_partitions_list(k) for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
REFERENCES: http://en.wikipedia.org/wiki/Partition_
n, S, [k=None]) |
This function will be deprecated in a future version of Sage and eventually removed. Use RestrictedPartitions(n, S, k).count() instead.
Original docstring follows.
Returns the size of partitions_restricted(n,S,k). Wraps GAP's NrRestrictedPartitions.
sage: number_of_partitions_restricted(8,[1,3,5,7]) 6 sage: number_of_partitions_restricted(8,[1,3,5,7],2) 2
S, k) |
Returns 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.
sage: mset = [1,2,3,4] sage: number_of_partitions_set(mset,2) 7 sage: stirling_number2(4,2) 7
REFERENCES http://en.wikipedia.org/wiki/Partition_of_a_set
n, k) |
number_of_partition_tuples( n, k ) returns the number of partition_tuples(n,k).
Wraps GAP's NrPartitionTuples.
sage: number_of_partitions_tuples(3,2) 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
n, [k=None]) |
An ordered partition of
is an ordered sum
of positive integers and is represented by the list
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
of
has the
generating function is
sage: ordered_partitions(10,2) [[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: http://en.wikipedia.org/wiki/Ordered_partition_of_a_set
pi) |
partition_associated( pi ) returns the ``associated'' (also called ``conjugate'' in the literature) partition of the partition pi which is obtained by transposing the corresponding Ferrers diagram.
sage: partition_associated([2,2]) [2, 2] sage: partition_associated([6,3,1]) [3, 2, 2, 1, 1, 1] sage: print ferrers_diagram([6,3,1]) ****** *** * sage: print ferrers_diagram([3,2,2,1,1,1]) *** ** ** * * *
pi, k) |
partition_power( pi, k ) returns the partition corresponding to the
-th power of a permutation with cycle structure pi
(thus describes the powermap of symmetric groups).
Wraps GAP's PowerPartition.
sage: partition_power([5,3],1) [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
:
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)
pi) |
partition_sign( pi ) returns the sign of a permutation with cycle structure given by the partition pi.
This function corresponds to a homomorphism from the symmetric group
into the cyclic group of order 2, whose kernel is exactly the
alternating group
. Partitions of sign
are called even partitions
while partitions of sign
are called odd.
Wraps GAP's SignPartition.
sage: partition_sign([5,3]) 1 sage: partition_sign([5,2]) -1
Zolotarev's lemma states that the Legendre symbol
for an integer
(
a prime number),
can be computed as sign(p_a), where sign denotes the sign of a permutation
and p_a the permutation of the residue classes
induced by
modular multiplication by
, provided
does not divide
.
We verify this in some examples.
sage: F = GF(11) sage: a = F.multiplicative_generator();a 2 sage: plist = [int(a*F(x)) for x in range(1,11)]; plist [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
This corresponds ot the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6)
(acting the set
) and to the partition [10].
sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)') sage: p.sign() -1 sage: partition_sign([10]) -1 sage: kronecker_symbol(11,2) -1
Now replace
by
:
sage: plist = [int(F(3*x)) for x in range(1,11)]; plist [3, 6, 9, 1, 4, 7, 10, 2, 5, 8] sage: range(1,11) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sage: p = PermutationGroupElement('(3,4,8,7,9)') sage: p.sign() 1 sage: kronecker_symbol(3,11) 1 sage: partition_sign([5,1,1,1,1,1]) 1
In both cases, Zolotarev holds.
REFERENCES: http://en.wikipedia.org/wiki/Zolotarev's_lemma
n) |
Generator of all the partitions of the integer
.
Input:
To compute the number of partitions of
use
number_of_partitions(n)
.
sage: partitions(3) <generator object at 0x...> sage: list(partitions(3)) [(1, 1, 1), (1, 2), (3,)]
Author: Adapted from David Eppstein, Jan Van lent, George Yoshida; Python Cookbook 2, Recipe 19.16.
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.
sage: partitions_greatest(10,2) [[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]]
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.
sage: partitions_greatest_eq(10,2) [[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]]
n, [k=None]) |
This function will be deprecated in a future version of Sage and eventually removed. Use Partitions(n).list() or Partitions(n, length=k).list() instead.
Original docstring follows.
An unordered partition of
is an unordered sum
of positive integers and is represented by
the list
, in nonincreasing order, i.e.,
.
Input:
partitions_list(n,k)
returns the list of all (unordered)
partitions of the positive integer n into sums with k summands. If
k is omitted then all partitions are returned.
Do not call partitions_list with an n much larger than 40, in which case there are 37338 partitions, since the list will simply become too large.
Wraps GAP's Partitions.
sage: partitions_list(10,2) [[5, 5], [6, 4], [7, 3], [8, 2], [9, 1]] sage: partitions_list(5) [[1, 1, 1, 1, 1], [2, 1, 1, 1], [2, 2, 1], [3, 1, 1], [3, 2], [4, 1], [5]]
n, S, [k=None]) |
This function will be deprecated in a future version of Sage and eventually removed. Use RestrictedPartitions(n, S, k).list() instead.
Original docstring follows.
A restricted partition is, like an ordinary partition, an
unordered sum
of positive integers and is
represented by the list
, in nonincreasing
order. The difference is that here the
must be elements
from the set
, while for ordinary partitions they may be
elements from
.
Returns the list of all restricted partitions of the positive integer
n into sums with k summands with the summands of the partition coming
from the set
. If k is not given all restricted partitions for all
k are returned.
Wraps GAP's RestrictedPartitions.
sage: partitions_restricted(8,[1,3,5,7]) [[1, 1, 1, 1, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1], [3, 3, 1, 1], [5, 1, 1, 1], [5, 3], [7, 1]] sage: partitions_restricted(8,[1,3,5,7],2) [[5, 3], [7, 1]]
S, [k=None], [use_file=True]) |
An unordered partition of a set
is a set of pairwise disjoint
nonempty subsets with union
and is represented by a sorted
list of such subsets.
partitions_set returns the list of all unordered partitions of the
list
of increasing positive integers into k pairwise disjoint
nonempty sets. If k is omitted then all partitions are returned.
The Bell number
, 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
intepreter. 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.
sage: S = [1,2,3,4] sage: partitions_set(S,2) [[[1], [2, 3, 4]], [[1, 2], [3, 4]], [[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 3], [2, 4]], [[1, 3, 4], [2]], [[1, 4], [2, 3]]]
REFERENCES: http://en.wikipedia.org/wiki/Partition_of_a_set
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
.
Wraps GAP's PartitionTuples.
sage: partitions_tuples(3,2) [[[1, 1, 1], []], [[1, 1], [1]], [[1], [1, 1]], [[], [1, 1, 1]], [[2, 1], []], [[1], [2]], [[2], [1]], [[], [2, 1]], [[3], []], [[], [3]]]
Class: OrderedPartitions_nk
self, n, [k=None]) |
sage: o = OrderedPartitions(4,2) sage: o == loads(dumps(o)) True
Functions: count,
list
self) |
sage: OrderedPartitions(3).count() 4 sage: OrderedPartitions(3,2).count() 2
self) |
sage: OrderedPartitions(3).list() [[3], [2, 1], [1, 2], [1, 1, 1]] sage: OrderedPartitions(3,2).list() [[2, 1], [1, 2]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: o = OrderedPartitions(4,2) sage: [2,1] in o False sage: [2,2] in o True sage: [1,2,1] in o False
self) |
sage: OrderedPartitions(3).__repr__() 'Ordered partitions of 3' sage: OrderedPartitions(3,2).__repr__() 'Ordered partitions of 3 of length 2'
Class: Partition_class
Functions: add_box,
add_horizontal_border_strip,
add_vertical_border_strip,
arm,
arm_lengths,
arms_legs_coeff,
associated,
atom,
boxes,
centralizer_size,
character_polynomial,
conjugacy_class_size,
conjugate,
contains,
content,
corners,
dominate,
dominates,
down,
down_list,
evaluation,
ferrers_diagram,
generalized_pochhammer_symbol,
hook,
hook_lengths,
hook_polynomial,
hook_product,
hooks,
jacobi_trudi,
k_atom,
k_conjugate,
k_skew,
k_split,
leg,
leg_lengths,
length,
lower_hook,
lower_hook_lengths,
next,
outside_corners,
parent,
power,
pp,
r_core,
r_quotient,
reading_tableau,
remove_box,
sign,
size,
to_exp,
to_list,
up,
up_list,
upper_hook,
upper_hook_lengths,
weighted_size
self, i, [j=None]) |
Returns a partition corresponding to self with a box added in row i. i and j are 0-based row and column indices. This does not change p.
Note that if you have coordinates in a list, you can call this function with python's * notation (see the examples below).
sage: Partition([3, 2, 1, 1]).add_box(0) [4, 2, 1, 1] sage: cell = [4, 0]; Partition([3, 2, 1, 1]).add_box(*cell) [3, 2, 1, 1, 1]
self, k) |
Returns a list of all the partitions that can be obtained by adding a horizontal border strip of length k to self.
sage: Partition([]).add_horizontal_border_strip(0) [[]] sage: Partition([]).add_horizontal_border_strip(2) [[2]] sage: Partition([2,2]).add_horizontal_border_strip(2) [[2, 2, 2], [3, 2, 1], [4, 2]] sage: Partition([3,2,2]).add_horizontal_border_strip(2) [[3, 2, 2, 2], [3, 3, 2, 1], [4, 2, 2, 1], [4, 3, 2], [5, 2, 2]]
self, k) |
Returns a list of all the partitions that can be obtained by adding a vertical border strip of length k to self.
sage: Partition([]).add_vertical_border_strip(0) [[]] sage: Partition([]).add_vertical_border_strip(2) [[1, 1]] sage: Partition([2,2]).add_vertical_border_strip(2) [[3, 3], [3, 2, 1], [2, 2, 1, 1]] sage: Partition([3,2,2]).add_vertical_border_strip(2) [[4, 3, 2], [4, 2, 2, 1], [3, 3, 3], [3, 3, 2, 1], [3, 2, 2, 1, 1]]
self, i, j) |
Returns the arm of cell (i,j) in partition p. The arm of cell (i,j) is the number of boxes that appear to the right of cell (i,j). Note that i and j are 0-based indices. If your coordinates are in the form [i,j], use Python's *-operator.
sage: p = Partition([2,2,1]) sage: p.arm(0, 0) 1 sage: p.arm(0, 1) 0 sage: p.arm(2, 0) 0 sage: Partition([3,3]).arm(0, 0) 2 sage: Partition([3,3]).arm(*[0,0]) 2
self, [flat=False]) |
Returns a tableau of shape p where each box is filled its arm. The optional boolean parameter flat provides the option of returning a flat list.
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]
self, i, j) |
This is a statistic on a cell c=[i,j] in the diagram of partition p given by
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)
self) |
An alias for partition.conjugate(p).
sage: Partition([4,1,1]).associated() [3, 1, 1, 1] sage: Partition([4,1,1]).conjugate() [3, 1, 1, 1] sage: Partition([5,4,2,1,1,1]).associated().associated() [5, 4, 2, 1, 1, 1]
self) |
Returns a list of the standard tableaux of size self.size() whose atom is equal to self.
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]]]
self) |
Return the coordinates of the boxes of self. Coordinates are given as (row-index, column-index) and are 0 based.
sage: Partition([2,2]).boxes() [(0, 0), (0, 1), (1, 0), (1, 1)] sage: Partition([3,2]).boxes() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)]
self, [t=0], [q=0]) |
Returns the size of the centralizer of any permuation of cycle type
p. If m_i is the multiplicity of i as a part of p, this is given by
. Including the optional parameters t
and q gives the q-t analog which is the former product times
sage: Partition([2,2,1]).centralizer_size() 8 sage: Partition([2,2,2]).centralizer_size() 48
REFERENCES: Kerber, A. 'Algebraic Combintorics via Finite Group Action', 1.3 p24
self) |
Returns the character polynomial associated to the partition
self. The character polynomial
is defined by
where
It is computed in the following manner.
1) Expand the Schur function
in the power-sum basis.
2) Replace each
with
3) Apply the umbral operator
to the resulting
polynomial.
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
self) |
Returns the size of the conjugacy class of the symmetric group indexed by the partition p.
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: Kerber, A. 'Algebraic Combinatorics via Finite Group Action' 1.3 p24
self) |
conjugate() returns the ``conjugate'' (also called ``associated'' in the literature) partition of the partition p which is obtained by transposing the corresponding Ferrers diagram.
sage: Partition([2,2]).conjugate() [2, 2] sage: Partition([6,3,1]).conjugate() [3, 2, 2, 1, 1, 1] sage: print Partition([6,3,1]).ferrers_diagram() ****** *** * sage: print Partition([6,3,1]).conjugate().ferrers_diagram() *** ** ** * * *
self, x) |
Returns True if p2 is a partition whose Ferrers diagram is contained in the Ferrers diagram of self
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
self, i, j) |
Returns the content statistic of the given cell, which is simply defined by j - i. This doesn't technically depend on the partition, but is included here because it is often useful in the context of partitions.
sage: Partition([2,1]).content(0,1) 1 sage: p = Partition([3,2]) sage: sum([p.content(*c) for c in p.boxes()]) 2
self) |
Returns a list of the corners of the partitions. These are the positions where we can remove a box. Indices are of the form [i,j] where i is the row-index and j is the column-index, and are 0-based.
sage: Partition([3,2,1]).corners() [[0, 2], [1, 1], [2, 0]] sage: Partition([3,3,1]).corners() [[1, 2], [2, 0]]
self, [rows=None]) |
Returns a list of the partitions dominated by n. If n is specified, then it only returns the ones with <= rows rows.
sage: Partition([3,2,1]).dominate() [[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]).dominate(rows=3) [[3, 2, 1], [2, 2, 2]]
self, p2) |
Returns True if partition p1 dominates partitions p2. Otherwise, it returns False.
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: Partition([]).dominates([1]) False sage: Partition([]).dominates([]) True sage: Partition([1]).dominates([]) True
self) |
Returns a generator for partitions that can be obtained from p by removing a box.
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]]
self) |
Returns a list of the partitions that can be obtained from the partition p by removing a box.
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]]
self) |
Returns the evaluation of the partition.
sage: Partition([4,3,1,1]).evaluation() [2, 0, 1, 1]
self) |
Return the Ferrers diagram of pi.
Input:
sage: print Partition([5,5,2,1]).ferrers_diagram() ***** ***** ** * sage: pi = Partitions(10).list()[11] ## [6,1,1,1,1] sage: print pi.ferrers_diagram() ****** * * * * sage: pi = Partitions(10).list()[8] ## [6, 3, 1] sage: print pi.ferrers_diagram() ****** *** *
self, a, alpha) |
Returns the generalized Pochhammer symbol
.
This is the product over all cells (i,j) in p of
.
sage: Partition([2,2]).generalized_pochhammer_symbol(2,1) 12
self, i, j) |
Returns the hook of box (i,j) in the partition p. The hook of box (i,j) is defined to be one more than the sum of number of boxes to the right and the number of boxes below (in the English convention). Note that i and j are 0-based. If your coordinates are in the form [i,j], use Python's *-operator.
sage: p = Partition([2,2,1]) sage: p.hook(0, 0) 4 sage: p.hook(0, 1) 2 sage: p.hook(2, 0) 1 sage: Partition([3,3]).hook(0, 0) 4 sage: cell = [0,0]; Partition([3,3]).hook(*cell) 4
self) |
Returns a tableau of shape p with the boxes filled in with the hook lengths
In each box, put the sum of one plus the number of boxes horizontally to the right and vertically below the box (the hook length).
For example, consider the partition [3,2,1] of 6 with Ferrers Diagram * * * * * * When we fill in the boxes with the hook lengths, we obtain 5 3 1 3 1 1
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: http://mathworld.wolfram.com/HookLengthFormula.html
self, q, t) |
Returns the two-variable hook polynomial.
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
self, a) |
Returns the Jack hook-product.
sage: Partition([3,2,1]).hook_product(x) (x + 2)^2*(2*x + 3) sage: Partition([2,2]).hook_product(x) 2*(x + 1)*(x + 2)
self) |
Returns a sorted list of the hook lengths in self.
sage: Partition([3,2,1]).hooks() [5, 3, 3, 1, 1, 1]
self) |
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 = SFASchur(QQ) sage: h = SFAHomogeneous(QQ) 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]
self, k) |
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) [[]]
self, k) |
Returns the k-conjugate of the partition.
The k-conjugate is the partition that is given by the columns of the k-skew diagram of the partition.
sage: p = Partition([4,3,2,2,1,1]) sage: p.k_conjugate(4) [3, 2, 2, 1, 1, 1, 1, 1, 1]
self, k) |
Returns the k-skew partition.
The k-skew diagram of a k-bounded partition is the skew diagram denoted
satisfying the conditions:
(i) row i of
has length
(ii) no cell in
has hook-length exceeding k
(iii) every square above the diagram of
has hook
length exceeding k.
REFERENCES: Lapointe, L. and Morse, J. 'Order Ideals in Weak Subposets of Young's Lattice and Associated Unimodality Conjectures'
sage: p = Partition([4,3,2,2,1,1]) sage: p.k_skew(4) [[9, 5, 3, 2, 1, 1], [5, 2, 1]]
self, k) |
Returns the k-split of self.
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]]
self, i, j) |
Returns the leg of box (i,j) in partition p. The leg of box (i,j) is defined to be the number of boxes below it in partition p. Note that i and j are 0-based. If your coordinates are in the form [i,j], use Python's *-operator.
sage: p = Partition([2,2,1]) sage: p.leg(0, 0) 2 sage: p.leg(0,1) 1 sage: p.leg(2,0) 0 sage: Partition([3,3]).leg(0, 0) 1 sage: cell = [0,0]; Partition([3,3]).leg(*cell) 1
self, [flat=False]) |
Returns a tableau of shape p with each box filled in with its leg. The optional boolean parameter flat provides the option of returning a flat list.
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]
self) |
Returns the number of parts in self.
sage: Partition([3,2]).length() 2 sage: Partition([2,2,1]).length() 3 sage: Partition([]).length() 0
self, i, j, alpha) |
Returns the lower hook length of the box (i,j) in self. When alpha == 1, this is just the normal hook length. Indices are 0-based.
The lower hook length of a box (i,j) in a partition
is defined by
sage: p = Partition([2,1]) sage: p.lower_hook(0,0,1) 3 sage: p.hook(0,0) 3 sage: [ p.lower_hook(i,j,x) for i,j in p.boxes() ] [x + 2, 1, 1]
self, alpha) |
Returns the lower hook lengths of the partition. When alpha == 1, these are just the normal hook lengths.
The lower hook length of a box (i,j) in a partition
is defined by
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]]
self) |
Returns the partition that lexicographically follows the partition p. If p is the last partition, then it returns False.
sage: Partition([4]).next() [3, 1] sage: Partition([1,1,1,1]).next() False
self) |
Returns a list of the positions where we can add a box so that the shape is still a partition. Indices are of the form [i,j] where i is the row-index and j is the column-index, and are 0-based.
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]]
self) |
Returns the combinatorial class of partitions of sum(self).
sage: Partition([3,2,1]).parent() Partitions of the integer 6
self, k) |
partition_power( pi, k ) returns the partition corresponding to the
-th power of a permutation with cycle structure pi
(thus describes the powermap of symmetric groups).
Wraps GAP's PowerPartition.
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
:
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)
self) |
sage: Partition([5,5,2,1]).pp() ***** ***** ** *
self, length) |
Returns the r-core of the partition p. The construction of the r-core can be visualized by repeatedly removing border strips of size r from p until this is no longer possible. The remaining partition is the r-core.
sage: Partition([6,3,2,2]).r_core(3) [2, 1, 1] sage: Partition([]).r_core(3) [] sage: Partition([8,7,7,4,1,1,1,1,1]).r_core(3) [2, 1, 1]
TESTS:
sage: Partition([3,3,3,2,1]).r_core(3) [] sage: Partition([10,8,7,7]).r_core(4) [] sage: Partition([21,15,15,9,6,6,6,3,3]).r_core(3) []
self, length) |
Returns the r-quotient of the partition p. The r-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 box labelled i, and C_i be the set of columns ending in a box labelled i. Then the jth component of the r-quotient of p is the partition defined by intersecting R_j with C_j+1.
sage: Partition([7,7,5,3,3,3,1]).r_quotient(3) [[2], [1], [2, 2, 2]]
TESTS:
sage: Partition([8,7,7,4,1,1,1,1,1]).r_quotient(3) [[2, 1], [2, 2], [2]] sage: Partition([10,8,7,7]).r_quotient(4) [[2], [3], [2], [1]] sage: Partition([6,3,3]).r_quotient(3) [[1], [1], [2]] sage: Partition([3,3,3,2,1]).r_quotient(3) [[1], [1, 1], [1]] sage: Partition([6,6,6,3,3,3]).r_quotient(3) [[2, 1], [2, 1], [2, 1]] sage: Partition([21,15,15,9,6,6,6,3,3]).r_quotient(3) [[5, 2, 1], [5, 2, 1], [7, 3, 2]] sage: Partition([21,15,15,9,6,6,3,3]).r_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]).r_quotient(5) [[3, 3], [2, 2, 1], [], [3, 3, 3], [1]]
self) |
sage: Partition([3,2,1]).reading_tableau() [[1, 3, 6], [2, 5], [4]]
self, i, [j=None]) |
Returns the partition obtained by removing a box at the end of row i.
sage: Partition([2,2]).remove_box(1) [2, 1] sage: Partition([2,2,1]).remove_box(2) [2, 2] sage: #Partition([2,2]).remove_box(0)
sage: Partition([2,2]).remove_box(1,1) [2, 1] sage: #Partition([2,2]).remove_box(1,0)
self) |
partition_sign( pi ) returns the sign of a permutation with cycle structure given by the partition pi.
This function corresponds to a homomorphism from the symmetric group
into the cyclic group of order 2, whose kernel is exactly the
alternating group
. Partitions of sign
are called even partitions
while partitions of sign
are called odd.
Wraps GAP's SignPartition.
sage: Partition([5,3]).sign() 1 sage: Partition([5,2]).sign() -1
Zolotarev's lemma states that the Legendre symbol
for an integer
(
a prime number),
can be computed as sign(p_a), where sign denotes the sign of a permutation
and p_a the permutation of the residue classes
induced by
modular multiplication by
, provided
does not divide
.
We verify this in some examples.
sage: F = GF(11) sage: a = F.multiplicative_generator();a 2 sage: plist = [int(a*F(x)) for x in range(1,11)]; plist [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
This corresponds ot the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6)
(acting the set
) and to the partition [10].
sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)') sage: p.sign() -1 sage: Partition([10]).sign() -1 sage: kronecker_symbol(11,2) -1
Now replace
by
:
sage: plist = [int(F(3*x)) for x in range(1,11)]; plist [3, 6, 9, 1, 4, 7, 10, 2, 5, 8] sage: range(1,11) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sage: p = PermutationGroupElement('(3,4,8,7,9)') sage: p.sign() 1 sage: kronecker_symbol(3,11) 1 sage: Partition([5,1,1,1,1,1]).sign() 1
In both cases, Zolotarev holds.
REFERENCES: http://en.wikipedia.org/wiki/Zolotarev's_lemma
self) |
Returns the size of partition p.
sage: Partition([2,2]).size() 4 sage: Partition([3,2,1]).size() 6
self, [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.
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]
self) |
Return self as a list.
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]
self) |
Returns a generator for partitions that can be obtained from pi by adding a box.
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]]
self) |
Returns a list of the partitions that can be formed from the partition p by adding a box.
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]]
self, i, j, alpha) |
Returns the upper hook length of the box (i,j) in self. When alpha == 1, this is just the normal hook length. As usual, indices are 0 based.
The upper hook length of a box (i,j) in a partition
is defined by
sage: p = Partition([2,1]) sage: p.upper_hook(0,0,1) 3 sage: p.hook(0,0) 3 sage: [ p.upper_hook(i,j,x) for i,j in p.boxes() ] [2*x + 1, x, x]
self, alpha) |
Returns the upper hook lengths of the partition. When alpha == 1, these are just the normal hook lengths.
The upper hook length of a box (i,j) in a partition
is defined by
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]]
self) |
Returns sum([i*p[i] for i in range(len(p))]). It is also the sum of the leg of every cell in b, or the sum of binomial(s[i],2) for s the conjugate partition of p.
sage: Partition([2,2]).weighted_size() 2 sage: Partition([3,3,3]).weighted_size() 9 sage: Partition([5,2]).weighted_size() 2
Special Functions: __div__
self, p) |
Returns the skew partition self/p.
sage: p = Partition([3,2,1]) sage: p/[1,1] [[3, 2, 1], [1, 1]] sage: p/[3,2,1] [[3, 2, 1], [3, 2, 1]] sage: p/Partition([1,1]) [[3, 2, 1], [1, 1]]
Class: Partitions_all
self) |
TESTS:
sage: P = Partitions() sage: P == loads(dumps(P)) True
Functions: count,
list
self) |
Returns the number of integer partitions.
sage: Partitions().count() +Infinity
self) |
sage: Partitions().list() Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: P = Partitions() sage: Partition([2,1]) in P True sage: [2,1] in P True sage: [3,2,1] in P True sage: [1,2] in P False sage: [] in P True sage: [0] in P False
self) |
TESTS:
sage: repr(Partitions()) 'Partitions'
Class: Partitions_constraints
self, n) |
TESTS:
sage: p = Partitions(5, min_part=2) sage: p == loads(dumps(p)) True
Functions: iterator
self) |
An iterator a list of the partitions of n.
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, 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]] sage: [x for x in Partitions(4, outer=[3,1,1])] [[3, 1], [2, 1, 1]] sage: [x for x in Partitions(4, outer=['inf', 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]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: p = Partitions(5, min_part=2) sage: [2,1] in p False sage: [2,2,1] in p False sage: [3,2] in p True
self) |
TESTS:
sage: repr( Partitions(5, min_part=2) ) 'Partitions of the integer 5 satisfying constraints min_part=2'
Class: Partitions_ending
self, n, ending_partition) |
sage: Partitions(4, ending=[1,1,1,1]).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: Partitions(4, ending=[2,2]).list() [[4], [3, 1], [2, 2]] sage: Partitions(4, ending=[4]).list() [[4]]
TESTS:
sage: p = Partitions(4, ending=[1,1,1,1]) sage: p == loads(dumps(p)) True
Functions: first,
next
self) |
sage: Partitions(4, ending=[1,1,1,1]).first() [4]
self, part) |
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
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: p = Partitions(4, ending=[2,2]) sage: [4] in p True sage: [2,1,1] in p False sage: [2,1] in p False
self) |
sage: Partitions(4, ending=[1,1,1,1]).__repr__() 'Partitions of the integer 4 ending with [1, 1, 1, 1]'
Class: Partitions_n
self, n) |
TESTS:
sage: p = Partitions(5) sage: p == loads(dumps(p)) True
Functions: count,
first,
iterator,
last
self, [algorithm=default]) |
algorithm - (default: 'default')
'bober' - use Jonathan Bober's implementation (*very* fast,
but new and not well tested yet).
'gap' - use GAP (VERY *slow*)
'pari' - use PARI. Speed seems the same as GAP until
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)should be 533!. So do not use this option.
'default' - 'bober' when k is not specified; otherwise
use 'gap'.
Use the function partitions(n)
to return a generator over
all partitions of
.
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.
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).count(algorithm='gap') 7 sage: Partitions(5).count(algorithm='pari') 7 sage: Partitions(5).count(algorithm='bober') 7
The input must be a nonnegative integer or a ValueError is raised.
sage: Partitions(10).count() 42 sage: Partitions(3).count() 3 sage: Partitions(10).count() 42 sage: Partitions(3).count(algorithm='pari') 3 sage: Partitions(10).count(algorithm='pari') 42 sage: Partitions(40).count() 37338 sage: Partitions(100).count() 190569292
A generating function for p(n) is given by the reciprocal of Euler's function:
We use SAGE to verify that the first several coefficients do instead agree:
sage: q = PowerSeriesRing(QQ, 'q', default_prec=9).gen() sage: prod([(1-q^k)^(-1) for k in range(1,9)]) ## partial product of 1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + O(q^9) sage: [Partitions(k) .count()for k in range(2,10)] [2, 3, 5, 7, 11, 15, 22, 30]
REFERENCES: http://en.wikipedia.org/wiki/Partition_
self) |
Returns the lexicographically first partition of a positive integer n. This is the partition [n].
sage: Partitions(4).first() [4]
self) |
An iterator a list of the partitions of n.
sage: [x for x in Partitions(4)] [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
self) |
Returns the lexicographically last partition of the positive integer n. This is the all-ones partition.
sage: Partitions(4).last() [1, 1, 1, 1]
Special Functions: __contains__,
__init__,
__repr__,
_fast_iterator
self, x) |
TESTS:
sage: p = Partitions(5) sage: [2,1] in p False sage: [2,2,1] in p True sage: [3,2] in p True
self) |
TESTS:
sage: repr( Partitions(5) ) 'Partitions of the integer 5'
self) |
A fast iterator for the partitions of n which returns lists and not partition types.
sage: p = Partitions(4) sage: it = p._fast_iterator() sage: it.next() [4] sage: type(_) <type 'list'>
Class: Partitions_starting
self, n, starting_partition) |
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]]
TESTS:
sage: p = Partitions(3, starting=[2,1]) sage: p == loads(dumps(p)) True
Functions: first,
next
self) |
sage: Partitions(3, starting=[2,1]).first() [2, 1]
self, part) |
sage: Partitions(3, starting=[2,1]).next(Partition([2,1])) [1, 1, 1]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: p = Partitions(3, starting=[2,1]) sage: [1,1] in p False sage: [2,1] in p True sage: [1,1,1] in p True sage: [3] in p False
self) |
sage: Partitions(3, starting=[2,1]).__repr__() 'Partitions of the integer 3 starting with [2, 1]'
Class: PartitionsGreatestEQ_nk
self, n, k) |
TESTS:
sage: p = PartitionsGreatestEQ(10,2) sage: p == loads(dumps(p)) True
Functions: list
self) |
Wraps GAP's PartitionsGreatestEQ.
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]]
Special Functions: __contains__,
__init__
self, x) |
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
Class: PartitionsGreatestLE_nk
self, n, k) |
TESTS:
sage: p = PartitionsGreatestLE(10,2) sage: p == loads(dumps(p)) True
Functions: list
self) |
Returns a list of all (unordered) ``restricted'' partitions of the integer n having parts less than or equal to the integer k.
Wraps GAP's PartitionsGreatestLE.
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]]
Special Functions: __contains__,
__init__
self, x) |
sage: [4,3,2,1] in PartitionsGreatestLE(10,2) False sage: [2,2,2,2,2] in PartitionsGreatestLE(10,2) True
Class: PartitionsInBox_hw
self, h, w) |
TESTS:
sage: p = PartitionsInBox(2,2) sage: p == loads(dumps(p)) True
Functions: list
self) |
Returns a list of all the partitions inside a box of height h and width w.
sage: PartitionsInBox(2,2).list() [[], [1], [1, 1], [2], [2, 1], [2, 2]]
Special Functions: __contains__,
__init__
self, x) |
sage: [] in PartitionsInBox(2,2) True sage: [2,1] in PartitionsInBox(2,2) True sage: [3,1] in PartitionsInBox(2,2) False sage: [2,1,1] in PartitionsInBox(2,2) False
Class: PartitionTuples_nk
self, n, k) |
TESTS:
sage: p = PartitionTuples(4,2) sage: p == loads(dumps(p)) True
Functions: count,
iterator
self) |
Returns the number of k-tuples of partitions which together form a partition of n.
Wraps GAP's NrPartitionTuples.
sage: PartitionTuples(3,2).count() 10 sage: PartitionTuples(8,2).count() 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
self) |
Returns an iterator for all k-tuples of partitions which together form a partition of n.
sage: PartitionTuples(2,0).list() #indirect doctest [] sage: PartitionTuples(2,1).list() #indirect doctest [[[2]], [[1, 1]]] sage: PartitionTuples(2,2).list() #indirect doctest [[[2], []], [[1, 1], []], [[1], [1]], [[], [2]], [[], [1, 1]]] sage: PartitionTuples(3,2).list() #indirect doctest [[[3], []], [[2, 1], []], [[1, 1, 1], []], [[2], [1]], [[1, 1], [1]], [[1], [2]], [[1], [1, 1]], [[], [3]], [[], [2, 1]], [[], [1, 1, 1]]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: [[], [1, 1, 1]] in PartitionTuples(3,2) True sage: [[1], [1, 1, 1]] in PartitionTuples(3,2) False
self) |
sage: PartitionTuples(4,2).__repr__() '2-tuples of partitions of 4'
Class: RestrictedPartitions_nsk
self, n, S, [k=None]) |
TESTS:
sage: r = RestrictedPartitions(5,[3,2,1]) sage: r == loads(dumps(r)) True
Functions: count,
list
self) |
Returns the size of RestrictedPartitions(n,S,k). Wraps GAP's NrRestrictedPartitions.
sage: RestrictedPartitions(8,[1,3,5,7]).count() 6 sage: RestrictedPartitions(8,[1,3,5,7],2).count() 2
self) |
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
. If k is not given all restricted partitions for all
k are returned.
Wraps GAP's RestrictedPartitions.
sage: RestrictedPartitions(8,[1,3,5,7]).list() [[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]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: [4,1] in RestrictedPartitions(5,[3,2,1]) False sage: [3,2] in RestrictedPartitions(5,[3,2,1]) True sage: [3,2] in RestrictedPartitions(5,[3,2,1],4) False sage: [2,1,1,1] in RestrictedPartitions(5,[3,2,1],4) True
self) |
sage: RestrictedPartitions(5,[3,2,1]).__repr__() 'Partitions of 5 restricted to the values [1, 2, 3] ' sage: RestrictedPartitions(5,[3,2,1],4).__repr__() 'Partitions of 5 restricted to the values [1, 2, 3] of length 4'