---
title: "Partitions"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/PartitionsWordsTableaux/partitions.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/PartitionsWordsTableaux/partitions.md"
part: "Combinatorics"
chapter: "Partitions, Words, and Young Tableaux"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Partitions, Words, and Young Tableaux", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/PartitionsWordsTableaux/index-partitions-words-tableaux.md"}
prev: {"title": "Introduction", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/PartitionsWordsTableaux/introduction.md"}
next: {"title": "Words", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/PartitionsWordsTableaux/words.md"}
intrinsics:
  - {"name": "NumberOfPartitions", "signature": "NumberOfPartitions(n): RngIntElt -> RngIntElt"}
  - {"name": "Partitions", "signature": "Partitions(n): RngIntElt -> [ [ RngIntElt ] ]"}
  - {"name": "Partitions", "signature": "Partitions(n, k): RngIntElt, RngIntElt -> [ [ RngIntElt ] ]"}
  - {"name": "RestrictedPartitions", "signature": "RestrictedPartitions(n, M): RngIntElt, SetEnum -> [ [ RngIntElt ] ]"}
  - {"name": "RestrictedPartitions", "signature": "RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum -> [ [ RngIntElt ] ]"}
  - {"name": "WeightedPartitions", "signature": "WeightedPartitions(n, w): RngIntElt, [ RngIntElt ] -> [ [ RngIntElt ] ]"}
  - {"name": "WeightedRestrictedPartitions", "signature": "WeightedRestrictedPartitions(n, S, w): RngIntElt, [ { RngIntElt }], [ RngIntElt ] -> [ [ RngIntElt ] ]"}
  - {"name": "IsPartition", "signature": "IsPartition(S): SeqEnum -> BoolElt"}
  - {"name": "RandomPartition", "signature": "RandomPartition(n): RngIntElt -> SeqEnum"}
  - {"name": "Weight", "signature": "Weight(P): SeqEnum -> RngIntElt"}
  - {"name": "IndexOfPartition", "signature": "IndexOfPartition(P): SeqEnum -> RngIntElt"}
examples:
  - "ex-071b39"
  - "ex-d58f82"
---

<a id="tableaux-partitions"></a>
<a id="id1"></a>
# 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.

<a id="function-numberofpartitions-rngintelt"></a>
## `NumberOfPartitions(n): RngIntElt -> RngIntElt`

Given a positive integer $n$, return the total number of partitions of $n$.

<a id="function-partitions-rngintelt"></a>
## `Partitions(n): RngIntElt -> [ [ RngIntElt ] ]`

Given a positive integer $n$, return the sequence of all partitions of $n$.

<a id="function-partitions-rngintelt-rngintelt"></a>
## `Partitions(n, k): RngIntElt, RngIntElt -> [ [ RngIntElt ] ]`

Given positive integers $n$ and $k$, return the sequence of all the partitions of $n$ into $k$ parts.

<a id="function-restrictedpartitions-rngintelt-setenum"></a>
## `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$.

<a id="function-restrictedpartitions-rngintelt-rngintelt-setenum"></a>
## `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$.

<a id="function-weightedpartitions-rngintelt-rngintelt"></a>
## `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$.

<a id="function-weightedrestrictedpartitions-rngintelt-rngintelt-rngintelt"></a>
## `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$.

<a id="function-ispartition-seqenum"></a>
## `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).

<a id="function-randompartition-rngintelt"></a>
## `RandomPartition(n): RngIntElt -> SeqEnum`

Returns a weakly decreasing sequence of positive integers which is random partition of the positive integer $n$.

<a id="function-weight-seqenum"></a>
## `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.

<a id="function-indexofpartition-seqenum"></a>
## `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.

<a id="example-ex-071b39"></a>
## `Example: Partitions and Conjugacy Classes (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)
```

<a id="example-ex-d58f82"></a>
## `Example: Changing Money with 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)
```
