组合数学

· · 个人记录

目录

1. 排列数与组合数

2. 组合数的求法

3. 组合数的应用

4. Lucas定理

5. Catalan数

6. 其他的组合问题

by laihaochen

1. 排列数与组合数

排列数

从n个不同元素中依次取出m个元素排成一列，产生的不同排列的数量为：

A_n^m = \frac{n!}{(n - m)!} = n * (n - 1) * …… * (n - m + 1)

组合数

从n个不同元素中一次取出m个组成一个集合（不考虑顺序），产生的不同集合的数量为：

C_n^m = \frac{n!}{m!(n - m)!} = \frac{n * (n - 1) * …… * (n - m + 1)}{m * (m - 1) * …… * 2 * 1}

性质

  1. C_n^m = C_n^{n - m}
  2. C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1}
  3. C_n^0 + C_n^1 + C_n^2 + …… + C_n^n = 2^n

证明：

性质1. C_n^m = \frac{n!}{m!(n - m)!} = \frac{n!}{(n - m)!(n - (n - m))!} = C_n^{n - m}

性质2. 在n个不同元素中选m个元素可以分为两种情况：

不选第n个元素：从剩下的n - 1个元素中再选m个元素，即C_{n - 1}^m

选第n个元素：从剩下的n - 1个元素中再选m - 1个元素，即C_{n - 1}^ {m - 1}

故共有C_{n - 1}^m + C_{n - 1}^ {m - 1}种

所以，C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1}

性质3. 从n个元素中选若干元素可以分为n + 1种情况：

选0个元素，有C_n^0种

选1个元素，有C_n^1种

……

选n个元素，有C_n^n种

另一方面，每个元素都有选或不选两种可能，故有2^n中不同的选法。

所以，C_n^0 + C_n^1 + C_n^2 + …… + C_n^n = 2^n

2. 组合数的求法

  1. 根据性质2，可以用DP来求组合数，时间复杂度为O(n^2)

  2. 如果题目要求输出C_n^m \pmod p，那么可以先求出n! \pmod p取模的值，在求出m!(n - m)! \pmod p的逆元，乘起来得到C_n^m \pmod p，时间复杂度为O(n)

  3. 用O(n)预处理出阶乘(jc_i)和阶乘的逆元(inv_i)，就可以只用O(1)的时间算出1 \leq y \leq x \leq n的所有组合数C_x^y \equiv jc_x * inv_y * inv_{x - y} \pmod p

  4. Lucas定理 + 3. 后面会介绍

3. 组合数的应用

二项式定理

(a + b)^n = \sum_{k = 0}^n C_n^ka^kb^{n - k}
故加起来可以得到$(a + b)^n = \sum_{k = 0}^n C_n^ka^kb^{n - k}$。 ### [P1313 计算系数](https://www.luogu.com.cn/problem/P1313) 由二项式定理，$(ax + by)^k = \sum_{n = 0}^k C_k^na^nb^{k - n}x^ny^{k - n}$，所以$x^ny^m$的系数是$C_k^na^nb^m$，我们要求的就是$C_k^na^nb^m \pmod {10007}$。 我们可以用$O(log k)$的时间求出$a^nb^m \pmod {10007}$，因为$0 \leq k \leq 1000$，所以我们可以用第$2$种组合数的求法。（注：10007是质数，用快速幂求逆元即可，[详见](https://www.luogu.com.cn/blog/lhc123/chu-tan-shu-lun)）。 ```cpp #include <cstdio> #include <algorithm> const int mod = 10007; long long a, b, k, n, m, ans; long long f (long long x, long long y) { long long res = 1; while (y > 0) { if (y & 1) { res = (res * x) % mod; } x = (x * x) % mod; y >>= 1; } return res % mod; } int main() { scanf ("%lld%lld%lld%lld%lld", &a, &b, &k, &n, &m); ans = (f(a, n) * f(b, m)) % mod; long long jc_n = 1, jc_k = 1, jc_k_n = 1; for (long long i = 1; i <= n; i++) { jc_n = (jc_n * i) % mod; } for (long long i = 1; i <= k; i++) { jc_k = (jc_k * i) % mod; } for (long long i = 1; i <= k - n; i++) { jc_k_n = (jc_k_n * i) % mod; } ans = (ans * jc_k) % mod; ans = (ans * f(jc_n, mod - 2)) % mod; ans = (ans * f(jc_k_n, mod - 2)) % mod; printf ("%lld\n", ans); return 0; } ``` **多重集排列数** 多重集是指包含重复元素的集合，例如$S = \{n_1 * a_1, n_2 * a_2, ……, n_k * a_k\}$，是由$n_1$个$a_1$，$n_2$个$a_2$，……， $n_k$个$a_k$构成的集合，它的全排列个数为： $\frac{n!}{n_1!n_2!……n_k!}

多重集组合数

设S = \{n_1 * a_1, n_2 * a_2, ……, n_k * a_k\}，是由n_1个a_1，n_2个a_2，……， n_k个a_k组成的多重集。从S中取出r \leq n_i(n_i \in [1, k])个元素组成一个多重集（不考虑元素排列的顺序），产生的不同多重集数量为：

C_{k + r - 1}^{k - 1}

证明：

原命题等价于统计下列集合的数量：\{x_1 * a_1, x_2 * a_2, ……, x_k * a_k\}，其中\sum_{i = 1}^{k} x_i = r并且x_i \leq n_i, i \in [1, k]。

因为r \leq n_i, i \in [1, k]，又\sum_{i = 1}^{k} x_i = r，所以必定有x_i \leq n_i, i \in [1, k]。

所以x_i只需满足\sum_{i = 1}^{k} x_i = r，故可以用挡板法来求解。

因为x_i可以为0，所以共有C_{k + r - 1}^{k - 1}种不同序列。

P4778 Counting swaps

我们把题目所给的排列p_1, p_2, ……, p_n中的每个p_i连一条到i的边，这样就可以得到一张n个点的图，并且图中存在若干个环，例如排列 2, 4, 6, 1, 5, 3：

引理：

把一个大小为n的环断成n个自环，至少需要n - 1次操作。

证明：

用数学归纳法：首先，把长度为2的环变为两个自环，需要1次操作。

假设\forall k \leq n - 1，把大小不超过k的环断成k个自环，至少需要k - 1次操作。假设大小为n的环为v_1 \rightarrow v_2 \rightarrow …… \rightarrow v_n \rightarrow v_1，假设我们交换的是v_i与v_j(i < j), 那么原来的环就会变为v_{i + 1} \rightarrow v_{i + 2} \rightarrow …… \rightarrow v_i \rightarrow v_{i + 1}和v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow …… \rightarrow v_j \rightarrow v_{j + 1} \rightarrow …… v_n \rightarrow v_1两个环。

例如：

变为

两个环的大小分别为(j - i)与(n - (j - i))，把这两个环变为自环共需(j - i - 1) + (n - (j - i) - 1) = n - 2，加上刚才交换的一次，共n - 1次操作，由数学归纳法，引理成立。

设f_n表示把大小为n的环变为n个自环不同的方法数。

由上面的证明过程可知，每次要把大小为n的环拆分成两个大小分别为x, y的环，其中x + y = n。T(x, y)表示拆分的不同方法数。画个图易得：

\begin{array}{rcl} x = y, T(x, y) = \frac{n}{2}\\ x \neq y,T(x, y) = n\\ \end{array} \right.

则由多重集排列数可得，f_n = \sum_{x + y = n}T(x, y) * f_x * f_y * \frac{(x + y - 2)!}{(x - 1)!(y - 1)!}

得到了$f_n$，我们再把图给建出来，可以用并查集求出每个环的大小。 假设有$k$个环，环的大小为$cnt_1, cnt_2, ……, cnt_k

同样由多重集排列数可得，ans = \prod_{i = 1}^kf_{cnt_i} * \frac{(n - k)!}{\prod_{i = 1}^k(cnt_i - 1)!}

这样就可以完成O(n^2)做法，但还不足以过掉此题。

打表可得f_i = i^{i - 2}，这样就可以得到O(n log n)做法。

//O(n^2) 
/*#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 9;
long long n, ans, p[N], cnt[N], S[N], f[N], jc[N];
long long T (long long x, long long y) {
    if (x != y) {
        return x + y;
    }
    return x;
}
long long fp (long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return res % mod;
}
long long C (long long x, long long y) {
    return ((jc[x + y - 2] * fp(jc[x - 1], mod - 2)) % mod * fp(jc[y - 1], mod - 2)) % mod;
}
int getf (int x) {
    if (x == S[x]) {
        return x;
    }
    return S[x] = getf(S[x]);
}
void merge (int x, int y) {
    int u = getf(x), v = getf(y);
    if (u != v) {
        S[u] = v;
    }
}
int main() {
    jc[0] = 1;
    for (long long i = 1; i <= 1000; i++) {
        jc[i] = (jc[i - 1] * i) % mod;
    } 
    f[1] = 1;
    for (long long i = 2; i <= 1000; i++) {
        for (long long x = 1; x <= i / 2; x++) {
            long long y = i - x;
            f[i] = (f[i] +  (( (T(x, y) * ( (f[x] * f[y]) % mod )) % mod) * C(x, y)) % mod) % mod;
        }
    }
    int t;
    scanf ("%d", &t);
    while (t--) {
        memset (cnt, 0, sizeof(cnt));
        scanf ("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf ("%lld", &p[i]);
            S[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            merge (p[i], i);
        }
        for (int i = 1; i <= n; i++) {
            cnt[getf(i)]++;
        }
        ans  = 1;
        long long k = 0;
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            ans = (ans * f[cnt[i]]) % mod;
            ans = (ans * fp (jc[cnt[i] - 1], mod - 2)) % mod;
            k++;
        }
        ans = (ans * jc[n - k]) % mod;
        printf ("%lld\n", ans);
    }
    return 0;
}*/
//打表可得f[i] = i^{i - 2}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 9;
long long n, ans, p[N], cnt[N], S[N], f[N], jc[N];
long long T (long long x, long long y) {
    if (x != y) {
        return x + y;
    }
    return x;
}
long long fp (long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return res % mod;
}
long long C (long long x, long long y) {
    return ((jc[x + y - 2] * fp(jc[x - 1], mod - 2)) % mod * fp(jc[y - 1], mod - 2)) % mod;
}
int getf (int x) {
    if (x == S[x]) {
        return x;
    }
    return S[x] = getf(S[x]);
}
void merge (int x, int y) {
    int u = getf(x), v = getf(y);
    if (u != v) {
        S[u] = v;
    }
}
int main() {
    jc[0] = 1;
    for (long long i = 1; i < N; i++) {
        jc[i] = (jc[i - 1] * i) % mod;
    } 
    f[1] = 1;
    for (long long i = 2; i < N; i++) {
        f[i] = fp (i, i - 2);
    }
    int t;
    scanf ("%d", &t);
    while (t--) {
        memset (cnt, 0, sizeof(cnt));
        scanf ("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf ("%lld", &p[i]);
            S[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            merge (p[i], i);
        }
        for (int i = 1; i <= n; i++) {
            cnt[getf(i)]++;
        }
        ans  = 1;
        long long k = 0;
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            ans = (ans * f[cnt[i]]) % mod;
            ans = (ans * fp (jc[cnt[i] - 1], mod - 2)) % mod;
            k++;
        }
        ans = (ans * jc[n - k]) % mod;
        printf ("%lld\n", ans);
    }
    return 0;
}

4. Lucas定理

若p是质数，则对于任意整数1 \leq m \leq n，有：

C_n^m \equiv C_{n \bmod p}^{m \bmod p} * C_{n / p}^{m / p} \pmod p

证明：由二项式定理可知 C_n^m 即为(1 + x)^n中x^m的系数。

同理，对于方程(1 + x)^{n_0}(1 + x^p)^{n_1}……(1 + x^{p^k})^{n_k}（即为把n分解成p进制数）

\because m = m_0 + m_1^p + m_2^{p^2} + …… + m_k^{p^k} $C_{n_1}^{m_1}$为$(1 + x^p)^{n_1}$中$x^{m_1}$的系数。 $\vdots $\therefore C_{n_0}^{m_0} * C_{n_1}^{m_1} * …… * C_{n_k}^{m_k}$即为$(1 + x)^{n_0}(1 + x^p)^{n_1}……(1 + x^{p^k})^{n_k}$中$x_m$的系数 又$(1 + x)^{n_0}(1 + x^p)^{n_1}……(1 + x^{p^k})^{n_k} \equiv (1 + x)^n \pmod p \therefore C_{n_0}^{m_0} * C_{n_1}^{m_1} * …… * C_{n_k}^{m_k} \equiv C_n^m \pmod p \because n_0 = n \bmod p, m_0 = m \bmod p \therefore C_{n_0}^{m_0} = C_{n \bmod p}^{m \bmod p} \therefore$ 将 $C_{n \bmod p}^{m \bmod p} * C_{n / p}^{m / p}$递归展开后可以得到$C_{n_0}^{m_0} * C_{n_1}^{m_1} * …… * C_{n_k}^{m_k}

证毕。

利用Lucas定理和第3.种组合数的求法，我们可以得出一种O(n)预处理，O(\sqrt[p]{n})的做法，但这只适用于p（模数）是质数的情况。

inline void init (long long p) {
    jc[0] = 1;
    for (int i = 1; i <= p; i++) {
        jc[i] = (jc[i - 1] * i) % p;
    }
    inv[p] = 0;
    inv[p - 1] = f (jc[p - 1], p - 2, p);
    for (int i = p - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1)) % p;
    }
}
long long C (int n, int m, int p) {
    if (m > n) {
        return 0;
    } 
    return (((jc[n] * inv[m]) % p) * inv[n - m]) % p;
}
long long Lucas (int n, int m, int p) {
    if (m == 0) {
        return 1;
    }
    return (Lucas (n / p, m / p, p) * C (n % p, m % p, p)) % p;
}

P2480 [SDOI2010]古代猪文

题目大意：给定n, g, 求g^{\sum_{d|n} C_n^d} \pmod {999911659}

显然指数很大，我们求不了。所以我们想办法将指数取模。

因为999911659是质数，所以由扩展欧拉定理可得:g^{\sum_{d|n} C_n^d} \equiv g^{\sum_{d|n} C_n^d \bmod 999911658} \pmod {999911659}

因为$n \leq 10^9$，所以我们必须用$O(n)$的时间求出$C_n^d$，所以就必须用第4.种组合数的求法。 然鹅这道数论大杂烩还没有结束，因为$Lucas$定理只适用于模数是质数的情况。 我们把$999911658$分解质因数得到$999911658 = 2 * 3 * 4679 * 35617

所以我们分别求出C_n^d对2, 3, 4679, 35617取模的余数，再用中国剩余定理求出答案。

注意用long long。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int mod1 = 999911659, mod2 = 999911658, N = 50005;
int n, g, cnt, factor[N];
long long jc[N], inv[N];
int p[10] = {0, 2, 3, 4679, 35617}, a[10];
long long f (long long a, long long b, long long k) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % k;
        }
        b >>= 1;
        a = (a * a) % k;
    }
    return res % k;
}
void getfactor (int x) {
    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i != 0) {
            continue;
        }
        factor[++cnt] = i;
        if (i != n / i) {
            factor[++cnt] = x / i;
        }
    }
}
//求指数 
inline void init (long long p) {
    jc[0] = 1;
    for (int i = 1; i <= p; i++) {
        jc[i] = (jc[i - 1] * i) % p;
    }
    inv[p] = 0;
    inv[p - 1] = f (jc[p - 1], p - 2, p);
    for (int i = p - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1)) % p;
    }
}
long long C (int n, int m, int p) {
    if (m > n) {
        return 0;
    } 
    return (((jc[n] * inv[m]) % p) * inv[n - m]) % p;
}
long long Lucas (int n, int m, int p) {
    if (m == 0) {
        return 1;
    }
    return (Lucas (n / p, m / p, p) * C (n % p, m % p, p)) % p;
}
long long calc (int x) {
    init(p[x]);
    for (int i = 1; i <= cnt; i++) {
        a[x] = (a[x] + Lucas(n, factor[i], p[x])) % p[x];
    }
}
// 
long long crt () {
    long long ans = 0, M = 1;
    for (int i = 1; i <= 4; i++) {
        M *= p[i];
    }
    for (int i = 1; i <= 4; i++) {
        long long Mi = M / p[i];
        long long Mi_1 = f(Mi, p[i] - 2, p[i]);
        ans = ((ans + ((Mi * Mi_1) % M) * a[i]) % M + M) % M; 
    }
    return ans % M;
}
int main() {
    scanf ("%d%d", &n, &g); 
    if (g % mod1 == 0) {//当mod1 | g就不互质了，就不能用欧拉定理 
        printf ("0\n");
        return 0;
    }
    getfactor (n);
    for (int i = 1; i <= 4; i++) {
        calc (i);
    }
    printf ("%lld\n", f(g, crt(), mod1));
    return 0;
}

5. Catalan数

给定 n 个 0 与 n 个 1 ，他们按照某种顺序排成长度为 2n 的序列，满足任意前缀中 0 的个数都不少于 1 的个数的序列的数量为：

Cat_n = \frac{C_{2n}^n}{n + 1}

证明：

假设 n 个 0 与 n 个 1 排成的长度为 2n 的序列 S 不满足任意前缀中 0 的个数都不少于 1 的个数，那么其中必存在一个最小的位置2p + 1 \in [1, 2n]，使得S[1 ~ 2p +1]中有p个0，p + 1个1。而把S[2p + 2~2n]中的所有数取反后，包含n - p - 1个0，n - p个1。所以我们就得到了一个由n - 1个0与n + 1个1组成的序列。

同理，n - 1个0与n + 1个1组成的序列S'中，必有一个最小的位置2p' + 1 \in [1, 2n]，使得S'[1~2p' + 1]中有p'个0，p' + 1个1，把S'[2p' + 2~2n]中的所有数取反后，包含n - p'个0，n - p' - 1个1。所以我们就得到了一个前缀中0的个数比1的个数少的序列。

因此，以下两种序列的数量相等：

  1. 由n个0与n个1组成的，存在一个前缀0比1多的序列。

  2. 由n - 1个0与n + 1个1组成的序列。

显然，第2.种序列有C_{2n}^{n - 1}个。

综上，由n个0与n个1组成的，任意前缀中0的个数都不少于1的个数的序列数量为：

Cat_n = C_{2n}^n - C_{2n}^{n - 1} = \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n + 1)!(n - 1)!} \because (n + 1)! = n!(n + 1)

又 (n - 1)! = n!\frac{1}{n}

\therefore (n + 1)!(n - 1)! = n!n!\frac{n + 1}{n} \therefore Cat_n = \frac{(2n)!}{n!n!} - \frac{(2n)!}{n!n!\frac{n + 1}{n}} = \frac{(2n)!}{n!n!} - \frac{(2n)!/ \frac{n + 1}{n}}{n!n!} = \frac{(2n)!}{n!n!} - \frac{(2n)!\frac{n}{n + 1}}{n!n!} \therefore Cat_n = \frac{(2n)!(1 - \frac{n}{n + 1})}{n!n!} = \frac{(2n)!\frac{1}{n + 1}}{n!n!} = \frac{(2n)! / (n!n!)}{n + 1} = \frac{C_{2n}^n}{n + 1}

更多 Catalan 数的应用，可见这里

注：在不相交弦问题中，最顶端的点的顺时针方向的第一条线的左右括号写反了。

6. 其他的组合问题

6.1 小球

1. n 个相同的小球，选 m 个 (n \geq m)

> #### 2. $n$ 个不同的小球，选 $m$ 个 $(n \geq m) > #### 3. $n$ 个相同的小球，选 $m$ 个排成一行 $(n \geq m) > #### 4. $n$ 个不同的小球，选 $m$ 个排成一行 $(n \geq m) > ### 6.2 小球与盒子 > #### 1. $n$ 个相同的球，放入 $m$ 个相同的盒子，盒子不能为空 $(n \geq m)

这个问题需要用 dp 来解决

状态：f[i][j] 表示用了 i 个球，j 个盒子的种数（盒子不能为空）。

我们分类讨论，考虑是否有盒子中只有一个球：

那么我们把这个盒子去掉，剩下的有 f[i - 1][j - 1] 种情况。

那么我们把所有盒子都去掉一个球，剩下的有 f[i - j][j] 种情况。

所以得出转移方程：f[i][j] = f[i - 1][j - 1] + f[i - j][j]

显然，边界是 f[1][1] = 1

目标就是 f[n][m]

f[1][1] = 1; 
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m && j <= i; j++) {//注意这里还要让j <= i
        f[i][j] = f[i - 1][j - 1] + f[i - j][j];
    }
}

2. n 个相同的球，放入 m 个相同的盒子，盒子能为空

类似地，我们定义 f[i][j] 表示用了 i 个球，j 个盒子的种数（盒子能为空）。

这次我们来看有无空盒子：

那么我们去掉这个盒子，剩下的有 f[i][j - 1] 种情况。

那么我们把所有的盒子中去掉一个球，剩下的有 f[i - j][j - 1] 种情况。

所以得出转移方程：f[i][j] = f[i][j - 1] + f[i - j][j]

显然，边界是 f[0][0] = 1

由于没有了 n, m 的限制，我们求目标时需要分类讨论 n, m 的关系：

由于每个小球只能进入一个盒子，所以只有 n 个盒子是有意义的，故目标为 f[n][n]

f[n][m]

我们还有另一种做法：我们用盒子与小球 1 的 dp，最后的答案为 \sum_{i = 1}^m f[n][i]

3. n 个相同的球，放入 m 个不同的盒子，盒子不能为空 (n \geq m)

> #### 4. $n$ 个相同的球，放入 $m$ 个不同的盒子，盒子能为空 把每个盒子中都放一个球，再用挡板法： $C_{n + m - 1}^{m - 1}

5. n 个不同的球，放入 m 个相同的盒子，盒子不能为空 (n \geq m)

定义：f[i][j] 表示用了 i 个球，j 个盒子的种数。

我们考虑把第 i 个球放入一个新盒子，还是放过球的盒子：

f[i - 1][j - 1] 方程：$f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j]

因为盒子不能为空，所以边界为：f[i][i] = 1, i \in [1, n]

答案：f[n][m]

6. n 个不同的球，放入 m 个相同的盒子，盒子能为空

我们可以转换为 5，只需在求答案时枚举有多少个盒子放了球，即：

\sum_{i = 1}^n f[n][k]

7. n 个不同的球，放入 m 个不同的盒子，盒子不能为空 (n \geq m)

我们可以转换为 5，相当于把每种情况的盒子进行全排列，所以答案为：

m! * f[n][m]

8. n 个不同的球，放入 m 个不同的盒子，盒子能为空

我们可以发现每个球都有 m 种选择，所以共有 n^m 种方案。

6.3 圆排列（第一类斯特林数）

定义 f[i][j] 表示 i 个不同元素构成 j 个圆排列的方案数

分类讨论第 i 个元素是放在了一个新的圆里还是放在已有的某个元素后面：

f[i - 1][j - 1] (i - 1) * f[i - 1][j]$，由于每个元素不同，所以要乘上 $i - 1

故 f[i][j] = f[i - 1][j - 1] + (i - 1) * f[i - 1][j]

边界：f[i][i] = 1, i \in [1, n]，答案：f[n][m]

其实这个 dp 是与 6.3 盒子与小球中的第 5 种完全相同的。

6.4 正难则反

在 n 个不同的球中选 m 个球，不能选相邻的两个球，有多少种方案。(n \geq 2 * m - 1)

我们考虑剩下来的 n - m 个球，这样就把问题转化为在 n - m 个球中，不相邻的插入 m 个球。

显然，就是在 n - m 个球制造出的 n - m + 1 个空隙中放入 m 个球，即 C_{n + m - 1}^m

6.5 错排问题

把 n 个编号为 1 - n 的物体放入 n 个编号为 1 - n 的盒子，每个盒子里放一个物体，求有几种方案使得所有球和所在的盒子的编号都不相同，即 n 的错排数。

我们设 f_i 表示 i 的错排数。

我们假设物体 a 放到了盒子 B 中，我们考虑物体 b 与盒子 A：

那么剩下的 n - 2 个物体和盒子要满足错排，故有 f_{i - 2} 种方案。

因为物体 b 也不能放入盒子 A 中，所以我们可以把盒子 A 当成盒子 B，这样就使得剩下的 n - 1 个物体都有对应不能放的盒子，故有 f_{i - 1} 中方案。

所以物体 a 放到除 A 盒子之外的 i - 1 个盒子都有 f_{i - 1} + f_{i - 2} 种方案，故 f_i = (i - 1) * (f_{i - 1} + f_{i - 2})

边界：f_1 = 0, f_2 = 1，答案：f_n

6.6 整数划分

（下列的整数都默认是正整数）

1. n 划分成若干个整数之和的方案数。

可以用完全背包解决，有 n 个物品，第 i 个物品的体积是 i，f_i 就表示 i 划分成若干个整数之和的方案数。

f[1] = 1;//边界
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        f[j] += f[j - i];
    }
}

2. n 划分成若干个不同整数之和的方案数。

```cpp f[1] = 1; for (int i = 1; i <= n; i++) { for (int j = n; j >= i; j--) { f[j] += f[j - i]; } } ``` > #### 3. $n$ 划分成 $m$ 个整数之和的方案数。 和小球与盒子 $1$ 一样： ```cpp f[1][1] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m && j <= i; j++) { f[i][j] = f[i - 1][j - 1] + f[i - j][j]; } } ``` > #### 4. $n$ 划分成 $m$ 个不同整数之和的方案数。 我们可以转换为 $3$，像完全背包改成 $01$ 背包一样： ```cpp f[1][1] = 1; for (int i = 1; i <= n; i++) { for (int j = min (i, m); j >= 1; j--) { f[i][j] = f[i - 1][j - 1] + f[i - j][j]; } } ``` > #### 5. $n$ 划分成最大数不超过 $m$ 的若干整数之和的方案数。 我们可以转换为 $1$，只是限定了物品的种类： ```cpp f[1] = 1; for (int i = 1; i <= m; i++) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; } } ``` > #### 6. $n$ 划分成最小数不少于 $m$ 的若干整数之和的方案数。 我们可以转换为 $1$，只是限定了物品的种类： ```cpp f[1] = 1; for (int i = m; i <= n; i++) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; } } ``` > #### 7. $n$ 划分成最大数不超过 $m$ 的若干不同整数之和的方案数。 我们可以转换为 $2$，只是限定了物品的种类： ```cpp f[1] = 1; for (int i = 1; i <= m; i++) { for (int j = n; j >= i; j--) { f[j] += f[j - i]; } } ``` > #### 8. $n$ 划分成最小数不少于 $m$ 的若干不同整数之和的方案数。 我们可以转换为 $2$，只是限定了物品的种类： ```cpp f[1] = 1; for (int i = m; i <= n; i++) { for (int j = n; j >= i; j--) { f[j] += f[j - i]; } } ``` > #### 9. $n$ 划分成若干个奇数的方案数。 ```cpp f[1] = 1; for (int i = 1; i <= n; i += 2) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; } } ``` > #### 10. $n$ 划分成若干个偶数的方案数。 ```cpp f[1] = 1; for (int i = 2; i <= n; i += 2) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; } } ```