API reference

CoolLexCombinations

Produce $(n,k)$-combinations in cool-lex order.

Reference

Ruskey, F., & Williams, A. (2009). The coolest way to generate combinations. Discrete Mathematics, 309(17), 5305-5320.

combinations(a, n)

Generate all combinations of n elements from an indexable object a. Because the number of combinations can be very large, this function returns an iterator object. Use collect(combinations(a, n)) to get an array of all combinations.

combinations(a)

Generate combinations of the elements of a of all orders. Chaining of order iterators is eager, but the sequence at each order is lazy.

multiset_combinations(a, t)

Generate all combinations of size t from an array a with possibly duplicated elements.

powerset(a, min=0, max=length(a))

Generate all subsets of an indexable object a including the empty set, with cardinality bounded by min and max. Because the number of subsets can be very large, this function returns an iterator object. Use collect(powerset(a, min, max)) to get an array of all subsets.

with_replacement_combinations(a, t)

Generate all combinations with replacement of size t from an array a.

factorial(n, k)

Compute $n!/k!$.

derangement(n)

Compute the number of permutations of n with no fixed points, also known as the subfactorial. An alias subfactorial for this function is provided for convenience.

multinomial(k...)

Compute the multinomial coefficient $\binom{n}{k_1,k_2,...,k_i} = \frac{n!}{k_1!k_2! \cdots k_i!}, n = \sum{k_i}$. Throws an OverflowError when the input is too large.

See Also: binomial.

Examples

julia> # (x+y)^2 = x^2 + 2xy + y^2

julia> multinomial(2, 0)
1

julia> multinomial(1, 1)
2

julia> multinomial(0, 2)
1

julia> multinomial(10, 10, 10, 10)
ERROR: OverflowError: 5550996791340 * 847660528 overflowed for type Int64
Stacktrace:
[...]

External links

• Definitions on DLMF
• Multinomial theorem on Wikipedia

partialderangement(n, k)

Compute the number of permutations of n with exactly k fixed points.

multiexponents(m, n)

Returns the exponents in the multinomial expansion (x₁ + x₂ + ... + xₘ)ⁿ.

For example, the expansion (x₁ + x₂ + x₃)² = x₁² + x₁x₂ + x₁x₃ + ... has the exponents:

julia> collect(multiexponents(3, 2))
6-element Vector{Vector{Int64}}:
 [2, 0, 0]
 [1, 1, 0]
 [1, 0, 1]
 [0, 2, 0]
 [0, 1, 1]
 [0, 0, 2]

bellnum(n)

Compute the $n$th Bell number.

catalannum(n)

Compute the $n$th Catalan number.

lassallenum(n)

Compute the $n$th entry in Lassalle's sequence, OEIS entry A180874.

lobbnum(m,n)

Compute the Lobb number L(m,n), or the generalised Catalan number given by $\frac{2m+1}{m+n+1} \binom{2n}{m+n}$. Wikipedia : https://en.wikipedia.org/wiki/Lobb_number

narayana(n,k)

Compute the Narayana number N(n,k) given by $\frac{1}{n}\binom{n}{k}\binom{n}{k-1}$ Wikipedia : https://en.wikipedia.org/wiki/Narayana_number

stirlings1(n::Integer, k::Integer)

Compute the Stirling number of the first kind, s(n,k).

stirlings2(n::Integer, k::Integer)

Compute the Stirling number of the second kind, S(n,k).

integer_partitions(n)

Generates all partitions of the integer n as a list of integer arrays, where each partition represents a way to write n as a sum of positive integers.

See also: partitions(n::Integer)

Examples

julia> integer_partitions(2)
2-element Vector{Vector{Int64}}:
 [1, 1]
 [2]

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

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

julia> integer_partitions(-1)
ERROR: DomainError with -1:
n must be nonnegative
Stacktrace:
[...]

References

• Integer partition - Wikipedia

ncpartitions(n::Int)

Generates all noncrossing partitions of a set of n elements, returning them as a Vector of partition representations.

The number of noncrossing partitions of an n-element set is given by the n-th Catalan number Cn: length(ncpartitions(n)) == catalannum(n).

See also: catalannum

Examples

julia> ncpartitions(1)
1-element Vector{Vector{Vector{Int64}}}:
 [[1]]

julia> ncpartitions(3)
5-element Vector{Vector{Vector{Int64}}}:
 [[1], [2], [3]]
 [[1], [2, 3]]
 [[1, 2], [3]]
 [[1, 3], [2]]
 [[1, 2, 3]]

julia> catalannum(3)
5

julia> length(ncpartitions(6)) == catalannum(6)
true

References

• Noncrossing partition - Wikipedia

partitions(s::AbstractVector, m::Int)

Generate all set partitions of the elements of an array s into exactly m subsets, represented as arrays of arrays.

Because the number of partitions can be very large, this function returns an iterator object. Use collect(partitions(s, m)) to get an array of all partitions.

The number of partitions into m subsets is equal to the Stirling number of the second kind, and can be efficiently computed using length(partitions(s, m)).

See also: stirlings2(n::Int, k::Int)

Examples

julia> collect(partitions('a':'c', 3))
1-element Vector{Vector{Vector{Char}}}:
 [['a'], ['b'], ['c']]

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

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

julia> stirlings2(3, 2)
3

julia> length(partitions(1:10, 3)) == stirlings2(10, 3)
true

References

• Partition of a set - Wikipedia

partitions(s::AbstractVector)

Generate all set partitions of the elements of an array s, represented as arrays of arrays.

Because the number of partitions can be very large, this function returns an iterator object. Use collect(partitions(s)) to get an array of all partitions.

The number of partitions of an n-element set is given by the n-th Bell number Bn: length(partitions(s)) == bellnum(length(s)).

See also: bellnum

Examples

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

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

julia> collect(partitions('a':'c'))
5-element Vector{Vector{Vector{Char}}}:
 [['a', 'b', 'c']]
 [['a', 'b'], ['c']]
 [['a', 'c'], ['b']]
 [['a'], ['b', 'c']]
 [['a'], ['b'], ['c']]

julia> length(partitions(1:10)) == bellnum(10)
true

References

• Partition of a set - Wikipedia

partitions(n::Integer, m::Integer)

Generate all integer partitions of n into exactly m parts, that sum to n.

Because the number of partitions can be very large, this function returns an iterator object. Use collect(partitions(n, m)) to get an array of all partitions.

The number of partitions to generate can be efficiently computed using length(partitions(n, m)).

See also: partitions(n::Integer)

Examples

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

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

julia> collect(partitions(4, 4))
1-element Vector{Vector{Int64}}:
 [1, 1, 1, 1]

julia> collect(partitions(4, 5))
Vector{Int64}[]

julia> partitions(4, 0)
ERROR: DomainError with (4, 0):
n and m must be positive
Stacktrace:
[...]

partitions(n::Integer)

Generate all integer arrays that sum to n.

Because the number of partitions can be very large, this function returns an iterator object. Use collect(partitions(n)) to get an array of all partitions.

The number of partitions to generate can be efficiently computed using length(partitions(n)).

See also:

• integer_partitions(n::Integer) for a non-iterator version that returns all partitions as a array
• partitions(n::Integer, m::Integer) for partitions with exactly m parts.

Examples

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

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

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

julia> first(partitions(10))
1-element Vector{Int64}:
 10

julia> length(partitions(10))
42

References

• Integer partition - Wikipedia

prevprod(a::Vector{Int}, x)

Find the largest integer not greater than x that can be expressed as a product of powers of the elements in a.

This function computes the largest value y ≤ x that can be written as:

\[y = \prod a_i^{n_i} = a_1^{n_1} a_2^{n_2} \cdots a_k^{n_k} \leq x\]

where $n_i$ is a non-negative integer, k is the length of Vector a.

Examples

julia> prevprod([10], 1000)   # 1000 = 10^3
1000

julia> prevprod([2, 5], 30)   # 25 = 2^0 * 5^2
25

julia> prevprod([2, 3], 100)  # 96 = 2^5 * 3^1
96

julia> prevprod([2, 3, 5], 1) # 1 = 2^0 * 3^0 * 5^0
1

derangements(a)

Generate all derangements of an indexable object a in lexicographic order. Because the number of derangements can be very large, this function returns an iterator object. Use collect(derangements(a)) to get an array of all derangements. Only works for a with defined length.

Examples

julia> derangements("julia") |> collect
44-element Vector{Vector{Char}}:
 ['u', 'j', 'i', 'a', 'l']
 ['u', 'j', 'a', 'l', 'i']
 ['u', 'l', 'j', 'a', 'i']
 ['u', 'l', 'i', 'a', 'j']
 ['u', 'l', 'a', 'j', 'i']
 ['u', 'i', 'j', 'a', 'l']
 ['u', 'i', 'a', 'j', 'l']
 ['u', 'i', 'a', 'l', 'j']
 ['u', 'a', 'j', 'l', 'i']
 ['u', 'a', 'i', 'j', 'l']
 ⋮
 ['a', 'j', 'i', 'l', 'u']
 ['a', 'l', 'j', 'u', 'i']
 ['a', 'l', 'u', 'j', 'i']
 ['a', 'l', 'i', 'j', 'u']
 ['a', 'l', 'i', 'u', 'j']
 ['a', 'i', 'j', 'u', 'l']
 ['a', 'i', 'j', 'l', 'u']
 ['a', 'i', 'u', 'j', 'l']
 ['a', 'i', 'u', 'l', 'j']

levicivita(p)

Compute the Levi-Civita symbol of a permutation p. Returns 1 if the permutation is even, -1 if it is odd, and 0 otherwise.

The parity is computed by using the fact that a permutation is odd if and only if the number of even-length cycles is odd.

Examples

julia> levicivita([1, 2, 3])
1

julia> levicivita([3, 2, 1])
-1

julia> levicivita([1, 1, 1])
0

julia> levicivita(collect(1:100))
1

julia> levicivita(ones(Int, 100))
0

multiset_permutations(a, t)

Generate all permutations of size t from an array a where a may have duplicated elements.

Examples

julia> collect(permutations([1,1,1], 2))
6-element Vector{Vector{Int64}}:
 [1, 1]
 [1, 1]
 [1, 1]
 [1, 1]
 [1, 1]
 [1, 1]

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

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

multiset_permutations(a)

Generate all permutations of an array a where a may have duplicated elements.

nthperm!(a, k)

In-place version of nthperm; the array a is overwritten.

Examples

julia> a = [1, 2, 3];

julia> collect(permutations(a))
6-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

julia> nthperm!(a, 3); a
3-element Vector{Int64}:
 2
 1
 3

julia> nthperm!(a, 4); a
3-element Vector{Int64}:
 1
 3
 2

julia> nthperm!(a, 0)
ERROR: ArgumentError: permutation k must satisfy 0 < k ≤ 6, got 0
[...]

nthperm(a, k)

Compute the kth lexicographic permutation of the vector a.

Examples

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

julia> nthperm([1,2], 1)
2-element Vector{Int64}:
 1
 2

julia> nthperm([1,2], 2)
2-element Vector{Int64}:
 2
 1

julia> nthperm([1,2], 3)
ERROR: ArgumentError: permutation k must satisfy 0 < k ≤ 2, got 3
[...]

nthperm(p)

Return the integer k that generated permutation p. Note that nthperm(nthperm([1:n], k)) == k for 1 <= k <= factorial(n).

Examples

julia> nthperm(nthperm([1:3...], 4))
4

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

julia> nthperm([1, 2, 3])
1

julia> nthperm([3, 2, 1])
6

julia> nthperm([1, 1, 1])
ERROR: ArgumentError: argument is not a permutation
[...]

julia> nthperm(collect(1:10))
1

julia> nthperm(collect(10:-1:1))
3628800

parity(p)

Compute the parity of a permutation p using the levicivita function, permitting calls such as iseven(parity(p)). If p is not a permutation then an error is thrown.

Examples

julia> parity([1, 2, 3])
0

julia> parity([3, 2, 1])
1

julia> parity([1, 1, 1])
ERROR: ArgumentError: Not a permutation
[...]

julia> parity((collect(1:100)))
0

permutations(a, t)

Generate all size t permutations of an indexable object a. Only works for a with defined length. If (t <= 0) || (t > length(a)), then returns an empty vector of eltype of a

Examples

julia> [ (len, permutations(1:3, len)) for len in -1:4 ]
6-element Vector{Tuple{Int64, Any}}:
 (-1, Vector{Int64}[])
 (0, [Int64[]])
 (1, [[1], [2], [3]])
 (2, Combinatorics.Permutations{UnitRange{Int64}}(1:3, 2))
 (3, Combinatorics.Permutations{UnitRange{Int64}}(1:3, 3))
 (4, Vector{Int64}[])

julia> [ (len, collect(permutations(1:3, len))) for len in -1:4 ]
6-element Vector{Tuple{Int64, Vector{Vector{Int64}}}}:
 (-1, [])
 (0, [[]])
 (1, [[1], [2], [3]])
 (2, [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]])
 (3, [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]])
 (4, [])

permutations(a)

Generate all permutations of an indexable object a in lexicographic order. Because the number of permutations can be very large, this function returns an iterator object. Use collect(permutations(a)) to get an array of all permutations. Only works for a with defined length.

Examples

julia> permutations(1:2)
Combinatorics.Permutations{UnitRange{Int64}}(1:2, 2)

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

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

Recursively compute the character of the partition μ using the Murnaghan-Nakayama rule.

character(λ::Partition, μ::Partition)

Compute the character $\chi^{\lambda(\mu)}$ of the partition μ in the λth irreducible representation ("irrep") of the symmetric group $S_n$.

Implements the Murnaghan-Nakayama algorithm as described in:

Dan Bernstein,
"The computational complexity of rules for the character table of Sn",
Journal of Symbolic Computation, vol. 37 iss. 6 (2004), pp 727-748.
doi:10.1016/j.jsc.2003.11.001

isrimhook(a::Int, b::Int)

Take two elements of a partition sequence, with a to the left of b.

isrimhook(ξ::SkewDiagram)
isrimhook(λ::Partition, μ::Partition)

Check whether the given skew diagram is a rim hook.

leglength(ξ::SkewDiagram)
leglength(λ::Partition, μ::Partition)

Compute the leg length for the given skew diagram.

partitionsequence(lambda::Partition)

Compute essential part of the partition sequence of lambda.