# 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.

```magma
> 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: 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.

```magma
> 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)

```