# Partitions

`Partition`

— Type`Partition{T<:IntegerUnion} <: AbstractVector{T}`

A **partition** of a non-negative integer $n$ is a decreasing sequence $λ₁ ≥ λ₂ ≥ … ≥ λᵣ$ of positive integers $λᵢ$ such that $n = λ₁ + … + λᵣ$. The $λᵢ$ are called the **parts** of the partition and $r$ is called the **length**.

A partition can be encoded as an array with elements $λᵢ$. We provide the parametric type `Partition{T}`

which is a subtype of `AbstractVector{T}`

where `T`

can be any subtype of `IntegerUnion`

. All functions that can be used for vectors (1-dimensional arrays) can thus be used for partitions as well. There is no performance impact by using an own type for partitions rather than simply using arrays. The parametric type allows to increase performance by using smaller integer types. For efficiency, the `Partition`

constructor does not check whether the given array is indeed a decreasing sequence.

**Examples**

A partition can be created by either calling `Partition`

on an array of integers or by calling `Partition`

with arguments being the sequence of parts.

```
julia> P = Partition([6,4,4,2]) #The partition 6+4+4+2 of 16.
[6, 4, 4, 2]
julia> P = Partition(6,4,4,2) #Same as above but less to type
[6, 4, 4, 2]
julia> length(P)
4
julia> P[1]
6
```

Usually, $|λ| ≔ n$ is called the **size** of $λ$. In Julia, the function `size`

for arrays already exists and returns the *dimension* of an array. Instead, you can use the Julia function `sum`

to get the sum of the parts.

```
julia> P = Partition(6,4,4,2)
[6, 4, 4, 2]
julia> sum(P)
16
```

You can create partitions with smaller integer types as follows.

```
julia> P = Partition{Int8}(6,4,4,2) #Or Partition(Int8[6,4,4,2])
Int8[6, 4, 4, 2]
```

There is a unique partition of 0, namely the **empty partition** (of length 0). It can be created as follows.

```
julia> P = Partition() #Or Partition([])
Int64[]
julia> sum(P)
0
julia> length(P)
0
julia> P = Partition{Int8}() #Or Partition(Int8[])
Int8[]
```

**References**

- William Fulton (1997)
- Donald E. Knuth (2011), Section 7.2.1.4 (starting on page 390).

`getindex_safe`

— Function`getindex_safe(P::Partition, i::IntegerUnion)`

In algorithms involving partitions it is sometimes convenient to be able to access parts beyond the length of the partition and then one wants to get the value zero instead of an error. This function is a shortcut for

`return (i>length(P.p) ? 0 : getindex(P.p,i))`

If you are sure that `P[i]`

exists, use `getindex`

because this will be faster.

**Examples**

```
julia> P=Partition([3,2,1])
[3, 2, 1]
julia> getindex_safe(P, 3)
1
julia> getindex_safe(P, 4)
0
```

## Generating and counting

`partitions`

— Method`partitions(n::IntegerUnion)`

A list of all partitions of a non-negative integer `n`

, produced in lexicographically *descending* order. This ordering is like in Sage, but opposite to GAP. You can apply the function `reverse`

to reverse the order. As usual, you may increase performance by using smaller integer types.

**Algorithm**

The algorithm used is "Algorithm ZS1" by A. Zoghbi, I. Stojmenovic (1998). This algorithm is also discussed in Donald E. Knuth (2011), Algorithm P (page 392).

**Examples**

```
julia> partitions(4) # Use partitions(Int8(4)) to use 8-bit integers
5-element Vector{Partition{Int64}}:
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
```

`num_partitions`

— Method`num_partitions(n::IntegerUnion)`

The number of integer partitions of the non-negative integer `n`

.

**Examples**

```
julia> num_partitions(1000)
24061467864032622473692149727991
```

**Algorithm**

We use the function `arith_number_of_partitions`

from W. B. Hart (2010) which is very fast. It is based on the Hardy-Ramanujan-Rademacher formula, see Fredrik Johansson (2012) for details.

**Further references**

- Donald E. Knuth (2011), Section 7.2.1.4 (starting on page 395).
- OEIS Foundation Inc. (2023), A000041

### Partitions with restrictions

How many ways are there to pay one euro, using coins worth 1, 2, 5, 10, 20, 50, and/or 100 cents? What if you are allowed to use at most two of each coin?

This is Exercise 11 in Knu11, Section 7.2.1.4 (page 408). It goes back to the famous "Ways to change one dollar" problem, see Pol56. Generally, the problem is to generate and/or count partitions satisfying some restrictions. Of course, one could generate the list of all partitions of 100 (there are about 190 million) and then filter the result by the restrictions. But for certain types of restrictions there are much more efficient algorithms. The functions in this section implement some of these. In combination with Julia's filter function one can also handle more general types of restrictions.

For example, there are precisely six ways for the second question in the exercise quoted above:

```
julia> partitions(100, [1,2,5,10,20,50], [2,2,2,2,2,2])
6-element Vector{Partition{Int64}}:
[50, 50]
[50, 20, 20, 10]
[50, 20, 20, 5, 5]
[50, 20, 10, 10, 5, 5]
[50, 20, 20, 5, 2, 2, 1]
[50, 20, 10, 10, 5, 2, 2, 1]
```

and there are 4562 ways for the first question in the exercise:

```
julia> length(partitions(100, [1,2,5,10,20,50]))
4562
```

The original "Ways to change one dollar" problem has 292 solutions:

```
julia> length(partitions(100,[1,5,10,25,50]))
292
```

`partitions`

— Method`partitions(m::T, n::IntegerUnion, l1::IntegerUnion, l2::IntegerUnion; only_distinct_parts::Bool = false) where T <: IntegerUnion`

A list of all partitions of a non-negative integer `m`

into `n >= 0`

parts with lower bound `l1 >= 0`

and upper bound `l2`

for the parts. There are two choices for the parameter `only_distinct_parts`

:

`false`

: no further restriction (*default*);`true`

: only distinct parts. The partitions are produced in*decreasing*order.

**Examples**

We compute all partitions of 7 into 3 parts where all parts are between 1 and 4:

```
julia> partitions(7, 3, 1, 4)
3-element Vector{Partition{Int64}}:
[4, 2, 1]
[3, 3, 1]
[3, 2, 2]
```

Same as above but requiring all parts to be distinct:

```
julia> partitions(7, 3, 1, 4 ; only_distinct_parts=true)
1-element Vector{Partition{Int64}}:
[4, 2, 1]
```

**Algorithm**

The algorithm used is "parta" in W. Riha, K. R. James (1976), de-gotoed from old ALGOL 60 code by E. Thiel.

`partitions`

— Method`partitions(m::T, n::IntegerUnion) where T<:IntegerUnion`

All partitions of a non-negative integer `m`

into `n`

parts (no further restrictions).

**Examples**

```
# All partitions of 7 into 3 parts.
julia> partitions(7, 3)
4-element Vector{Partition{Int64}}:
[5, 1, 1]
[4, 2, 1]
[3, 3, 1]
[3, 2, 2]
```

**Algorithm**

This function is a shortcut for `partitions(m,n,1,m;only_distinct_parts=false)`

.

`num_partitions`

— Method`num_partitions(n::IntegerUnion, k::IntegerUnion)`

The number of integer partitions of the non-negative integer `n`

into `k >= 0`

parts.

**Algorithm**

We use the recurrence relation $p_k(n) = p_{k-1}(n-1) + p_k(n-k)$, where $p_k(n)$ denotes the number of partitions of $n$ into $k$ parts; see Donald E. Knuth (2011), Section 7.2.1.4, Equation (39) on page 399.

**References**

`partitions`

— Method`partitions(m::T, n::IntegerUnion, v::Vector{T}, mu::Vector{S}) where {T<:IntegerUnion, S<:IntegerUnion}`

All partitions of a non-negative integer `m`

into `n >= 0`

parts, where each part is an element in the vector `v`

of positive integers and each `v[i]`

occurs a maximum of `mu[i] > 0`

times. We assume (without loss of generality) that the entries in `v`

are strictly increasing. The partitions are produced in lexicographically *decreasing* order.

**Examples**

We compute the partitions of 100 into seven parts, where the parts are required to be elements from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice.

```
julia> partitions(100, 7, [1,2,5,10,20,50], [2,2,2,2,2,2])
1-element Vector{Partition{Int64}}:
[50, 20, 20, 5, 2, 2, 1]
```

**Algorithm**

The algorithm used is "partb" in W. Riha, K. R. James (1976), de-gotoed from old ALGOL 60 code by E. Thiel. The algorithm as published in the paper has several issues and we hope to have fixed them all, see the code for details. Some initial fixing was done by T. Schmit.

`partitions`

— Method`partitions(m::T, v::Vector{T}, mu::Vector{S}) where {T<:IntegerUnion,S<:IntegerUnion}`

All partitions of a non-negative integer `m`

where each part is an element in the vector `v`

of positive integers and each `v[i]`

occurs a maximum of `mu[i] > 0`

times. We assume (without loss of generality) that the entries in `v`

are strictly increasing.

**Example**

We compute all partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice:

```
julia> partitions(100, [1,2,5,10,20,50], [2,2,2,2,2,2])
6-element Vector{Partition{Int64}}:
[50, 50]
[50, 20, 20, 10]
[50, 20, 20, 5, 5]
[50, 20, 10, 10, 5, 5]
[50, 20, 20, 5, 2, 2, 1]
[50, 20, 10, 10, 5, 2, 2, 1]
```

**Algorithm**

We use the function `partitions(m,n,v,mu)`

, looping over the number of possible parts of partitions.

`partitions`

— Method`function partitions(m::T, v::Vector{T}) where T<:IntegerUnion`

All partitions of a non-negative integer `m`

where each part is an element in the vector `v`

. We assume (without loss of generality) that the entries in `v`

are strictly increasing.

**Example**

We compute the number of partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50}:

```
julia> length(partitions(100, [1,2,5,10,20,50]))
4562
```

**Algorithm**

We use the function `partitions(m,n,v,mu)`

, looping over the number of possible parts of partitions.

## Operations

`conjugate`

— Function`conjugate(lambda::Partition{T}) where T<:IntegerUnion`

The **conjugate** of a partition is obtained by considering its Young diagram (see Tableaux) and then flipping it along its main diagonal.

**Examples**

```
julia> conjugate(Partition(8,8,8,7,2,1,1))
[7, 5, 4, 4, 4, 4, 4, 3]
```

**References**

- William Fulton (1997), page 2
- Donald E. Knuth (2011), Section 7.2.1.4, page 394.

## Relations

`dominates`

— Function`dominates(lambda::Partition, mu::Partition)`

The **dominance order** on partitions is the partial order $⊵$ defined by $λ ⊵ μ$ if and only if $λ₁ + … + λᵢ ≥ μ₁ + … + μᵢ$ for all i. If $λ ⊵ μ$ one says that $λ$ **dominates** $μ$. This function returns true if and only if `lambda`

dominates `mu`

.

Note that whereas the lexicographic ordering is a total ordering, the dominance ordering is not.

**Examples**

```
julia> dominates( Partition(3,1), Partition(2,2) )
true
julia> dominates( Partition(4,1), Partition(3,3) )
false
```

**Remarks**

Donald E. Knuth (2011) says **majorizes** instead of **dominates** and uses the symbol $⪰$ instead of $⊵$.

**References**

- William Fulton (1997), page 26
- Donald E. Knuth (2011), Section 7.2.1.4, Exercise 54 (page 412)