mathematicskit.combinatorics

mathematicskit.combinatorics hub · History · Examples · API reference

Permutation/combination counting via scipy.special.perm/comb (sequence generation via itertools); binomial/multinomial coefficients, with a hand-rolled Pascal’s-triangle build kept as a pedagogical illustration; integer partitions and Young/Ferrers diagrams; the inclusion-exclusion principle and derangements; Stirling numbers, Catalan numbers, and Bell numbers.

mathematicskit.combinatorics: combinatorial mathematics.

Permutation and combination counting via scipy.special.perm/comb (sequence generation, which scipy doesn’t provide, is mathematicskit’s own thin wrapper around itertools); binomial and multinomial coefficients via scipy.special.comb, with a hand-rolled Pascal’s- triangle build kept only as a pedagogical illustration of the recurrence; integer partitions (the partition function via Euler’s pentagonal-number recurrence, and full enumeration) and Young/Ferrers diagrams; the inclusion-exclusion principle and the classic derangement- counting application; and Stirling numbers (first and second kind), Catalan numbers, and Bell numbers with their combinatorial interpretations; Fibonacci and Bernoulli numbers, power sums, and Gray codes; Latin squares; Prüfer codes for labeled trees; Ramsey’s R(3,3) and Erdős-Szekeres monotone subsequences; Hall’s marriage theorem; and Pólya necklace counting – all hand-rolled, with no scipy/numpy equivalent.

class mathematicskit.combinatorics.HallResult(satisfied, violating_subset=frozenset({}), matching=<factory>)

Bases: object

Container for a Hall’s-condition check on a bipartite graph.

Parameters:

• satisfied (bool)

• violating_subset (frozenset)

• matching (dict)

matching: dict

A maximum matching {left: right} found by augmenting paths.

Type:

dict

satisfied: bool

Whether every subset S of the left side has |N(S)| >= |S|.

Type:

bool

violating_subset: frozenset = frozenset({})

A left-side subset with too few neighbors, when the condition fails.

Type:

frozenset

class mathematicskit.combinatorics.YoungDiagram(parts=<factory>)

Bases: object

A Young diagram for an integer partition \(\lambda = (\lambda_1 \geq \lambda_2 \geq \dots)\).

Rows are left-justified, of non-increasing length – the standard combinatorial picture of a partition, e.g. \(\lambda=(4,2,1)\) of 7 is drawn as three rows of 4, 2, and 1 boxes. See Andrews & Eriksson, Integer Partitions, 2nd ed., Ch. 1.

Parameters:

parts (list) – Non-increasing positive integers summing to the partitioned number.

Examples

>>> diagram = YoungDiagram([4, 2, 1])
>>> print(diagram.ferrers_diagram())
****
**
*
>>> diagram.conjugate().parts
[3, 2, 1, 1]

conjugate()

The conjugate (transpose) partition: reflect the diagram across its main diagonal.

\(\lambda'_k\) = the number of parts of \(\lambda\) that are \(\geq k\).

Return type:

YoungDiagram

Returns:

YoungDiagram

ferrers_diagram(symbol='*')

Render the diagram as a multi-line string of symbol characters.

Parameters:

symbol (str)

Return type:

str

Returns:

str

property n: int

The partitioned integer, sum(parts).

Type:

int

parts: list

mathematicskit.combinatorics.are_orthogonal(a, b)

Whether two Latin squares are orthogonal: superimposed, every ordered pair of symbols appears exactly once.

Parameters:

• a (array_like, shape (n, n))

• b (array_like, shape (n, n))

Return type:

bool

Returns:

bool

Examples

>>> are_orthogonal(cyclic_latin_square(3, 1), cyclic_latin_square(3, 2))
True

mathematicskit.combinatorics.bell_number(n)

The n-th Bell number: the total number of ways to partition n labeled elements into any number of non-empty unlabeled blocks.

\(B_n = \sum_{k=0}^{n} \left\{{n \atop k}\right\}\), summing stirling_second_kind() over every possible number of blocks. See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 6.1, exercise 6.5.

Parameters:

n (int) – n >= 0.

Return type:

int

Returns:

int

Examples

>>> [bell_number(n) for n in range(6)]
[1, 1, 2, 5, 15, 52]

mathematicskit.combinatorics.bernoulli_numbers(n)

The Bernoulli numbers \(B_0, \dots, B_n\) as exact fractions, with \(B_1 = +\tfrac12\).

From the recurrence \(\sum_{j=0}^{m} \binom{m+1}{j} B_j = m+1\), which fixes the convention \(B_1 = +\tfrac12\) used by Jacob Bernoulli in Ars Conjectandi (1713).

Parameters:

n (int)

Return type:

list

Returns:

list of Fraction

Examples

>>> [str(b) for b in bernoulli_numbers(8)]
['1', '1/2', '1/6', '0', '-1/30', '0', '1/42', '0', '-1/30']

mathematicskit.combinatorics.catalan_number(n)

The n-th Catalan number, via its defining recurrence.

\(C_0 = 1\), \(C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}\) – counts, among many equivalent combinatorial objects: balanced strings of n pairs of parentheses, binary trees with n internal nodes, triangulations of a convex \((n+2)\)-gon, and monotonic lattice paths from \((0,0)\) to \((n,n)\) that never cross above the diagonal (Dyck paths). Equals the closed form \(\binom{2n}{n}/(n+1)\), cross-checked in this module’s tests. See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 7.5.

Parameters:

n (int) – n >= 0.

Return type:

int

Returns:

int

Examples

>>> [catalan_number(n) for n in range(6)]
[1, 1, 2, 5, 14, 42]

mathematicskit.combinatorics.combinations_count(n, k)

Number of ways to choose k of n distinct items, unordered: \(\binom{n}{k}\).

Via scipy.special.comb(). See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 5.1.

Parameters:

• n (int)

• k (int)

Return type:

int

Returns:

int

Examples

>>> combinations_count(5, 2)
10
>>> combinations_count(52, 5)  # 5-card poker hands
2598960

mathematicskit.combinatorics.count_bracelets(n, k)

Number of bracelets of n beads in k colors, up to rotation and reflection.

Parameters:

• n (int)

• k (int)

Return type:

int

Returns:

int

Examples

>>> [count_bracelets(n, 2) for n in range(1, 9)]
[2, 3, 4, 6, 8, 13, 18, 30]

mathematicskit.combinatorics.count_labeled_trees(n)

Cayley’s formula: \(n^{n-2}\) labeled trees on n vertices.

Parameters:

n (int) – n >= 1.

Return type:

int

Returns:

int

Examples

>>> [count_labeled_trees(n) for n in range(1, 7)]
[1, 1, 3, 16, 125, 1296]

mathematicskit.combinatorics.count_necklaces(n, k)

Number of necklaces of n beads in k colors, up to rotation.

Parameters:

• n (int) – Number of beads, n >= 1.

• k (int) – Number of colors.

Return type:

int

Returns:

int

Examples

>>> [count_necklaces(n, 2) for n in range(1, 9)]
[2, 3, 4, 6, 8, 14, 20, 36]

mathematicskit.combinatorics.count_triangle_free_colorings(n)

The number of red/blue edge colorings of \(K_n\) with no monochromatic triangle.

Exhaustive over all \(2^{\binom{n}{2}}\) colorings, so feasible only for \(n \le 6\). It is zero for \(n = 6\), which proves \(R(3,3) \le 6\): among any six people, three are mutual friends or three are mutual strangers.

Parameters:

n (int) – n <= 6.

Return type:

int

Returns:

int

Examples

>>> count_triangle_free_colorings(5), count_triangle_free_colorings(6)
(12, 0)

mathematicskit.combinatorics.cyclic_latin_square(n, multiplier=1)

The Latin square \(L_{ij} = (a\,i + j) \bmod n\) for a multiplier \(a\) coprime to n.

Parameters:

• n (int)

• multiplier (int) – The coefficient \(a\); it must be coprime to n for every column to be a permutation.

Return type:

ndarray

Returns:

ndarray, shape (n, n), int

Examples

>>> cyclic_latin_square(3)
array([[0, 1, 2],
       [1, 2, 0],
       [2, 0, 1]])

mathematicskit.combinatorics.derangement_count(n)

Number of derangements \(D_n\): permutations of n items with no fixed points.

The classic inclusion-exclusion application (the “hat-check problem”): starting from all \(n!\) permutations, subtract those fixing each point, add back those fixing each pair (double- subtracted), etc., giving \(D_n = n!\sum_{k=0}^n \dfrac{(-1)^k}{k!}\). See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 8.3, and Cormen et al., Introduction to Algorithms, 3rd ed., Ch. C.4.

Parameters:

n (int) – n >= 0.

Return type:

int

Returns:

int

Examples

>>> derangement_count(0)
1
>>> derangement_count(1)
0
>>> derangement_count(4)
9
>>> import itertools
>>> brute_force = sum(1 for p in itertools.permutations(range(4)) if all(p[i] != i for i in range(4)))
>>> derangement_count(4) == brute_force
True

mathematicskit.combinatorics.domino_tilings(n)

Number of ways to tile a \(2 \times n\) strip with \(1 \times 2\) dominoes, \(F_{n+1}\).

Equivalently, the number of ways to write \(n\) as an ordered sum of 1s and 2s – the counting problem behind the Sanskrit prosodists’ study of long and short syllables, centuries before Fibonacci.

Parameters:

n (int)

Return type:

int

Returns:

int

Examples

>>> domino_tilings(4)  # 1111, 112, 121, 211, 22
5

mathematicskit.combinatorics.fibonacci(n)

The Fibonacci number \(F_n\), with \(F_0 = 0\), \(F_1 = 1\), \(F_{n} = F_{n-1} + F_{n-2}\).

Parameters:

n (int) – n >= 0.

Return type:

int

Returns:

int

Examples

>>> [fibonacci(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

mathematicskit.combinatorics.generate_combinations(items, r)

Generate every r-combination of items, in lexicographic order.

Thin wrapper around itertools.combinations().

Parameters:

• items (sequence)

• r (int)

Return type:

list

Returns:

list of tuple

Examples

>>> generate_combinations([1, 2, 3, 4], r=2)
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

mathematicskit.combinatorics.generate_permutations(items, r=None)

Generate every r-permutation of items, in lexicographic order of position.

Thin wrapper around itertools.permutations() (which scipy.special.perm doesn’t provide – it only counts).

Parameters:

• items (sequence)

• r (int | None) – Defaults to len(items) (full permutations).

Return type:

list

Returns:

list of tuple

Examples

>>> generate_permutations([1, 2, 3], r=2)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

mathematicskit.combinatorics.gray_code(n)

The reflected binary Gray code on n bits, as integers \(g_k = k \oplus (k \gg 1)\).

Consecutive codes differ in exactly one bit, including the wrap from the last code back to the first. Frank Gray’s 1953 patent used the code in analog-to-digital converters. See Knuth, The Art of Computer Programming, Vol. 4A, Sec. 7.2.1.1.

Parameters:

n (int)

Return type:

list

Returns:

list of int

Examples

>>> [format(g, "03b") for g in gray_code(3)]
['000', '001', '011', '010', '110', '111', '101', '100']

mathematicskit.combinatorics.hall_condition(adjacency)

Check Hall’s condition \(|N(S)| \ge |S|\) for every subset \(S\) of the left side.

Checks all \(2^n\) subsets, so it is meant for small illustrations. Hall’s theorem says the condition holds exactly when maximum_matching() covers every left vertex; this function returns both, so the two can be compared.

Parameters:

adjacency (dict) – {left_vertex: iterable of right vertices}.

Return type:

HallResult

Returns:

HallResult

Examples

>>> hall_condition({"a": [1], "b": [1], "c": [2]}).violating_subset == frozenset({"a", "b"})
True

mathematicskit.combinatorics.has_monochromatic_triangle(n, coloring)

Whether a 2-coloring of the edges of \(K_n\) contains a triangle with all three edges the same color.

Parameters:

• n (int)

• coloring (dict) – {(i, j): color} for every pair i < j.

Return type:

bool

Returns:

bool

Examples

>>> pentagon = {(i, j): int((j - i) % 5 in (1, 4)) for i, j in combinations(range(5), 2)}
>>> has_monochromatic_triangle(5, pentagon)  # K_5 can avoid them: R(3,3) > 5
False

mathematicskit.combinatorics.integer_partitions(n)

Enumerate every integer partition of n, each as a non-increasing list of parts.

Generated recursively: every partition of n with largest part \(\leq m\) either has largest part exactly m (prepend m to a partition of n-m with parts \(\leq m\)) or largest part \(< m\) (a partition of n with parts \(\leq m-1\)). See Andrews & Eriksson, Integer Partitions, 2nd ed., Ch. 1.

Parameters:

n (int) – n >= 0.

Return type:

list

Returns:

list of list of int – In descending-largest-part order; len(...) == partition_function(n).

Examples

>>> integer_partitions(4)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
>>> len(integer_partitions(10)) == partition_function(10)
True

mathematicskit.combinatorics.is_latin_square(square)

Whether every row and every column of an \(n \times n\) array is a permutation of 0..n-1.

Parameters:

square (array_like, shape (n, n))

Return type:

bool

Returns:

bool

Examples

>>> is_latin_square([[0, 1], [1, 0]]), is_latin_square([[0, 1], [0, 1]])
(True, False)

mathematicskit.combinatorics.longest_decreasing_subsequence(sequence)

A longest strictly decreasing subsequence; see longest_increasing_subsequence().

Parameters:

sequence (sequence of numbers)

Return type:

list

Returns:

list

Examples

>>> longest_decreasing_subsequence([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
[9, 6, 5, 3]

mathematicskit.combinatorics.longest_increasing_subsequence(sequence)

A longest strictly increasing subsequence, by patience sorting in \(O(n \log n)\).

The Erdős-Szekeres theorem guarantees that any sequence of \((r-1)(s-1)+1\) distinct numbers has an increasing subsequence of length \(r\) or a decreasing one of length \(s\).

Parameters:

sequence (sequence of comparable values)

Return type:

list

Returns:

list

Examples

>>> longest_increasing_subsequence([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
[1, 2, 3, 5]

mathematicskit.combinatorics.maximum_matching(adjacency)

A maximum matching of a bipartite graph, by repeated augmenting-path search.

Parameters:

adjacency (dict) – {left_vertex: iterable of right vertices}.

Return type:

dict

Returns:

dict – {left: right} for every matched left vertex.

Examples

>>> sorted(maximum_matching({"a": [1, 2], "b": [1], "c": [2, 3]}).items())
[('a', 2), ('b', 1), ('c', 3)]

mathematicskit.combinatorics.multinomial_coefficient(n, ks)

Multinomial coefficient \(\dbinom{n}{k_1,\dots,k_m} = \dfrac{n!}{k_1!\cdots k_m!}\), sum(ks) = n.

Computed as a product of ordinary binomial coefficients (each via scipy.special.comb()): choose \(k_1\) of n, then \(k_2\) of the remaining \(n-k_1\), and so on – equivalent to the factorial-ratio definition but built entirely from library calls. See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 5.5.

Parameters:

• n (int)

• ks (sequence of int) – Must sum to n.

Return type:

int

Returns:

int

Examples

>>> multinomial_coefficient(10, [2, 3, 5])
2520

mathematicskit.combinatorics.orthogonal_latin_square_pair(n)

A pair of orthogonal Latin squares of odd order n: \(L_{ij} = i + j\) and \(M_{ij} = 2i + j \pmod n\).

Euler conjectured in 1782 that no pair exists when \(n \equiv 2 \pmod 4\). Gaston Tarry confirmed it for \(n = 6\) in 1900, but R. C. Bose, S. S. Shrikhande, and E. T. Parker disproved the conjecture for every other such \(n > 6\) in 1959-1960. This construction covers odd \(n\), where 2 is invertible modulo \(n\).

Parameters:

n (int) – Odd, n >= 3.

Returns:

tuple of ndarray

Examples

>>> a, b = orthogonal_latin_square_pair(5)
>>> are_orthogonal(a, b)
True

mathematicskit.combinatorics.partition_function(n)

The partition function \(p(n)\): the number of ways to write n as a sum of positive integers (order irrelevant).

Computed via Euler’s pentagonal number theorem recurrence,

\[p(n) = \sum_{k \geq 1} (-1)^{k+1}\left[p\!\left(n - \tfrac{k(3k-1)}{2}\right) + p\!\left(n - \tfrac{k(3k+1)}{2}\right)\right]\]

which is far faster than enumerating every partition (see integer_partitions()) just to count them. See Hardy & Wright, An Introduction to the Theory of Numbers, 6th ed., Sec. 19.10-19.11.

Parameters:

n (int) – n >= 0.

Return type:

int

Returns:

int

Examples

>>> partition_function(0)
1
>>> partition_function(5)
7
>>> partition_function(10)
42

mathematicskit.combinatorics.pascals_triangle(n_rows)

Build the first n_rows rows of Pascal’s triangle via the addition recurrence.

Row n (0-indexed) holds \(\binom{n}{0}, \dots, \binom{n}{n}\), each computed as the sum of the two entries above it in the previous row (with implicit zeros outside the triangle) – never calling combinations_count() at all. See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 5.1.

Parameters:

n_rows (int)

Return type:

list

Returns:

list of list of int

Examples

>>> pascals_triangle(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

mathematicskit.combinatorics.permutations_count(n, k=None)

Number of ways to arrange k of n distinct items in order: \(P(n,k) = n!/(n-k)!\).

Via scipy.special.perm(). k=None (the default) counts full permutations, \(P(n,n) = n!\). See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 5.1.

Parameters:

• n (int)

• k (int | None)

Return type:

int

Returns:

int

Examples

>>> permutations_count(5, 2)  # 5*4
20
>>> permutations_count(5)  # 5!
120

mathematicskit.combinatorics.prufer_decode(sequence)

The labeled tree with the given Prüfer sequence, as a sorted edge list.

Inverts prufer_encode(): a sequence of length \(n - 2\) over 0..n-1 determines a unique tree on n vertices.

Parameters:

sequence (sequence of int)

Return type:

list

Returns:

list of tuple

Examples

>>> prufer_decode([3, 3, 3])
[(0, 3), (1, 3), (2, 3), (3, 4)]

mathematicskit.combinatorics.prufer_encode(edges, n)

The Prüfer sequence of a labeled tree on vertices 0..n-1.

Repeatedly removes the smallest-labeled leaf and records its neighbor, until two vertices remain. The result has length \(n - 2\).

Parameters:

• edges (iterable of (int, int)) – The tree’s \(n - 1\) edges.

• n (int) – Number of vertices, n >= 2.

Return type:

list

Returns:

list of int

Examples

>>> prufer_encode([(0, 3), (1, 3), (2, 3), (3, 4)], 5)  # a star around 3, plus 4
[3, 3, 3]

mathematicskit.combinatorics.stirling_first_kind(n, k, signed=False)

Stirling numbers of the first kind: permutations of n elements with exactly k cycles.

Unsigned, \(\left[{n \atop k}\right]\), via the recurrence \(\left[{n \atop k}\right] = (n-1)\left[{n-1 \atop k}\right] + \left[{n-1 \atop k-1}\right]\) (inserting element n either into an existing cycle in \((n-1)\) ways, or as its own new cycle). signed=True returns the signed version \(s(n,k) = (-1)^{n-k}\left[{n \atop k}\right]\) (the coefficients of \(x(x-1)\cdots(x-n+1)\) in powers of x). See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 6.1.

Parameters:

• n (int) – n, k >= 0.

• k (int) – n, k >= 0.

• signed (bool)

Return type:

int

Returns:

int

Examples

>>> stirling_first_kind(4, 2)  # permutations of 4 elements with exactly 2 cycles
11
>>> sum(stirling_first_kind(4, k) for k in range(5)) == 24  # sum over k = n!
True

mathematicskit.combinatorics.stirling_second_kind(n, k)

Stirling numbers of the second kind: ways to partition n labeled elements into exactly k non-empty unlabeled blocks.

\(\left\{{n \atop k}\right\}\), via the recurrence \(\left\{{n \atop k}\right\} = k\left\{{n-1 \atop k}\right\} + \left\{{n-1 \atop k-1}\right\}\) (element n joins one of the k existing blocks, or starts a new one). See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 6.1.

Parameters:

• n (int) – n, k >= 0.

• k (int) – n, k >= 0.

Return type:

int

Returns:

int

Examples

>>> stirling_second_kind(4, 2)  # ways to split 4 labeled items into 2 non-empty groups
7
>>> stirling_second_kind(5, 1)  # only one way: everything in one block
1
>>> stirling_second_kind(5, 5)  # only one way: every element its own block
1

mathematicskit.combinatorics.sum_of_powers(n, p)

The power sum \(1^p + 2^p + \cdots + n^p\), by Faulhaber’s formula.

Jacob Bernoulli’s formula expresses the sum as a polynomial in \(n\) whose coefficients involve the Bernoulli numbers:

\[\sum_{k=1}^{n} k^p = \frac{1}{p+1} \sum_{j=0}^{p} \binom{p+1}{j} B_j\, n^{p+1-j}.\]

Parameters:

• n (int)

• p (int) – p >= 0.

Return type:

int

Returns:

int

Examples

>>> sum_of_powers(1000, 10)  # Bernoulli's own boast: computed "in half of a quarter of an hour"
91409924241424243424241924242500

mathematicskit.combinatorics.union_size_inclusion_exclusion(sets)

Exact size of the union of several (possibly overlapping) sets.

\(\left|\bigcup_i A_i\right| = \sum_i |A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \dots\), summed over every nonempty subset of the given sets, alternating sign by subset size. See Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., Sec. 8.3, eq. (8.63).

Parameters:

sets (Sequence[set])

Return type:

int

Returns:

int

Examples

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> c = {4, 5, 6, 7}
>>> union_size_inclusion_exclusion([a, b, c]) == len(a | b | c)
True