Partitions( n )
Partitions( n, k )
NrPartitions( n )
NrPartitions( n, k )
In the first form Partitions
returns the set of all (unordered)
partitions of the positive integer n. In the second form Partitions
returns the set of all (unordered) partitions of the positive integer n
into sums with k summands.
In the first form NrPartitions
returns the number of (unordered)
partitions of the positive integer n. In the second form
NrPartitions
returns the number of (unordered) partitions of the
positive integer n into sums with k summands.
An unordered partition is an unordered sum n = p_1+p_2 +..+ p_k of positive integers and is represented by the list p = [p_1,p_2,..,p_k], in nonincreasing order, i.e., p_1>=p_2>=..>=p_k. We write pvdash n. There are approximately E^{pi sqrt{2/3 n}} / {4 sqrt{3} n} such partitions.
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.
Ramanujan found the identities p(5i+4) = 0 mod 5, p(7i+5) = 0 mod 7 and p(11i+6) = 0 mod 11 and many other fascinating things about the number of partitions.
Do not call Partitions
with an n much larger than 40, in which case
there are 37338 partitions, since the list will simply become too large.
gap> Partitions( 7 ); [ [ 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1 ], [ 2, 2, 1, 1, 1 ], [ 2, 2, 2, 1 ], [ 3, 1, 1, 1, 1 ], [ 3, 2, 1, 1 ], [ 3, 2, 2 ], [ 3, 3, 1 ], [ 4, 1, 1, 1 ], [ 4, 2, 1 ], [ 4, 3 ], [ 5, 1, 1 ], [ 5, 2 ], [ 6, 1 ], [ 7 ] ] gap> Partitions( 8, 3 ); [ [ 3, 3, 2 ], [ 4, 2, 2 ], [ 4, 3, 1 ], [ 5, 2, 1 ], [ 6, 1, 1 ] ] gap> NrPartitions( 7 ); 15 gap> NrPartitions( 100 ); 190569292
The function OrderedPartitions
(see OrderedPartitions) is the ordered
counterpart of Partitions
.
GAP 3.4.4