API reference

Combinations

Combinatorics.CoolLexCombinations — Type

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.

source

Combinatorics.combinations — Method

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.

source

Combinatorics.combinations — Method

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.

source

Combinatorics.multiset_combinations — Method

multiset_combinations(a, t)

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

source

Combinatorics.powerset — Function

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.

source

Combinatorics.with_replacement_combinations — Method

with_replacement_combinations(a, t)

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

source

Factorials

Base.factorial — Method

factorial(n, k)

Compute $n!/k!$.

source

Combinatorics.derangement — Method

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.

source

Combinatorics.multinomial — Method

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.

Multinomials

Combinatorics.multiexponents — Method

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]

source

Numbers

Combinatorics.bellnum — Method

bellnum(n)

Compute the $n$th Bell number.

source

Combinatorics.catalannum — Method

catalannum(n)

Compute the $n$th Catalan number.

source

Combinatorics.lassallenum — Method

lassallenum(n)

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

source

Combinatorics.lobbnum — Method

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

source

Combinatorics.narayana — Method

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

source

Combinatorics.stirlings2 — Method

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

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

source

Partitions

Combinatorics.integer_partitions — Method

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.

Permutations

Combinatorics.derangements — Method

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

source

Combinatorics.levicivita — Method

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

source

Combinatorics.multiset_permutations — Method

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]

source

Combinatorics.multiset_permutations — Method

multiset_permutations(a)

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

source

Combinatorics.nthperm! — Method

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
[...]

source

Combinatorics.nthperm — Method

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
[...]

source

Combinatorics.nthperm — Method

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

source

Combinatorics.parity — Method

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

source

Combinatorics.permutations — Method

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, [])

source

Combinatorics.permutations — Method

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]

source

Young diagrams

Combinatorics.MN1inner — Method

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

source

Combinatorics.character — Method

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

source

Combinatorics.isrimhook — Method

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

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

source

Combinatorics.isrimhook — Method

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

Check whether the given skew diagram is a rim hook.

source

Combinatorics.leglength — Method

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

Compute the leg length for the given skew diagram.

Note

Strictly speaking, the leg length is defined for rim hooks only, but here we define it for all skew diagrams.

source

Combinatorics.partitionsequence — Method

partitionsequence(lambda::Partition)

Compute essential part of the partition sequence of lambda.

source