组合数

$${\displaystyle (\genfrac{}{}{0ex}{}{n}{m})}={\displaystyle (\genfrac{}{}{0ex}{}{n-1}{m})}+{\displaystyle (\genfrac{}{}{0ex}{}{n-1}{m-1})}$$$${\displaystyle (\genfrac{}{}{0ex}{}{n}{m})}={\displaystyle (\genfrac{}{}{0ex}{}{n}{n-m})}$$$$\sum _{i=0}^n{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}=2^n$$$$\sum _{i=1}^{n}i{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}=n{2}^{n-1}$$$$\sum _{i=0}^k{\displaystyle (\genfrac{}{}{0ex}{}{n+i}{i})}={\displaystyle (\genfrac{}{}{0ex}{}{n+k+1}{k})}$$$${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{k+1})}=\sum _{i=0}^n{\displaystyle (\genfrac{}{}{0ex}{}{i}{k})}$$$$\sum _{i=0}^k{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}{\displaystyle (\genfrac{}{}{0ex}{}{m}{k-i})}={\displaystyle (\genfrac{}{}{0ex}{}{n+m}{k})}$$

卡特兰数

$$H_n={\displaystyle \frac{{\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}}{n+1}}$$$$H_n=\{\begin{array}{l}\sum _{i=1}^n{H}_{i-1}{H}_{n-i}n\ge 2\\ 1& n=0,1\end{array}$$$$H_n={\displaystyle \frac{4n-2}{n+1}}{H}_{n-1}$$$$H_n={\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}-{\displaystyle (\genfrac{}{}{0ex}{}{2n}{n-1})}$$

斯特林数

第一类斯特林数

存在 $k$ 个置换环的大小为 $n$ 的置换：$\left[\begin{array}{c}n\\ k\end{array}\right]$

约定 $\left[\begin{array}{c}0\\ 0\end{array}\right]=1$；当 $n>0$ 时 $\left[\begin{array}{c}n\\ 0\end{array}\right]=0$，当 $k<0$ 或 $k>n$ 时取 $0$。

递推公式

$$\left[\begin{array}{c}n\\ k\end{array}\right]=\left[\begin{array}{c}n-1\\ k-1\end{array}\right]+(n-1)\times \left[\begin{array}{c}n-1\\ k\end{array}\right]$$

性质式

$$n!=\sum _{i=0}^n\left[\begin{array}{c}n\\ i\end{array}\right]$$$$x^{\underset{―}{n}}=\sum _{i=0}^n\left[\begin{array}{c}n\\ i\end{array}\right](-1{)}^{n-i}{x}^i$$

第二类斯特林数

$n$ 个有标号的球分配到 $k$ 个无标号的盒子的方案数：$\left\{\begin{array}{c}n\\ k\end{array}\right\}$

约定 $\left\{\begin{array}{c}0\\ 0\end{array}\right\}=1$；当 $n>0$ 时 $\left\{\begin{array}{c}n\\ 0\end{array}\right\}=0$，当 $k<0$ 或 $k>n$ 时取 $0$。

递推公式

$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\}+k\times \left\{\begin{array}{c}n-1\\ k\end{array}\right\}$$

性质式

$$x^n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}{x}^{\underset{―}{i}}$$

特别地：

$$\sum _{i=0}^n{i}^k=\sum _{i=0}^k\left\{\begin{array}{c}k\\ i\end{array}\right\}{\displaystyle \frac{(n+1{)}^{\underset{―}{i+1}}}{i+1}}$$

斐波那契数列

定义 $f_i=\{\begin{array}{ll}0& i=0\\ 1& i=1\\ f_{i-1}+f_{i-2}& i\ge 2\end{array}$ 的数列为斐波那契数列。

通项公式：

$$f_n={\displaystyle \frac{(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n}{\sqrt{5}}}$$

若 $5$ 在给定模数模意义下存在二次剩余，结合二次剩余和逆元可在 $O(\log n)$ 时间求解 $f_n$。

注：常见模数 ${10}^9+7$ 和 $998244353$，对 $5$ 不存在二次剩余。${10}^9+9$ 对 $5$ 存在二次剩余，解为：$383008016,616991993$。

倍增：

$$f_{2k}=f_k(2f_{k+1}-f_k),f_{2k+1}=f_{k+1}^2+f_k^2$$

根据奇偶性递推 $f_n$ 即可。

时间复杂度：$O(\log n)$，常数较小。

矩阵递推：

$$[f_{n-1},f_n]=[f_{n-2},f_{n-1}]\times \left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$

令 $p=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$，$[f_n,f_{n+1}]=[f_0,f_1]\times p^n$

利用矩阵快速幂，可在 $O(2^3\times \log n)$ 的时间计算 $f_n$。

预处理 $2^i$ 矩阵，可将询问转换成向量乘矩阵，矩乘满足结合律，时间复杂度：$O(2^2\times \log n)$。

性质

• $f_{n-1}{f}_{n+1}-f_n^2=(-1{)}^n$
• $f_{n+k}=f_k{f}_{n+1}+f_{k-1}{f}_n$，特别地 $f_{2n}=f_n(f_{n+1}+f_{n-1})$
• $gcd(f_a,f_b)=f_{gcd(a,b)}$，其中 $a,b\ge 1$
• $n\ge 1,k\ge 0\to f_n\mid f_{nk}$
• 由 gcd 恒等式可得，当 $a\ge 3,b\ge 1$ 时，$f_a\mid f_b\iff a\mid b$；$a=1,2$ 时 $f_a=1$，会整除任意 $f_b$，上述等价关系不再普遍成立

模意义下的周期性

记斐波那契数列模 $m$ 的最小正周期为 $\pi (m)$。正整数 $T$ 是它的一个周期，当且仅当 $(f_T,f_{T+1})\equiv (0,1)(\mathrm{mod}m)$。

令模数为 $m$，斐波那契数列的最小正周期不超过 $6m$。

模数较小时暴力枚举求周期即可。

斐波那契数列模 $2$ 的最小正周期是 $3$，模 $5$ 的最小正周期是 $20$。

对于奇素数 $p\equiv 1,4(\mathrm{mod}5)$，$p-1$ 是斐波那契数列模 $p$ 的周期。

对于奇素数 $p\equiv 2,3(\mathrm{mod}5)$，$2p+2$ 是斐波那契数列模 $p$ 的周期。

上面给出的是候选周期，不一定是最小周期。可以分解候选周期，并依次尝试约去质因子；使用 $(f_T,f_{T+1})\equiv (0,1)(\mathrm{mod}p)$ 检验，得到 $\pi (p)$。

对于素数幂，若 $k\ge 2$ 且 $M=\pi (p^{k-1})$，则 $pM$ 是模 $p^k$ 的一个候选周期，且

$$M\mid \pi (p^k)\mid pM.$$

因此 $\pi (p^k)$ 只能是 $M$ 或 $pM$。需要先检验 $M$ 在模 $p^k$ 下是否仍为周期，不能无条件认为最小周期每层都恰好乘 $p$。

令 $m=\prod p_i^{a_i}$，逐层求出每个最小周期 $\pi (p_i^{a_i})$ 后，根据中国剩余定理有

$$\pi (m)=\underset{i}{\mathrm{lcm}}\pi (p_i^{a_i}).$$

错位排列

定义 $D_n$ 表示满足 $p_i\ne i$ 的 $n$ 元排列数量，并约定 $D_0=1$。

$$D_n=n!\sum _{i=0}^n{\displaystyle \frac{(-1{)}^i}{i!}}$$$$D_n=n{D}_{n-1}+(-1{)}^n(n\ge 1)$$

指数生成函数

$$D(x)=\sum _{n\ge 0}{D}_n\frac{x^n}{n!}=\text{exp}(-\ln (1-x)-x)$$

贝尔数

定义 $B_n$ 表示把大小为 $n$ 的集合划分成若干非空子集的方案数，并约定空集只有一种划分，即 $B_0=1$。

$$B_{n+1}=\sum _{i=0}^n{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}{B}_i(n\ge 0)$$$$B_n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}(n\ge 0)$$

贝尔三角形

定义 $a_{0,0}=1$。对于 $n\ge 1$，先令 $a_{n,0}=a_{n-1,n-1}$，再令

$$a_{n,m}=a_{n,m-1}+a_{n-1,m-1}(1\le m\le n),$$

则 $B_n=a_{n,0}$。

指数生成函数

$$B(x)=\sum _{n\ge 0}{B}_n\frac{x^n}{n!}=\text{exp}(e^x-1)$$

欧拉数

定义 $E(n,m)$ 表示 $n$ 元排列中恰好有 $m$ 个上升位置的排列数量，即恰好有 $m$ 个 $i\in [1,n-1]$ 满足 $p_i<p_{i+1}$。

递推式：

$$E(n,m)=\{\begin{array}{ll}1& n=0\wedge m=0\\ 0& m<0\vee (n=0\wedge m\ne 0)\vee (n\ge 1\wedge m\ge n)\\ (n-m)E(n-1,m-1)+(m+1)E(n-1,m)& n\ge 1,0\le m<n\end{array}$$

分拆数

定义 $p(n,k)$ 表示 $n=\sum _{i=1}^k{r}_i$ 且 $r_1\ge r_2\ge \cdots \ge r_k\ge 1$ 的方案数。约定 $p(0,0)=1$，下标越界时取 $0$，则 $p_n=\sum _{k=0}^{n}p(n,k)$，特别地 $p_0=1$。

分拆数增长率相对不大：

• $p_n\le 2\times {10}^5,n\le 50$
• $p_n\le {10}^6,n\le 60$
• $p_n\le 5\times {10}^6,n\le 70$

普通生成函数：

$$\begin{array}{rl}P(x)& =\sum _{n=0}^{\mathrm{\infty }}{p}_n{x}^n=\prod _{i=1}^{\mathrm{\infty }}(1-x^i{)}^{-1}\\ & =\text{exp}(-\sum _{i=1}^{\mathrm{\infty }}\ln (1-x^i))=\text{exp}\left(\sum _{i=1}^{\mathrm{\infty }}\sum _{j=1}^{\mathrm{\infty }}\frac{x^{ij}}{j}\right)\\ & =\text{exp}\left(\sum _{n=1}^{\mathrm{\infty }}\frac{{\sigma }_1(n)}{n}{x}^n\right).\end{array}$$

其中 ${\sigma }_1(n)=\sum _{d\mid n}d$ 表示 $n$ 的正因数之和。

性质：

设 $p_n(k)$ 是最大部分为 $k$ 的 $n$ 的分拆数量，$q_n(k)$ 是恰好 $k$ 个部分的分拆数量。

$$p_n(k)=q_n(k)$$

根据此性质，求 $p(n)$ 时可以根据拆分出 $r_i$ 的大小根号分治，时间复杂度：$O(n\sqrt{n})$。

设 $p_n^o$ 是把 $n$ 分拆成若干奇数部分的方案数，$p_n^d$ 是把 $n$ 分拆成若干互不相同部分的方案数。

$$p_n^o=p_n^d$$

五边形数定理：

Euler 五边形数定理给出

$$\mathrm{\Phi }(x)=\prod _{i=1}^{\mathrm{\infty }}(1-x^i)=1+\sum _{k=1}^{\mathrm{\infty }}(-1{)}^k(x^{k(3k-1)/2}+x^{k(3k+1)/2}).$$

令

$$g_k^{-}=\frac{k(3k-1)}{2},g_k^{+}=\frac{k(3k+1)}{2}(k\ge 1),$$

二者称为广义五边形数。其指数依次为 $1,2,5,7,12,15,\dots$，在 $\mathrm{\Phi }(x)$ 中的符号按 $-,-,+,+,\dots$ 成对出现。

由于 $P(x)=\mathrm{\Phi }(x{)}^{-1}$，比较 $P(x)\mathrm{\Phi }(x)=1$ 的 $x^n$ 系数，并约定 $p_0=1$、$p_n=0(n<0)$，可得

$$p_n=\sum _{k=1}^{\mathrm{\infty }}(-1{)}^{k-1}(p_{n-g_k^{-}}+p_{n-g_k^{+}}).$$

递推中的符号按 $+,+,-,-,\dots$ 成对出现。因为 $g_k^{\pm }=\mathrm{\Theta }(k^2)$，对每个 $n$ 只有 $O(\sqrt{n})$ 个有效项，计算 $p_0,\dots ,p_n$ 的时间复杂度为 $O(n\sqrt{n})$。