Multipartitions

Multipartitions are generalizations of partitions. An $r$-component multipartition of an integer $n$ is an $r$-tuple of partitions $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_r)$ where each $\lambda_i$ is a partition of some integer $n_i \geq 0$ and the $n_i$ sum to $n$. For an overview of multipartitions, see [And08].

A multipartition can be encoded as a 1-dimensional array whose elements are partitions. In OSCAR, we provide the parametric type Multipartition{T} which is a subtype of AbstractVector{T}, where T can by any subtype of IntegerUnion. By using smaller integer types when appropriate, this allows performance to be improved.

multipartition — Function

multipartition(mp::Vector{Partition{T}}) where T <: IntegerUnion
multipartition(mp::Vector{Vector{T}}) where T <: IntegerUnion

Return the multipartition given by the vector mp of integer sequences mp (which are interpreted as integer partitions) as an object of type Multipartition{T}. Note that a partition must be given by a weakly descending integer sequence.

The element type T may be optionally specified, see also the examples below.

Examples

julia> P = multipartition([[2,1], [], [3,2,1]])
Partition{Int64}[[2, 1], [], [3, 2, 1]]

julia> sum(P)
9

julia> P[2]
Empty partition

julia> P = multipartition(Vector{Int8}[[2,1], [], [3,2,1]])
Partition{Int8}[[2, 1], [], [3, 2, 1]]

source

Because Multipartition is a subtype of AbstractVector, all functions that can be used for vectors (1-dimensional arrays) can be used for multipartitions as well.

julia> MP = multipartition([[3, 2], [1, 1], [3, 1]])
Partition{Int64}[[3, 2], [1, 1], [3, 1]]

julia> length(MP)
3

julia> MP[1]
[3, 2]

However, usually, $|\lambda| := n$ is called the size of a multipartition $\lambda$. In Julia, the function size for arrays already exists and returns the dimension of an array. Instead, one can use the Julia function sum to get the sum of the parts.

julia> MP = multipartition([[3, 2], [1, 1], [3, 1]])
Partition{Int64}[[3, 2], [1, 1], [3, 1]]

julia> sum(MP)
11

Generating and counting

multipartitions — Method

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

A list of all r-component multipartitions of n, as elements of type Multipartitoon{T}. The algorithm is recursive and based on partitions(::IntegerUnion).

Example

julia> MP = multipartitions(2,2);

julia> first(MP)
Partition{Int64}[[], [2]]

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

source

number_of_multipartitions — Method

number_of_multipartitions(n::IntegerUnion, k::IntegerUnion)

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

\[\sum_{a=1}^k {k \choose a} \sum_{\lambda} p(\lambda_1) p(\lambda_2) \cdots p(\lambda_a) \;,\]

where the second sum is over all compositions $\lambda$ of $n$ into $a$ parts. This formula is due to [Cra06, Proof of Lemma 2.4].

source