Partitions

A partition of a positive integer n is a decreasing sequence [n1, n2, ..., nk] of positive integers such that ∑(ni)=n. The ni are called the parts of the partition.

All partition functions in Magma operate only on small, positive integers.

NumberOfPartitions(n) : RngIntElt -> RngIntElt
Given a positive integer n, return the total number of partitions of n.
Partitions(n) : RngIntElt -> [ [ RngIntElt ] ]
Given a positive integer n, return the sequence of all partitions of n.
Partitions(n, k) : RngIntElt, RngIntElt -> [ [ RngIntElt ] ]
Given positive integers n and k, return the sequence of all the partitions of n into k parts.
RestrictedPartitions(n, M) : RngIntElt, SetEnum -> [ [ RngIntElt ] ]
Given a positive integer n and a set of positive integers M, return the sequence of all partitions of n, where the parts are restricted to being elements of the set M.
RestrictedPartitions(n, k, M) : RngIntElt, RngIntElt, SetEnum -> [ [ RngIntElt ] ]
Given positive integers n and k, and a set of positive integers M, return the sequence of all partitions of n into k parts, where the parts are restricted to being elements of the set M.
IsPartition(S) : SeqEnum -> BoolElt
A sequence S is considered to be a partition if it consists of weakly decreasing positive integers. A sequence is allowed to have trailing zeros, and the empty sequence is accepted as a partition (of zero).
RandomPartition(n) : RngIntElt -> SeqEnum
Returns a weakly decreasing sequence of positive integers which is random partition of the positive integer n.
Weight(P) : SeqEnum -> RngIntElt
Given a sequence of positive integers P which is a partition, return a positive integer which is the sum of it's parts.
IndexOfPartition(P) : SeqEnum -> RngIntElt
Given a sequence of positive integers P which is a partition, return its lexicographical order among partitions of the same weight.

Lexicographical ordering of partitions is such that for partitions P1 and P2, then P1 > P2 implies that P1 is greater in the first part which differs from P2. The first index is zero.

Example Tableau_Partitions (H154E1)

The conjugacy classes of the symmetric group on n elements correspond to the partitions of n. The function PartnToElt below converts a partition to an element of the corresponding conjugacy class. 
> PartitionToElt := function(G, p)
>     x := [];
>     s := 0;
>     for d in p do
>         x cat:= Rotate([s+1 .. s+d], -1);
>         s +:= d;
>     end for;
>     return G!x;
> end function;
>
> ConjClasses := function(n)
>     G := Sym(n);
>     return [ PartitionToElt(G, p) : p in Partitions(n) ];
> end function;
>
> ConjClasses(5);
[
    (1, 2, 3, 4, 5),
    (1, 2, 3, 4),
    (1, 2, 3)(4, 5),
    (1, 2, 3),
    (1, 2)(3, 4),
    (1, 2),
    Id($)
]
> Classes(Sym(5));
Conjugacy Classes
-----------------
[1]     Order 1       Length 1
        Rep Id($)
[2]     Order 2       Length 10
        Rep (1, 2)
[3]     Order 2       Length 15
        Rep (1, 2)(3, 4)
[4]     Order 3       Length 20
        Rep (1, 2, 3)
[5]     Order 4       Length 30
        Rep (1, 2, 3, 4)
[6]     Order 5       Length 24
        Rep (1, 2, 3, 4, 5)
[7]     Order 6       Length 20
        Rep (1, 2, 3)(4, 5)

Example Tableau_RestrictedPartitions (H154E2)

The number of ways of changing money into five, ten, twenty and fifty cent coins can be calculated using RestrictedPartitions. There is also a well known solution using generating functions, which we use as a check. 
> coins := {5, 10, 20, 50};
> T := [#RestrictedPartitions(n, coins) : n in [0 .. 100 by 5]];
> T;
[ 1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 13, 13, 18, 18, 24, 24, 31, 31, 39, 39, 49 ]
> F<t> := PowerSeriesRing(RationalField(), 101);
> &*[1/(1-t^i) : i in coins];
1 + t^5 + 2*t^10 + 2*t^15 + 4*t^20 + 4*t^25 + 6*t^30 + 6*t^35 + 9*t^40 + 9*t^45
    + 13*t^50 + 13*t^55 + 18*t^60 + 18*t^65 + 24*t^70 + 24*t^75 + 31*t^80 +
    31*t^85 + 39*t^90 + 39*t^95 + 49*t^100 + O(t^101)
V2.28, 13 July 2023