Compositions

Composition{T<:Integer} <: AbstractArray{T,1}

A composition (also called ordered partition) of an integer n ≥ 0 is a sequence (λ₁,…,λₖ) of positive integers λᵢ whose sum is equal to n. The λᵢ are called the parts of the composition.

Examples

julia> c=Composition([2,1])
[2, 1]
julia> sum(c)
3
julia> c[1]
2

References

1. Wikipedia, Composition (combinatorics)
2. Bóna, M. (2017). A Walk Through Combinatorics (Fourth Edition). World Scientific.

struct Compositions{T<:Integer}

Returns an iterator over all compositions of an integer n. The iterator simply iterates over compositions of n into k parts for 1 ≤ k ≤ n using CompositionsFixedNumParts.

Examples

compositons(n::Integer)

Returns the full list of compositions of n using the Compositions iterator.

num_compositions(n::Integer)

The number of compositions of an integer $n ≥ 0$ is equal to

\[\left\lbrace \begin{array}{ll} 1 & \text{if } n = 0 \\ 2^{n-1} & \text{if } n ≥ 1 \;. \end{array} \right.\]

See Corollary 5.4 of Bóna (2017).

References

1. The On-Line Encyclopedia of Integer Sequences, A011782
2. Bóna, M. (2017). A Walk Through Combinatorics (Fourth Edition). World Scientific.

compositons(n::Integer, k::Integer)

Returns the full list of compositions of n into k parts using the CompositionsFixedNumParts iterator.

num_compositions(n::Integer, k::Integer)

The number of compositions of an integer $n ≥ 0$ into $k ≥ 0$ parts is equal to

\[\left\lbrace \begin{array}{ll} 1 & \text{if } n=k=0 \\ {n-1 \choose k-1} & \text{otherwise} \;. \end{array} \right.\]

See Corollary 5.3 of Bóna (2017).

References

1. Bóna, M. (2017). A Walk Through Combinatorics (Fourth Edition). World Scientific.