Multipartitions

Multipartition{T} <: AbstractArray{Partition{T},1}

Multipartitions are generalizations of partitions. An r-component multipartition of an integer n is an r-tuple of partitions λ¹, λ², …, λʳ where each λⁱ is a partition of some integer nᵢ ≥ 0 and the nᵢ sum to n.

Multipartitions are implemented as a subtype of 1-dimensional arrays of partitions. You can use smaller integer types to increase performance.

Examples

julia> P=Multipartition( [[2,1], [], [3,2,1]] )
Partition{Int64}[[2, 1], [], [3, 2, 1]]
julia> sum(P)
9
julia> P[2]
Int64[]
julia> P=Multipartition( Array{Int8,1}[[2,1], [], [3,2,1]] )
Partition{Int8}[[2, 1], [], [3, 2, 1]]

References

1. Wikipedia, Multipartition

multipartitions(n::T, r::Integer) where T<:Integer

A list of all r-component multipartitions of n. The algorithm is recursive and based on partitions(::Integer).

Example

julia> multipartitions(2,2)
5-element Vector{Multipartition{Int64}}:
 Partition{Int64}[[], [2]]
 Partition{Int64}[[], [1, 1]]
 Partition{Int64}[[1], [1]]
 Partition{Int64}[[2], []]
 Partition{Int64}[[1, 1], []]

num_multipartitions(n::Int, k::Int)

The number of multipartitions of $n$ into $k$ parts is equal to

\[\sum_{a=1}^k {k \choose a} \sum_{λ} p(λ₁) p(λ₂) ⋯ p(λ_a) \;,\]

where the second sum is over all compositions $λ$ of $n$ into $a$ parts. I found this formula in the Proof of Lemma 2.4 in Craven (2006).

References

1. Craven, D. (2006). The Number of t-Cores of Size n. http://web.mat.bham.ac.uk/D.A.Craven/docs/papers/tcores0608.pdf

sum(P::Multipartition{T}) where T<:Integer

If P is a multipartition of the integer n, this function returns n.