Partitions

A partition of a positive integer \(n\) is a decreasing sequence \([n_1, n_2, \ldots,n_k]\) of positive integers such that \(\sum{n_i}=n\). The \(n_i\) 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\).

WeightedPartitions(n, w): RngIntElt, [ RngIntElt ] -> [ [ RngIntElt ] ]

Given a positive integer \(n\) and a sequence of positive integers \(w\), return the sequence of all weighted partitions of \(n\) with weights \(w\), that is all sequences \(a_1, \ldots, a_m\) such that \(\sum_i w_i a_i = n\).

WeightedRestrictedPartitions(n, S, w): RngIntElt, [ { RngIntElt }], [ RngIntElt ] -> [ [ RngIntElt ] ]

Given a positive integer \(n\), a sequence of sets of non-negative integers \(S\), and a sequence of positive integers \(w\), return the sequence of all weighted partitions of \(n\) with weights \(w\), where each part is restricted to being an elements of the corresponding set in \(S\), that is all sequences \(a_1, \ldots, a_m\) such that \(\sum_i w_i a_i = n\) and \(a_i \in S_i\) for all \(1 \le i \le 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 \(P_1\) and \(P_2\), then \(P_1 > P_2\) implies that \(P_1\) is greater in the first part which differs from \(P_2\). The first index is zero.

Example: Partitions (ex-071b39)

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)

Run in calculatorCopy input

Example: Restricted Partitions (ex-d58f82)

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)

Run in calculatorCopy input