Compositions

A weak composition of a non-negative integer $n$ is a sequence $\lambda_1,\dots,\lambda_k$ of non-negative integers $\lambda_i$ such that $n = \lambda_1 + \dots + \lambda_k$. A composition of $n$ is a weak composition consisting of positive integers. The $\lambda_i$ are called the parts of the (weak) composition.

weak_composition — Function

weak_composition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnion

Return the weak composition given by the integer sequence parts as an object of type WeakComposition{T}.

If check is true (default), it is checked whether the given sequence defines a weak composition, that is, whether all elements of parts are non-negative.

Examples

julia> W = weak_composition([6, 0, 2, 3]) # the weak composition 6, 0, 2, 3 of 11
[6, 0, 2, 3]

julia> W = weak_composition(Int8[6, 0, 2, 3]) # save the elements in 8-bit integers
Int8[6, 0, 2, 3]

source

composition — Function

composition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnion

Return the composition given by the integer sequence parts as an object of type Composition{T}.

If check is true (default), it is checked whether the given sequence defines a composition, that is, whether all elements of parts are positive.

Examples

julia> C = composition([6, 1, 2, 3]) # the composition 6, 1, 2, 3 of 12
[6, 1, 2, 3]

julia> C = composition(Int8[6, 1, 2, 3]) # save the elements in 8-bit integers
Int8[6, 1, 2, 3]

source

Generating and counting

Unrestricted compositions

compositions — Method

compositions(n::IntegerUnion)

Return an iterator over all compositions of a non-negative integer n.

By a composition of n we mean a sequence of positive integers whose sum is n.

Examples

julia> C = compositions(4)
Iterator over the compositions of 4

julia> collect(C)
8-element Vector{Composition{Int64}}:
 [4]
 [3, 1]
 [2, 2]
 [1, 3]
 [2, 1, 1]
 [1, 2, 1]
 [1, 1, 2]
 [1, 1, 1, 1]

source

number_of_compositions — Method

number_of_compositions(n::IntegerUnion)

Return the number of compositions of the non-negative integer n. For n < 0, return 0.

source

Note that an integer $n$ has infinitely many weak compositions as one may always append zeros to the end of a given weak composition. Without restrictions on the number of parts, we can hence only generate compositions, but not weak compositions.

Restricted compositions

compositions — Method

compositions(n::IntegerUnion, k::IntegerUnion)

Return an iterator over all compositions of a non-negative integer n into k parts, produced in lexicographically descending order.

By a composition of n into k parts we mean a sequence of k positive integers whose sum is n.

Examples

julia> C = compositions(4, 2)
Iterator over the compositions of 4 into 2 parts

julia> collect(C)
3-element Vector{Composition{Int64}}:
 [3, 1]
 [2, 2]
 [1, 3]

source

number_of_compositions — Method

number_of_compositions(n::IntegerUnion, k::IntegerUnion)

Return the number of compositions of the non-negative integer n into k >= 0 parts. If n < 0 or k < 0, return 0.

source

Restricted weak compositions

weak_compositions — Function

weak_compositions(n::IntegerUnion, k::IntegerUnion)

Return an iterator over all weak compositions of a non-negative integer n into k parts, produced in lexicographically descending order. Using a smaller integer type for n (e.g. Int8) may increase performance.

By a weak composition of n into k parts we mean a sequence of k non-negative integers whose sum is n.

Examples

julia> W = weak_compositions(3, 2)
Iterator over the weak compositions of 3 into 2 parts

julia> length(W)
4

julia> collect(W)
4-element Vector{WeakComposition{Int64}}:
 [3, 0]
 [2, 1]
 [1, 2]
 [0, 3]

source

number_of_weak_compositions — Method

number_of_weak_compositions(n::IntegerUnion, k::IntegerUnion)

Return the number of weak compositions of the non-negative integer n into k >= 0 parts. If n < 0 or k < 0, return 0.

source

Ascending compositions

ascending_compositions — Function

ascending_compositions(n::IntegerUnion)

Return an iterator over all ascending compositions of a non-negative integer n.

By a ascending composition of n we mean a non-decreasing sequence of positive integers whose sum is n.

The implemented algorithm is "AccelAsc" (Algorithm 4.1) in [KO14].

Examples

julia> C = ascending_compositions(4)
Iterator over the ascending compositions of 4

julia> collect(C)
5-element Vector{Composition{Int64}}:
 [1, 1, 1, 1]
 [1, 1, 2]
 [1, 3]
 [2, 2]
 [4]

source

The number of ascending compositions of $n$ coincides with the number of partitions of $n$.