← ClaudeAtlas

combinatorics-generating-functionslisted

Counting and enumeration: twelvefold way, bijective and double-counting proofs, inclusion-exclusion and Mobius inversion, OGF/EGF and the symbolic method, recurrences to closed forms, Lagrange inversion, transfer matrices, Burnside/Polya, and coefficient asymptotics by singularity analysis, cross-checked by brute force and OEIS. Load when counting objects, solving or guessing a recurrence, or proving an enumeration identity.
rustcircle/c101 · ★ 0 · Code & Development · score 65
Install: claude install-skill rustcircle/c101
# Combinatorics and generating functions A count is finished when it has four things: a formula or generating function (GF), a proof (bijection, specification or algebra), an exact brute-force match for small n, and the OEIS A-number with the offset checked. Use the hub's status labels: a brute-force match alone is "Verified for n ≤ N", never "Proved". ## 1. Twelvefold way n balls into k boxes, i.e. functions from an n-set to a k-set. | Balls | Boxes | any | injective (≤ 1 per box) | surjective (≥ 1 per box) | |---|---|---|---|---| | labelled | labelled | kⁿ | k(k−1)···(k−n+1) | k! S(n,k) | | unlabelled | labelled | C(n+k−1, n) | C(k, n) | C(n−1, k−1) | | labelled | unlabelled | Σ_{j≤k} S(n,j) | 1 if n ≤ k else 0 | S(n,k) | | unlabelled | unlabelled | p_{≤k}(n), partitions into at most k parts | 1 if n ≤ k else 0 | p_k(n) = p_{≤k}(n−k) | S(n,k) (Stirling, second kind) satisfies S(n,k) = k S(n−1,k) + S(n−1,k−1), and Σ_k S(n,k) = B_n (Bell). Row 2 also counts compositions: C(n−1, k−1) into k positive parts, C(n+k−1, k−1) into k nonnegative parts. Check the corners n = 0 and k = 0 by brute force; conventions differ there. ```python from sympy import binomial, ff, factorial from sympy.functions.combinatorial.numbers import stirling, nT from sympy.utilities.iterables import partitions n, k = 7, 3 k**n, ff(k, n), factorial(k) * stirling(n, k) # labelled into labelled binomial(n + k - 1, n), binomial(k, n), binomial(n - 1, k - 1) sum(stirling(n, j) for j in range(k