定义

排列数

$$A(n,m) = A_n^m = \frac{n!}{(n-m)!}$$

组合数定义

$$C(n,m) = C_n^m = \left(\begin{smallmatrix}n\\m\end{smallmatrix}\right) = \frac{n!}{m!(n-m)!}$$

（注意组合数记法中，$\left(\begin{smallmatrix}n\\m\end{smallmatrix}\right)$ 是上 $n$ 下 $m$，$C_n^m$ 是上 $m$ 下 $n$）

组合数的递推公式

$$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$$

求法

最原始的求法

1
2
3
4
5
6
7
8
9
10
11
int comb(int n, int m)
{
    int p = 1, q = 1;
    for (int i = 1; i <= m; i++)
    {
        p = p * (n - i + 1);
        q = q * i;
    }
    if (p % q == 0) p /= q;
    return p / q;
}

递推

$$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$$

仅能用于预处理小范围的组合数。

1
2
3
4
5
6
7
ll C[maxn][maxn] = 0;
int init(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++)
            C[i][j]  = (j ? c[i - 1][j] + c[i - 1][j - 1] : 1);
}

预处理阶乘、逆元，用公式算

$$C(n,m) = C_n^m = \frac{n!}{m!(n-m)!}$$

1
2
3
4
5
6
7
8
9
10
11
ll fac[maxn];
void init(int n)
{
    fac[0] = 1;
    for (int i = 1; i< n; i++)
        fac[i] = i * fac[i-1];
}
ll C(int a, int b, int m)
{
    return a >= b ? fac[a] * inv(fac[b]) % m * inv(fac[a-b]) % m : 0;
}

Lucas定理

$$C^{ap+b}_{cp+d} \equiv C^{a}_{c} \cdot C^{b}_{d} (mod\space p)$$

或

$$C^{m}_{n} \equiv C^{m/p}_{n/p} \cdot C^{m\%p}_{n\%p} (mod\space p)$$

推导：费马小定理

Catlan 数

Catlan

N 球放 M 盒问题

见链接

Stirling 数

LGV 定理 ——2019.7.23

CodeForces 348D
两只乌龟走路，要求不能相交。

由 LGV 定理可得，如果起点集合为 $\{a_1,a_2,a_3,…,a_n\}$，终点集合为 $\{b_1,b_2,b_3,…,b_n\}$，则要求他们走路不相交的路径对 pair 总数有：

LGV
LGV

其中,$e(a,b)$ 表示从点 $a$ 到 点 $b$ 的边权（在这里即指可走路径数）。

CodeForces 上这道题退化到只有两个起点即 $(1,2),(2,1)$ 和两个终点即 $(m-1,n),(n,,m-1)$，按照公式算一下路径即可。

\begin{equation}
ans =
\left |
\begin{matrix}
e(1,2) \to e(n-1,m) & e(1,2) \to e(m-1,n) \\
e(2,1) \to e(n-1,m) & e(2,1) \to e(m-1,n)
\end{matrix}
\right |
\end{equation}