# Partitions

A **partition** of a non-negative integer $n$ is a decreasing sequence $\lambda_1 \geq \lambda_2\geq \dots \geq \lambda_r$ of positive integers $\lambda_i$ such that $n = \lambda_1 + \dots + \lambda_r$. The $\lambda_i$ are called the **parts** of the partition and $r$ is called the **length**. General references on partitions are [Ful97] and [Knu11], Section 7.2.1.4.

A partition can be encoded as an array with elements $\lambda_i$. In OSCAR, the parametric type `Partition{T}`

is provided which is a subtype of `AbstractVector{T}`

. Here, `T`

can be any subtype of `IntegerUnion`

. There is no performance impact by using an own type for partitions rather than simply using arrays. The parametric type allows to increase performance by using smaller integer types.

`partition`

— Function```
partition([T::Type{<:IntegerUnion}], parts::IntegerUnion...; check::Bool = true)
partition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnion
```

Return the partition given by the integer sequence `parts`

as an object of type `Partition{T}`

.

The element type `T`

may be optionally specified, see also the examples below.

If `check`

is `true`

(default), it is checked whether the given sequence defines a partition.

**Examples**

```
julia> P = partition([6, 4, 4, 2]) # the partition 6 + 4 + 4 + 2 of 16
[6, 4, 4, 2]
julia> P = partition(6, 4, 4, 2) # the same partition
[6, 4, 4, 2]
julia> P = partition(Int8, 6, 4, 4, 2) # save the elements in 8-bit integers
Int8[6, 4, 4, 2]
```

Because `Partition`

is a subtype of `AbstractVector`

, all functions that can be used for vectors (1-dimensional arrays) can be used for partitions as well.

```
julia> P = partition(6, 4, 4, 2)
[6, 4, 4, 2]
julia> length(P)
4
julia> P[1]
6
```

However, usually, $|\lambda| := n$ is called the **size** of $\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> P = partition(6, 4, 4, 2)
[6, 4, 4, 2]
julia> sum(P)
16
```

In algorithms involving partitions it is sometimes convenient to be able to access parts beyond the length of the partition and then one wants to get the value zero instead of an error. For this, OSCAR provides the function `getindex_safe`

:

`getindex_safe`

— Function`getindex_safe(P::Partition, i::IntegerUnion)`

Return `P[i]`

if `i < length(P)`

and `0`

otherwise. It is assumed that `i`

is positive.

**Examples**

```
julia> P = partition([3, 2, 1])
[3, 2, 1]
julia> getindex_safe(P, 3)
1
julia> getindex_safe(P, 4)
0
```

If you are sure that `P[i]`

exists, use `getindex`

because this will be faster.

## Generating and counting

`partitions`

— Method`partitions(n::IntegerUnion)`

Return an iterator over all partitions of a non-negative integer `n`

, produced in lexicographically *descending* order. Using a smaller integer type for `n`

(e.g. `Int8`

) may increase performance.

The algorithm used is "Algorithm ZS1" by [ZS98]. This algorithm is also discussed in [Knu11], Algorithm P (page 392).

**Examples**

```
julia> p = partitions(4);
julia> first(p)
[4]
julia> collect(p)
5-element Vector{Partition{Int64}}:
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]
julia> collect(partitions(Int8(4))) # using less memory
5-element Vector{Partition{Int8}}:
Int8[4]
Int8[3, 1]
Int8[2, 2]
Int8[2, 1, 1]
Int8[1, 1, 1, 1]
```

`number_of_partitions`

— Method`number_of_partitions(n::IntegerUnion)`

Return the number of integer partitions of `n`

. For `n < 0`

, return `0`

.

**Examples**

```
julia> number_of_partitions(1000)
24061467864032622473692149727991
```

For counting partitions, the Hardy-Ramanujan-Rademachen formula is used, see [Joh12] for details. See also [Knu11], Section 7.2.1.4 and [OEIS], A000041.

### Partitions with restrictions

How many ways are there to pay one euro, using coins worth 1, 2, 5, 10, 20, 50, and/or 100 cents? What if you are allowed to use at most two of each coin?

This is Exercise 11 in [Knu11], Section 7.2.1.4. It goes back to the famous "Ways to change one dollar" problem, see [Pol56]. Generally, the problem is to generate and/or count partitions satisfying some restrictions. Of course, one could generate the list of all partitions of 100 (there are about 190 million) and then filter the result by the restrictions. But for certain types of restrictions there are much more efficient algorithms. The functions in this section implement some of these. In combination with Julia's filter function one can also handle more general types of restrictions.

For example, there are precisely six ways for the second question in the exercise quoted above:

```
julia> collect(partitions(100, [1, 2, 5, 10, 20, 50], [2, 2, 2, 2, 2, 2]))
6-element Vector{Partition{Int64}}:
[50, 50]
[50, 20, 20, 10]
[50, 20, 20, 5, 5]
[50, 20, 10, 10, 5, 5]
[50, 20, 20, 5, 2, 2, 1]
[50, 20, 10, 10, 5, 2, 2, 1]
```

and there are 4562 ways for the first question in the exercise:

```
julia> length(collect(partitions(100, [1, 2, 5, 10, 20, 50])))
4562
```

The original "Ways to change one dollar" problem has 292 solutions:

```
julia> length(collect(partitions(100, [1, 5, 10, 25, 50])))
292
```

`number_of_partitions`

— Method`number_of_partitions(n::IntegerUnion, k::IntegerUnion)`

Return the number of integer partitions of the non-negative integer `n`

into `k >= 0`

parts. If `n < 0`

or `k < 0`

, return `0`

.

For counting the partitions the recurrence relation $p_k(n) = p_{k - 1}(n - 1) + p_k(n - k)$ is used, where $p_k(n)$ denotes the number of partitions of $n$ into $k$ parts; see [Knu11], Section 7.2.1.4, Equation (39), and also [OEIS], A008284.

`partitions`

— Method```
partitions(n::IntegerUnion, k::IntegerUnion; only_distinct_parts::Bool = false)
partitions(n::IntegerUnion, k::IntegerUnion, lb::IntegerUnion, ub::IntegerUnion; only_distinct_parts::Bool = false)
```

Return an iterator over all partitions of a non-negative integer `n`

into `k >= 0`

parts. Optionally, a lower bound `lb >= 0`

and an upper bound `ub`

for the parts can be supplied. In this case, the partitions are produced in *decreasing* order.

There are two choices for the parameter `only_distinct_parts`

:

`false`

: no further restriction (*default*);`true`

: only distinct parts.

The implemented algorithm is "parta" in [RJ76].

**Examples**

All partitions of 7 into 3 parts:

```
julia> collect(partitions(7, 3))
4-element Vector{Partition{Int64}}:
[5, 1, 1]
[4, 2, 1]
[3, 3, 1]
[3, 2, 2]
```

All partitions of 7 into 3 parts where all parts are between 1 and 4:

```
julia> collect(partitions(7, 3, 1, 4))
3-element Vector{Partition{Int64}}:
[4, 2, 1]
[3, 3, 1]
[3, 2, 2]
```

Same as above but requiring all parts to be distinct:

```
julia> collect(partitions(7, 3, 1, 4; only_distinct_parts = true))
1-element Vector{Partition{Int64}}:
[4, 2, 1]
```

`partitions`

— Method```
partitions(n::T, v::Vector{T}) where T <: IntegerUnion
partitions(n::T, v::Vector{T}, mu::Vector{<:IntegerUnion}) where T <: IntegerUnion
partitions(n::T, k::IntegerUnion, v::Vector{T}, mu::Vector{<:IntegerUnion}) where T <: IntegerUnion
```

Return an iterator over all partitions of a non-negative integer `n`

where each part is an element in the vector `v`

of positive integers. It is assumed that the entries in `v`

are strictly increasing.

If the optional vector `mu`

is supplied, then each `v[i]`

occurs a maximum of `mu[i] > 0`

times per partition.

If the optional integer `k >= 0`

is supplied, the partitions will be into `k`

parts. In this case, the partitions are produced in lexicographically *decreasing* order.

The implemented algorithm is "partb" in [RJ76].

**Example**

The number of partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50}:

```
julia> length(collect(partitions(100, [1, 2, 5, 10, 20, 50])))
4562
```

All partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice:

```
julia> collect(partitions(100, [1, 2, 5, 10, 20, 50], [2, 2, 2, 2, 2, 2]))
6-element Vector{Partition{Int64}}:
[50, 50]
[50, 20, 20, 10]
[50, 20, 20, 5, 5]
[50, 20, 10, 10, 5, 5]
[50, 20, 20, 5, 2, 2, 1]
[50, 20, 10, 10, 5, 2, 2, 1]
```

The partitions of 100 into seven parts, where the parts are required to be elements from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice.

```
julia> collect(partitions(100, 7, [1, 2, 5, 10, 20, 50], [2, 2, 2, 2, 2, 2]))
1-element Vector{Partition{Int64}}:
[50, 20, 20, 5, 2, 2, 1]
```

## Operations

The *conjugate* of a partition $\lambda$ is obtained by considering its Young diagram (see Tableaux) and then flipping it along its main diagonal, see [Ful97], page 2, and [Knu11], Section 7.2.1.4.

`conjugate`

— Function`conjugate(lambda::Partition)`

Return the conjugate of the partition `lambda`

.

**Examples**

```
julia> conjugate(partition(8, 8, 8, 7, 2, 1, 1))
[7, 5, 4, 4, 4, 4, 4, 3]
```

## Relations

The **dominance order** on partitions is the partial order $\trianglerighteq$ defined by $\lambda \trianglerighteq\mu$ if and only if $\lambda_1 + \dots + \lambda_i \geq \mu_1 + \dots + \mu_i$ for all $i$. If $\lambda\trianglerighteq\mu$ one says that $\lambda$ **dominates** $\mu$. See [Ful97], page 26, and [Knu11], Section 7.2.1.4, Exercise 54.

Note that whereas the lexicographic ordering is a total ordering, the dominance ordering is not. Further, [Knu11] says **majorizes** instead of **dominates** and uses the symbol $\succeq$ instead of $\trianglerighteq$.

`dominates`

— Function`dominates(lambda::Partition, mu::Partition)`

Return `true`

if `lambda`

dominates `mu`

, `false`

otherwise.

**Examples**

```
julia> dominates(partition(3, 1), partition(2, 2))
true
julia> dominates(partition(4, 1), partition(3, 3))
false
```