Combinatorics.CoolLexCombinations
— TypeCoolLexCombinations
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.
Base.factorial
— Methodfactorial(n, k)
Compute $n!/k!$.
Combinatorics.bellnum
— Methodbellnum(n)
Compute the $n$th Bell number.
Combinatorics.catalannum
— Methodcatalannum(n)
Compute the $n$th Catalan number.
Combinatorics.character
— Methodcharacter(λ::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
Combinatorics.combinations
— Methodcombinations(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.
Combinatorics.combinations
— Methodcombinations(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.
Combinatorics.derangement
— Methodderangement(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.
Combinatorics.integer_partitions
— Methodinteger_partitions(n)
List the partitions of the integer n
.
The order of the resulting array is consistent with that produced by the computational discrete algebra software GAP.
Combinatorics.isrimhook
— Methodisrimhook(a::Int, b::Int)
Take two elements of a partition sequence, with a
to the left of b
.
Combinatorics.isrimhook
— Methodisrimhook(ξ::SkewDiagram)
isrimhook(λ::Partition, μ::Partition)
Check whether the given skew diagram is a rim hook.
Combinatorics.lassallenum
— Methodlassallenum(n)
Compute the $n$th entry in Lassalle's sequence, OEIS entry A180874.
Combinatorics.leglength
— Methodleglength(ξ::SkewDiagram)
leglength(λ::Partition, μ::Partition)
Compute the leg length for the given skew diagram.
Strictly speaking, the leg length is defined for rim hooks only, but here we define it for all skew diagrams.
Combinatorics.levicivita
— Methodlevicivita(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.
Combinatorics.lobbnum
— Methodlobbnum(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
Combinatorics.multiexponents
— Methodmultiexponents(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 Array{Any,1}:
[2, 0, 0]
[1, 1, 0]
[1, 0, 1]
[0, 2, 0]
[0, 1, 1]
[0, 0, 2]
Combinatorics.multinomial
— Methodmultinomial(k...)
Multinomial coefficient where n = sum(k)
.
Combinatorics.multiset_combinations
— Methodmultiset_combinations(a, t)
Generate all combinations of size t
from an array a
with possibly duplicated elements.
Combinatorics.multiset_permutations
— Methodmultiset_permutations(m, f, t)
Generate all permutations of size t
from an array a
with possibly duplicated elements.
Combinatorics.narayana
— Methodnarayana(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
Combinatorics.nthperm!
— Methodnthperm!(a, k)
In-place version of nthperm
; the array a
is overwritten.
Combinatorics.nthperm
— Methodnthperm(p)
Return the integer k
that generated permutation p
. Note that nthperm(nthperm([1:n], k)) == k
for 1 <= k <= factorial(n)
.
Combinatorics.nthperm
— Methodnthperm(a, k)
Compute the k
th lexicographic permutation of the vector a
.
Combinatorics.parity
— Methodparity(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.
Combinatorics.partialderangement
— Methodpartialderangement(n, k)
Compute the number of permutations of n
with exactly k fixed points.
Combinatorics.partitions
— Methodpartitions(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))
.
Combinatorics.partitions
— Methodpartitions(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 to generate can be efficiently computed using length(partitions(s))
.
Combinatorics.partitions
— Methodpartitions(n, m)
Generate all arrays of m
integers 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))
.
Combinatorics.partitions
— Methodpartitions(n)
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))
.
Combinatorics.partitionsequence
— Methodpartitionsequence(lambda::Partition)
Compute essential part of the partition sequence of lambda
.
Combinatorics.permutations
— Methodpermutations(a, t)
Generate all size t
permutations of an indexable object a
.
Combinatorics.permutations
— Methodpermutations(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.
Combinatorics.powerset
— Functionpowerset(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.
Combinatorics.prevprod
— Methodprevprod(a::Vector{Int}, x)
Previous integer not greater than x
that can be written as $\prod k_i^{p_i}$ for integers $p_1$, $p_2$, etc.
For integers $i_1$, $i_2$, $i_3$, this is equivalent to finding the largest $x$ such that
for integers $n_1$, $n_2$, $n_3$.
Combinatorics.with_replacement_combinations
— Methodwith_replacement_combinations(a, t)
Generate all combinations with replacement of size t
from an array a
.
Combinatorics.MN1inner
— MethodRecursively compute the character of the partition μ
using the Murnaghan-Nakayama rule.