combinatorics-generating-functionslisted
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