v. Stirling, Bell and Partition Numbers

The number families behind set partitions, cycle structures and integer partitions: Stirling numbers of both kinds, Bell, Lah, Fubini, Eulerian, Motzkin, Schröder, Delannoy, partition numbers (all, bounded, distinct parts) and the $q$-binomial. Tables are templates over T (a mint from Modular Arithmetic or an exact integer type: ll overflows quickly, $p(400)\approx 6.9\cdot 10^{18}$, $B_{25}\approx 4.6\cdot 10^{18}$); functions that divide need a prime modulus. Catalan, Narayana and lattice paths are in Catalan and Lattice Paths, derangements in Inclusion–Exclusion.

Number	Counts	Recurrence / formula	Start
$c(n,k)=\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ (unsigned first kind)	permutations of $[n]$ with $k$ cycles	$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$; ${\sum }_{k}c(n,k)x^k=x(x+1)\cdots (x+n-1)$	row 4: 6, 11, 6, 1
$S(n,k)=\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ (second kind)	partitions of $[n]$ into $k$ non-empty blocks	$S(n,k)=S(n-1,k-1)+kS(n-1,k)$; $S(n,k)=\frac{1}{k!}{\sum }_j(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})j^n$	row 4: 1, 7, 6, 1
Bell $B_n$	all set partitions of $[n]$	$B_{n+1}={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k$; $B_n={\sum }_{k}S(n,k)$; EGF $e^{e^x-1}$	1, 1, 2, 5, 15, 52, 203, 877, 4140
Lah $L(n,k)$	partitions of $[n]$ into $k$ non-empty ordered lists	$\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)\frac{n!}{k!}$	row 3: 6, 6, 1
Fubini $F_n$	ordered set partitions (weak orders, race rankings with ties)	${\sum }_{k}k!S(n,k)$; $F_n={\sum }_{j\ge 1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)F_{n-j}$	1, 1, 3, 13, 75, 541
Eulerian $A(n,k)$	permutations with $k$ ascents	$(k+1)A(n-1,k)+(n-k)A(n-1,k-1)$	row 4: 1, 11, 11, 1
Motzkin $M_n$	paths U/D/F staying $\ge 0$; non-crossing chords (not all points used)	$(n+2)M_n=(2n+1)M_{n-1}+(3n-3)M_{n-2}$	1, 1, 2, 4, 9, 21, 51, 127
large Schröder $S_n$	paths E/N/NE under the diagonal; separable permutations ($n+1$)	$S_n=3S_{n-1}+{\sum }_{k=1}^{n-2}{S}_k{S}_{n-1-k}$	1, 2, 6, 22, 90, 394
Delannoy $D(a,b)$	paths E/N/NE, unrestricted	$D(a,b)=D(a-1,b)+D(a,b-1)+D(a-1,b-1)$	$D(n,n)$: 1, 3, 13, 63
$p(n)$	integer partitions	Euler’s pentagonal recurrence; ${\prod }_k\frac{1}{1-x^k}$	1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42
$p(n,k)$	partitions into exactly $k$ parts (= largest part $k$)	$p(n,k)=p(n-1,k-1)+p(n-k,k)$
$q(n)$	partitions into distinct parts (= into odd parts)	${\prod }_k(1+x^k)$	1, 1, 1, 2, 2, 3, 4, 5, 6, 8

Identity	Use
${\sum }_{k}c(n,k)=n!$, ${\sum }_{k}S(n,k)=B_n$	row sums
$x^n={\sum }_{k}S(n,k)x^{\underline{k}}$; $x^{\overline{n}}={\sum }_{k}c(n,k)x^k$; $x^{\underline{n}}={\sum }_k(-1{)}^{n-k}c(n,k)x^k$	change of basis between powers and falling factorials: sums of $i^n$, moments of random variables
surjections $[n]\to [k]$: $k!S(n,k)$	the twelvefold way (Counting Fundamentals)
${\sum }_{k}A(n,k)=n!$; Worpitzky $x^n={\sum }_{k}A(n,k)\left(\genfrac{}{}{0ex}{}{x+k}{n}\right)$
conjugation: partitions with at most $k$ parts = partitions with all parts $\le k$	Ferrers diagram transpose
$p(n)\sim \frac{1}{4n\sqrt{3}}{e}^{\pi \sqrt{2n/3}}$ (Hardy–Ramanujan)	$p(100)=190569292$, $p(10^4)$ has 107 digits
a whole row $S(n,\cdot )$ or $c(n,\cdot )$, $B_0..B_n$, $p(\mathrm{0..}n)$ in $O(n\log n)$	NTT: convolution, Taylor shift, $\exp$, inverse of the pentagonal series (Counting with Power Series)

template <class T> vector<vector<T>> stirling1Table(int n) {          // c[i][j], unsigned
    vector<vector<T>> s(n + 1, vector<T>(n + 1, T(0))); s[0][0] = T(1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) s[i][j] = s[i - 1][j - 1] + T(i - 1) * s[i - 1][j];
    return s;
}
template <class T> vector<vector<T>> stirling2Table(int n) {          // S[i][j]
    vector<vector<T>> s(n + 1, vector<T>(n + 1, T(0))); s[0][0] = T(1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) s[i][j] = s[i - 1][j - 1] + T(j) * s[i - 1][j];
    return s;
}
mint stirling2(ll n, int k, const Comb& cb) {                        // one S(n, k), huge n, O(k log n); cb covers k
    if (k < 0 || k > n) return 0;
    mint res = 0;
    for (int j = 0; j <= k; j++) { mint t = mint(j).pow(n) * cb.fi[j] * cb.fi[k - j]; res += (k - j) % 2 ? -t : t; }
    return res;
}
template <class T> vector<T> bellNumbers(int n) {                     // Bell triangle, O(n^2)
    vector<T> bell(n + 1), row = {T(1)}; bell[0] = T(1);
    for (int i = 1; i <= n; i++) {
        vector<T> next = {row.back()};
        for (const T& x : row) next.push_back(next.back() + x);
        row = move(next); bell[i] = row[0];
    }
    return bell;
}
template <class T> vector<T> partitionNumbers(int n) {                // p(0..n), pentagonal recurrence, O(n sqrt n)
    vector<T> p(n + 1, T(0)); p[0] = T(1);
    for (int i = 1; i <= n; i++)
        for (int k = 1;; k++) {
            ll g1 = (ll)k * (3 * k - 1) / 2, g2 = (ll)k * (3 * k + 1) / 2;
            if (g1 > i) break;
            T s = p[i - g1]; if (g2 <= i) s += p[i - g2];
            if (k % 2) p[i] += s; else p[i] -= s;
        }
    return p;
}
template <class T> vector<T> partitionsMaxPart(int n, int k) {        // partitions of 0..n with all parts <= k (coin-change DP), O(nk)
    vector<T> p(n + 1, T(0)); p[0] = T(1);
    for (int part = 1; part <= k; part++) for (int i = part; i <= n; i++) p[i] += p[i - part];
    return p;
}
template <class T> vector<vector<T>> partitionsIntoParts(int n, int k) {   // P[i][j]: i into exactly j parts
    vector<vector<T>> p(n + 1, vector<T>(k + 1, T(0))); p[0][0] = T(1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= min(i, k); j++) p[i][j] = p[i - 1][j - 1] + p[i - j][j];
    return p;
}
template <class T> vector<T> distinctPartitions(int n) {              // q(0..n), O(n sqrt n)
    vector<T> q(n + 1, T(0)), cur(n + 1, T(0)); q[0] = cur[0] = T(1);  // cur[i]: i into exactly j distinct parts
    for (int j = 1; j * (j + 1) / 2 <= n; j++) {
        vector<T> nxt(n + 1, T(0));
        for (int i = j; i <= n; i++) nxt[i] = nxt[i - j] + cur[i - j];
        cur = nxt;
        for (int i = 0; i <= n; i++) q[i] += cur[i];
    }
    return q;
}

Proof: Stirling, Bell and partition recurrences

First kind. Element $n$ is a fixed point (a new cycle: $c(n-1,k-1)$) or is inserted after one of the $n-1$ other elements in its cycle ($(n-1)c(n-1,k)$). The rising factorial $x^{\overline{n}}=x^{\overline{n-1}}(x+n-1)$ satisfies the same recurrence coefficientwise, and $x^{\underline{n}}=(-1{)}^n(-x{)}^{\overline{n}}$ gives the signed version. Second kind. Element $n$ is a singleton block or joins one of $k$ blocks. The closed form is inclusion–exclusion for surjections onto $k$ labelled boxes divided by $k!$ (blocks are unlabelled and non-empty, so each partition corresponds to exactly $k!$ surjections). Power basis: both sides of $x^n={\sum }_{k}S(n,k)x^{\underline{k}}$ count functions $[n]\to [x]$ for every positive integer $x$ (group by the partition of $[n]$ into fibres; the $k$ fibres get distinct values in $x^{\underline{k}}$ ways); polynomials agreeing at infinitely many points are equal. Row sums: permutations by cycle count, set partitions by block count.

Bell. In a partition of $[n+1]$, the block of $n+1$ contains $n-k$ other elements; the remaining $k$ are partitioned arbitrarily: $B_{n+1}={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)B_k={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k$. Bell triangle: with $a_{i,0}=a_{i-1,i-1}$ and $a_{i,j}=a_{i,j-1}+a_{i-1,j-1}$, induction on $i$ gives $a_{i,j}={\sum }_t\left(\genfrac{}{}{0ex}{}{j}{t}\right)B_{i-j+t}$: the recurrence becomes Pascal’s rule $\left(\genfrac{}{}{0ex}{}{j}{t}\right)=\left(\genfrac{}{}{0ex}{}{j-1}{t-1}\right)+\left(\genfrac{}{}{0ex}{}{j-1}{t}\right)$ after shifting $t$ by one in the first term. Hence $a_{i,0}=B_i$ and $a_{i,i}={\sum }_t\left(\genfrac{}{}{0ex}{}{i}{t}\right)B_t=B_{i+1}$, which is the first entry of the next row. EGF: a set partition is a set of non-empty blocks, so its EGF is $\exp (e^x-1)$.

Partitions. Pentagonal number theorem: ${\prod }_{k\ge 1}(1-x^k)={\sum }_{j\in \mathbb{Z}}(-1{)}^j{x}^{j(3j-1)/2}$. Franklin’s involution: in a partition into distinct parts, let $s$ be the smallest part and $\ell$ the length of the run of consecutive parts starting at the largest; move the smallest part onto the top run (one cell to each of the $s$ largest parts) if $s\le \ell$, else move the run’s last column into a new smallest part. This changes the number of parts by $\pm 1$, so it pairs partitions with opposite signs, and it is undefined exactly for the pentagonal shapes $j(3j\pm 1)/2$, which carry sign $(-1{)}^j$. Multiplying ${\sum }_{n}p(n)x^n$ by this series gives 1, which is the recurrence in partitionNumbers. Bounded parts: the coin DP adds parts of size part in nondecreasing order of size, so each multiset of parts is counted once. Exactly $k$ parts: either a part equals 1 (remove it) or all parts are $\ge 2$ (subtract 1 from each). Distinct parts: subtract 1 from each of the $j$ parts; a part 1 disappears ($j-1$ parts remain) or not. Euler: $\prod (1+x^k)=\prod \frac{1-x^{2k}}{1-x^k}={\prod }_{k\text{ odd}}\frac{1}{1-x^k}$. Conjugation: transposing the Ferrers diagram swaps the number of parts and the largest part. The asymptotic is Hardy–Ramanujan’s theorem (circle method), quoted. All tables were checked against brute-force enumeration (permutations, set partitions via restricted growth strings, integer partitions) for $n\le 9$.

More families

template <class T> vector<vector<T>> eulerianTable(int n) {           // E[i][k]: permutations of i with k ascents
    vector<vector<T>> e(n + 1, vector<T>(n + 1, T(0))); e[0][0] = T(1);
    for (int i = 1; i <= n; i++) for (int k = 0; k < i; k++) e[i][k] = T(k + 1) * e[i - 1][k] + (k ? T(i - k) * e[i - 1][k - 1] : T(0));
    return e;
}
template <class T> vector<T> motzkin(int n) {                         // prime modulus (division)
    vector<T> m(n + 1, T(1));
    for (int i = 2; i <= n; i++) m[i] = (T(2 * i + 1) * m[i - 1] + T(3 * i - 3) * m[i - 2]) / T(i + 2);
    return m;
}
template <class T> vector<T> schroder(int n) {                        // large Schroder, O(n^2)
    vector<T> s(n + 1, T(0)); s[0] = T(1); if (n >= 1) s[1] = T(2);
    for (int i = 2; i <= n; i++) { s[i] = T(3) * s[i - 1]; for (int k = 1; k <= i - 2; k++) s[i] += s[k] * s[i - 1 - k]; }
    return s;
}
template <class T> vector<vector<T>> delannoyTable(int n, int m) {
    vector<vector<T>> d(n + 1, vector<T>(m + 1, T(1)));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) d[i][j] = d[i - 1][j] + d[i][j - 1] + d[i - 1][j - 1];
    return d;
}
template <class T> vector<vector<T>> lahTable(int n) {                // L(i, k) = L(i-1, k-1) + (i - 1 + k) L(i-1, k)
    vector<vector<T>> l(n + 1, vector<T>(n + 1, T(0))); l[0][0] = T(1);
    for (int i = 1; i <= n; i++) for (int k = 1; k <= i; k++) l[i][k] = l[i - 1][k - 1] + T(i - 1 + k) * l[i - 1][k];
    return l;
}
template <class T> vector<T> fubini(int n) {                          // F(i) = sum_{j>=1} C(i, j) F(i - j)
    vector<vector<T>> c(n + 1, vector<T>(n + 1, T(0)));
    for (int i = 0; i <= n; i++) { c[i][0] = T(1); for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; }
    vector<T> f(n + 1, T(0)); f[0] = T(1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) f[i] += c[i][j] * f[i - j];
    return f;
}

Proof: Eulerian, Lah, Fubini, Motzkin, Schröder, Delannoy

Eulerian. Insert $n$ into a permutation of $[n-1]$ with $j$ ascents. At the front, or inside an ascent $a<b$ (giving $a<n>b$), the ascent count is unchanged: $j+1$ slots. At the end, or inside a descent $a>b$, it grows by one: $n-1-j$ slots. Hence $A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)$. Worpitzky: count words $w\in [x{]}^n$ for a positive integer $x$. Sort the positions stably by value; the resulting permutation $\sigma$ has $w({\sigma }_1)\le \cdots \le w({\sigma }_n)$, with strict inequality at every descent ${\sigma }_i>{\sigma }_{i+1}$ (equal values keep positions in increasing order). Conversely each $\sigma$ and each such value sequence give exactly one word. With $d$ forced strict steps, subtracting from each value the number of forced steps before it leaves a weakly increasing sequence in $[1,x-d]$: $\left(\genfrac{}{}{0ex}{}{x-d+n-1}{n}\right)$ choices. Since $d=n-1-\mathrm{asc}(\sigma )$, $x^n={\sum }_{k}A(n,k)\left(\genfrac{}{}{0ex}{}{x+k}{n}\right)$ for all positive integers $x$, hence as polynomials.

Lah. Write the $n$ elements in a row ($n!$), cut into $k$ non-empty consecutive lists ($\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ cut positions), and forget the order of the lists ($k!$, they are distinct). Recurrence: element $n$ forms its own list, or is inserted into one of the $k$ lists at one of $(n-1)+k$ positions (before each of the $n-1$ elements or at the end of a list). Fubini. An ordered set partition is an ordered sequence of $k$ blocks ($k!S(n,k)$), or: choose the first block ($\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, $j\ge 1$) and order the rest.

Motzkin. A path starts with F (then any path of length $n-1$) or with U, a path of length $k$, D, and the rest: $M_n=M_{n-1}+{\sum }_k{M}_k{M}_{n-2-k}$, i.e. $x^2{M}^2+(x-1)M+1=0$. Put $u=2x^{2}M=1-x-\sqrt{\Delta }$ with $\Delta =1-2x-3x^2$. Then $u^{\prime }=-1+\frac{1+3x}{\sqrt{\Delta }}$, so $\Delta u^{\prime }=-\Delta +(1+3x)(1-x-u)=4x-(1+3x)u$. With $u_m=2M_{m-2}$, the coefficient of $x^{m-1}$ for $m\ge 3$ reads $m{u}_m-2(m-1)u_{m-1}-3(m-2)u_{m-2}+u_{m-1}+3u_{m-2}=0$, i.e. $(n+2)M_n=(2n+1)M_{n-1}+(3n-3)M_{n-2}$ for $n=m-2$. Schröder. Draw the paths as U, D and double-length flat steps F staying $\ge 0$: a path is F followed by a path ($S_{n-1}$) or U $A$ D $B$ (${\sum }_{k=0}^{n-1}{S}_k{S}_{n-1-k}$); separating the terms $k=0$ and $k=n-1$ gives $3S_{n-1}+{\sum }_{k=1}^{n-2}{S}_k{S}_{n-1-k}$. Delannoy: classify by the last step. All tables were checked against brute force (ascent counts over permutations, list partitions, ordered partitions, and enumerated paths).

q-binomials

${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q={\prod }_{i=0}^{k-1}\frac{1-q^{n-i}}{1-q^{i+1}}$ counts $k$-dimensional subspaces of ${\mathbb{F}}_q^n$ ($q$ a prime power); as a polynomial in $q$ it is ${\sum }_w{q}^{\mathrm{inv}(w)}$ over binary words with $k$ ones and $n-k$ zeros, i.e. the generating function of partitions inside a $k\times (n-k)$ box by size, and of inversions of multiset permutations. At $q=1$ it is the ordinary binomial.

template <class Z> struct QBinomial {                                 // [n k]_q mod a prime, O(maxN) build, O(1) query (q-Lucas)
    Z q; int d; vector<Z> qfact, qinv;                               // d: multiplicative order of q (or maxN + 1)
    QBinomial(Z qq, int maxN) : q(qq), d(maxN + 1) {
        Z cur = 1;
        for (int i = 1; i <= maxN; i++) { cur *= q; if (cur == Z(1)) { d = i; break; } }
        int m = min(d - 1, maxN); qfact.assign(m + 1, Z(1)); Z qi = 1;
        for (int i = 1; i <= m; i++) qi *= q, qfact[i] = qfact[i - 1] * (Z(1) - qi);
        qinv.resize(m + 1); for (int i = 0; i <= m; i++) qinv[i] = Z(1) / qfact[i];
    }
    Z reduced(int n, int k) const { return k < 0 || k > n ? Z(0) : qfact[n] * qinv[k] * qinv[n - k]; }   // n < d
    Z binom(ll a, ll b) const { if (b < 0 || b > a) return Z(0); Z r = 1; for (ll i = 0; i < b; i++) r = r * Z(a - i) / Z(i + 1); return r; }
    Z C(int n, int k) const {
        if (k < 0 || k > n) return Z(0);
        if (n < d) return reduced(n, k);
        return binom(n / d, k / d) * reduced(n % d, k % d);
    }
};
template <class Z> vector<vector<Z>> qBinomialTable(int n, Z q) {     // [i j] = [i-1 j-1] + q^j [i-1 j], O(n^2), any ring
    vector<vector<Z>> t(n + 1, vector<Z>(n + 1, Z(0))); vector<Z> qp(n + 1, Z(1));
    for (int i = 1; i <= n; i++) qp[i] = qp[i - 1] * q;
    for (int i = 0; i <= n; i++) { t[i][0] = Z(1); for (int j = 1; j <= i; j++) t[i][j] = t[i - 1][j - 1] + qp[j] * t[i - 1][j]; }
    return t;
}

Proof: q-binomial recurrence, product formula, subspaces and q-Lucas

Recurrence. Let ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q={\sum }_w{q}^{\mathrm{inv}(w)}$ over words with $k$ ones and $n-k$ zeros, an inversion being a 1 before a 0. If the last letter is 1 it is in no inversion (${\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}_q$); if it is 0 it forms an inversion with each of the $k$ ones ($q^k{\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)}_q$). Product formula: both sides satisfy this recurrence with the same boundary values; for the product, ${\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}_q+q^k{\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)}_q={\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}_q(1+q^k\frac{1-q^{n-k}}{1-q^k})={\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}_q\frac{1-q^n}{1-q^k}$. Subspaces: ordered bases of a $k$-dimensional subspace of ${\mathbb{F}}_q^n$ number $(q^n-1)(q^n-q)\cdots (q^n-q^{k-1})$ in total, and each subspace has $(q^k-1)\cdots (q^k-q^{k-1})$ of them; the quotient is the product formula. Box partitions: the 1s of a word, read with the number of 0s before each, form a partition with at most $k$ parts, each $\le n-k$, whose size is the inversion count.

q-Lucas. Let $q$ have multiplicative order $d$ modulo $p$. The q-binomial theorem ${\prod }_{i=0}^{n-1}(1+q^{i}x)={\sum }_k{q}^{k(k-1)/2}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q{x}^k$ holds by induction on $n$: multiplying by $1+q^{n-1}x$ needs ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q={\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)}_q+q^{n-k}{\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}_q$, the q-Pascal rule obtained by classifying words by their first letter (a leading 1 precedes all $n-k$ zeros). For $n=ad+b$ the factors with $i\ge b$ group into $a$ full periods, each equal to ${\prod }_{i<d}(1+q^{i}x)=1-(-x{)}^d$ (the roots are $-q^{-i}$, all $d$-th roots of $(-1{)}^d$, and the constant term is 1). So ${\prod }_{i<n}(1+q^{i}x)=(1-(-x{)}^d{)}^a{\prod }_{i<b}(1+q^{i}x)$, and for $k=cd+e$ with $0\le e<d$ the coefficient of $x^k$ comes only from $x^{cd}$ in the first factor and $x^e$ in the second: $\left(\genfrac{}{}{0ex}{}{a}{c}\right)(-1{)}^{c(d+1)}{q}^{e(e-1)/2}{\left(\genfrac{}{}{0ex}{}{b}{e}\right)}_q$. On the left the coefficient is $q^{k(k-1)/2}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q$ with $\frac{k(k-1)}{2}=\frac{e(e-1)}{2}+cde+c^2\frac{d(d-1)}{2}+d\frac{c(c-1)}{2}$. The powers $q^0,\dots ,q^{d-1}$ are all the roots of $x^d-1$, so their product is $q^{d(d-1)/2}=(-1{)}^{d+1}$, and $q^d=1$; hence $q^{k(k-1)/2}=q^{e(e-1)/2}(-1{)}^{(d+1)c^2}=q^{e(e-1)/2}(-1{)}^{c(d+1)}$. Cancelling gives ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q=\left(\genfrac{}{}{0ex}{}{a}{c}\right){\left(\genfrac{}{}{0ex}{}{b}{e}\right)}_q$. The code’s reduced needs $n<d$ so that every $1-q^i$ is invertible. Checked against the inversion-count definition and against the table for random $q$, including $q$ of small order.

Related notes

• Counting Fundamentals (twelvefold way)
• Generating Functions
• Counting with Power Series (rows in $O(n\log n)$)