# Partitions

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

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, with the possibility to provide the element type as the first argument.

Examples

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

1. William Fulton (1997)
2. Donald E. Knuth (2011), Section 7.2.1.4 (starting on page 390).
source
getindex_safeFunction
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
source

## Generating and counting

partitionsMethod
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]
source
num_partitionsMethod
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

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

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

source
partitionsMethod
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).

source
num_partitionsMethod
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

1. OEIS Foundation Inc. (2023), A008284
source
partitionsMethod
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.

source
partitionsMethod
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.

source
partitionsMethod
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.

source

## Operations

conjugateFunction
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

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

## Relations

dominatesFunction
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

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