# 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]
```

`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]
```

## 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]
```

`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`

.

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]
```

`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`

.

### 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]
```

`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`

.

### 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]
```

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