2020-2021:teams:legal_string:jxm2001:二项式反演
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:二项式反演 [2020/08/21 10:31] jxm2001 |
2020-2021:teams:legal_string:jxm2001:二项式反演 [2020/08/21 11:08] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| ===== 算法例题 ===== | ===== 算法例题 ===== | ||
| - | ==== 题意 ==== | + | ==== 例题一 ==== |
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 求错排数 $D_n$。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 考虑任意排列，有 $n!$ 种，其中恰有 $i$ 封信错排的方案数为 ${n\choose i}D_i$，于是 $n!=\sum_{i=0}^n{n\choose i}D_i$。 | ||
| + | |||
| + | 根据二项式反演，有 $D_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}i!$ | ||
| + | |||
| + | ==== 例题二 ==== | ||
| + | |||
| + | === 题意 === | ||
| 一个有 $n$ 个元素的集合，现在要从他的所有子集中取出至少一个集合，使得所选子集的交集的元素个数为 $k$，求方案数。 | 一个有 $n$ 个元素的集合，现在要从他的所有子集中取出至少一个集合，使得所选子集的交集的元素个数为 $k$，求方案数。 | ||
| - | ==== 题解 ==== | + | === 题解 === |
| 定义 $f(k)$ 表示所有钦定 $k$ 个元素属于交集(其余元素任意)的方案数之和，于是有 $f(k)={n\choose k}2^{2^{n-k}}$。 | 定义 $f(k)$ 表示所有钦定 $k$ 个元素属于交集(其余元素任意)的方案数之和，于是有 $f(k)={n\choose k}2^{2^{n-k}}$。 | ||
2020-2021/teams/legal_string/jxm2001/二项式反演.1597977103.txt.gz · 最后更改: 2020/08/21 10:31 由 jxm2001
