Math
Modular arithmetic, number theory, combinatorics, and convolution.
Binomial and multinomial identities
Unless stated otherwise, all parameters are nonnegative integers and
\(\binom nk=0\) when \(k\notin[0,n]\).
\[
\binom nk=\binom{n-1}{k-1}+\binom{n-1}k,\qquad
\binom nk=\binom n{n-k},\qquad
\sum_{k=0}^{n}\binom nk=2^n.
\]
Vandermonde and its central special case:
\[
\sum_k\binom rk\binom s{n-k}=\binom{r+s}n,\qquad
\sum_{k=0}^{n}\binom nk^2=\binom{2n}n.
\]
Hockey-stick, weighted sums, and binomial inversion:
\[
\sum_{i=r}^{n}\binom ir=\binom{n+1}{r+1},\qquad
\sum_{k=0}^{n}k\binom nk=n2^{n-1},\qquad
\sum_{k=0}^{n}k(k-1)\binom nk=n(n-1)2^{n-2}.
\]
\[
g_n=\sum_{k=0}^{n}\binom nk f_k
\iff
f_n=\sum_{k=0}^{n}(-1)^{n-k}\binom nk g_k.
\]
\[
\binom{n}{n_1,\ldots,n_m}=\frac{n!}{\prod_i n_i!}
\quad\left(\sum_i n_i=n\right),\qquad
(x_1+\cdots+x_m)^n
=\sum_{n_1+\cdots+n_m=n}\binom{n}{n_1,\ldots,n_m}\prod_i x_i^{n_i}.
\]
Stirling, Eulerian, and Bell numbers
The unsigned first-kind numbers count permutations with \(k\) cycles; the
second-kind numbers count partitions into \(k\) nonempty unlabeled blocks:
\[
c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k),\qquad
\sum_{k=0}^{n}c(n,k)x^k=x(x+1)\cdots(x+n-1).
\]
\[
S(n,k)=S(n-1,k-1)+kS(n-1,k)
=\frac1{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n.
\]
\[
x^n=\sum_{k=0}^{n}S(n,k)x(x-1)\cdots(x-k+1),\qquad
B_n=\sum_{k=0}^{n}S(n,k),\qquad
\sum_{n\ge0}B_n\frac{x^n}{n!}=e^{e^x-1}.
\]
\[
\text{For }n\ge1,\quad
\left\langle{n\atop k}\right\rangle
=(n-k)\left\langle{n-1\atop k-1}\right\rangle
+(k+1)\left\langle{n-1\atop k}\right\rangle
=\sum_{j=0}^{k}(-1)^j\binom{n+1}{j}(k+1-j)^n.
\]
Here \(\left\langle{n\atop k}\right\rangle\) counts permutations of
\([n]\) with exactly \(k\) descents; it is zero outside \(0\le k<n\).
\[
C_n=\frac1{n+1}\binom{2n}{n},\qquad
C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i},\qquad
D_n=(n-1)(D_{n-1}+D_{n-2})
=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.
\]
\[
\text{nonnegative stars and bars}=\binom{n+k-1}{k-1},\qquad
\text{positive stars and bars}=\binom{n-1}{k-1}.
\]
\[
p(0)=1,\quad p(n)=0\ (n<0),\qquad
\sum_{n\ge0}p(n)x^n=\prod_{k\ge1}\frac1{1-x^k},\qquad
p(n)=\sum_{k\ne0}(-1)^{k+1}p\!\left(n-\frac{k(3k-1)}2\right).
\]
Burnside, necklaces modulo rotation with \(q\) colors, and labeled trees:
\[
|X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|,\qquad
N_q(n)=\frac1n\sum_{d\mid n}\varphi(d)q^{n/d}.
\]
\[
\#\text{ trees}=n^{n-2},\qquad
\#\text{ trees with degrees }d_i
=\frac{(n-2)!}{\prod_i(d_i-1)!}
\quad\left(d_i\ge1,\ \sum_i d_i=2n-2\right).
\]
For the Laplacian \(L\) of an undirected graph, let \(L^{(r)}\) denote the
matrix obtained by deleting row and column \(r\). Then the Matrix-Tree theorem
gives
\[
\tau(G)=\det L^{(r)}.
\]
For a strongly connected Eulerian directed multigraph, fix an edge \(e\) whose
tail is \(w\). Let \(t_w(G)\) be the number of spanning in-arborescences rooted
at \(w\), and let \(\operatorname{EC}_e(G)\) count edge-distinct Euler circuits
whose first edge is \(e\). The BEST theorem states
\[
\operatorname{EC}_e(G)=t_w(G)
\prod_{v\in V}(\operatorname{outdeg}(v)-1)!.
\]
Finite sums and inclusion-exclusion
\[
\sum_{i=0}^{n}x^i=\frac{x^{n+1}-1}{x-1},\qquad
\sum_{i=0}^{n}ix^i
=\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2}.
\]
\[
\sum_{i=1}^{n}i=\frac{n(n+1)}2,\qquad
\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}6,\qquad
\sum_{i=1}^{n}i^3=\left(\frac{n(n+1)}2\right)^2.
\]
\[
\left|\bigcup_{i=1}^{n}A_i\right|
=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}
\left|\bigcap_{i\in I}A_i\right|.
\]
Number theory
\[
\gcd(a,b)\operatorname{lcm}(a,b)=|ab|,\qquad
\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right),\qquad
\sum_{d\mid n}\varphi(d)=n.
\]
\[
\gcd(a,m)=1\Longrightarrow a^{\varphi(m)}\equiv1\pmod m,\qquad
a^{p-1}\equiv1\pmod p\quad(p\text{ prime},\ p\nmid a).
\]
\[
g(n)=\sum_{d\mid n}f(d)
\iff
f(n)=\sum_{d\mid n}\mu(d)g(n/d),\qquad
\sum_{d\mid n}\mu(d)=[n=1].
\]
For coprime \(m,n\), if \(x\equiv a\pmod m\) and \(x\equiv b\pmod n\):
\[
x\equiv a+m\bigl((b-a)m^{-1}\bmod n\bigr)\pmod{mn}.
\]
Generating functions and interpolation
\[
[x^n](A(x)B(x))=\sum_{k=0}^{n}a_kb_{n-k},\qquad
a_n=\sum_{i=1}^{d}c_i a_{n-i}
\Longrightarrow
A(x)=\frac{P(x)}{1-c_1x-\cdots-c_dx^d}.
\]
\[
P(x)=\sum_{i=0}^{n}y_i
\prod_{\substack{0\le j\le n\\j\ne i}}
\frac{x-x_j}{x_i-x_j},\qquad P(x_i)=y_i.
\]
Newton identities, with power sums \(p_i=\sum_jx_j^i\) and elementary
symmetric polynomials \(e_i\):
\[
ke_k=\sum_{i=1}^{k}(-1)^{i-1}e_{k-i}p_i.
\]
Probability
\[
\mathbb E\!\left[\sum_iX_i\right]=\sum_i\mathbb E[X_i],\qquad
\operatorname{Var}(X)=\mathbb E[X^2]-\mathbb E[X]^2,\qquad
\mathbb E[\mathbf1_A]=\Pr(A).
\]
\[
X\sim\operatorname{Bin}(n,p):\quad
\Pr(X=k)=\binom nkp^k(1-p)^{n-k},\quad
\mathbb E[X]=np,\quad\operatorname{Var}(X)=np(1-p).
\]
\[
\Pr(X=k)_{\rm hypergeom}
=\frac{\binom Kk\binom{N-K}{n-k}}{\binom Nn},\qquad
\Pr(A\mid B)=\frac{\Pr(B\mid A)\Pr(A)}{\Pr(B)}.
\]