46.13 Partitions

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.

Previous Up Top Next
Index