Contents
二项式定理
普通二项式定理：
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i
\begin{pmatrix}m\cr 0\end{pmatrix}+\begin{pmatrix}m\cr 1\end{pmatrix}+\cdots+\begin{pmatrix}m\cr m\end{pmatrix}=2^m
多元二项式定理
定义记号：
\binom{n}{n_1,n_2,\cdots,n_t}=\frac{n!}{n_1!n_2!\cdots n_t!}
其中 n_1+n_2+\cdots +n_t=n。
意义：将 n 个元素分为 t 组，使得第 i 组有 n_i 个元素的方案数。
定理内容：
(x_1 + \dots + x_m)^n = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = n}\binom{n}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i}
\sum_{c_i \ge 0,\sum_{i=1}^m c_i = n}\binom{n}{c_1, c_2, \cdots ,c_m}=m^n
广义二项式定理
(x+y)^n=\sum_{k=0}^{\infty}\begin{pmatrix}n\cr k\end{pmatrix}x^{n-k}y^k
栗子：
\begin{aligned}
\frac{1}{(1-x)^k}&=(1-x)^{-k}\cr
&=\sum_{i=0}^{\infty}\begin{pmatrix}-k\cr i\end{pmatrix}(-x)^i\cr
&=\sum_{i=0}^{\infty}(-1)^i\frac{(-k)^{\underline i}}{i!}x^i\cr
&=\sum_{i=0}^{\infty}(-1)^{2i}\frac{(k+i-1)^{\underline i}}{i!}x^i\cr
&=\sum_{i=0}^{\infty}\frac{(k+i-1)^{\underline i}}{i!}x^i\cr
&=\sum_{i=0}^{\infty}\begin{pmatrix}k+i-1\cr i\end{pmatrix}x^i
\end{aligned}
二项式推论
- 由定义导出的递推式：
m\cdot \binom{n}{m}=n\cdot\binom{n-1}{m-1}
- 一行组合数的递推公式：
\begin{pmatrix}k\cr i\end{pmatrix}=\begin{pmatrix}k\cr i-1\end{pmatrix}\times\frac{k-i+1}{i}
- 二项式定理的特殊情况：a=1,b=-1
\sum_{i=0}^{n}(-1)^i\binom{n}{i}=0
\begin{pmatrix}m\cr 0\end{pmatrix}+\begin{pmatrix}m\cr 2\end{pmatrix}+\cdots=\begin{pmatrix}m\cr 1\end{pmatrix}+\begin{pmatrix}m\cr 3\end{pmatrix}+\cdots=2^{m-1}
- 范德蒙德恒等式：
\begin{pmatrix}m+n\cr r\end{pmatrix}=\begin{pmatrix}m\cr 0\end{pmatrix}\cdot\begin{pmatrix}n\cr r\end{pmatrix}+\begin{pmatrix}m\cr 1\end{pmatrix}\cdot\begin{pmatrix}n\cr r-1\end{pmatrix}+\cdots +\begin{pmatrix}m\cr r\end{pmatrix}\cdot\begin{pmatrix}n\cr 0\end{pmatrix}
\begin{pmatrix}m+n\cr n\end{pmatrix}=\begin{pmatrix}m\cr 0\end{pmatrix}\cdot\begin{pmatrix}n\cr 0\end{pmatrix}+\begin{pmatrix}m\cr 1\end{pmatrix}\cdot\begin{pmatrix}n\cr 1\end{pmatrix}+\cdots +\begin{pmatrix}m\cr m\end{pmatrix}\cdot\begin{pmatrix}n\cr m\end{pmatrix}
- 上面的特殊情况，取 n=m：
\sum_{i=0}^{n}\begin{pmatrix}n\cr i\end{pmatrix}^2=\begin{pmatrix}2n\cr n\end{pmatrix}
- 带权和（对生成函数求导可得）：
\sum_{i=1}^{n}\begin{pmatrix}n\cr i\end{pmatrix}\cdot i=n\cdot 2^{n-1}
\sum_{i=1}^{n}\begin{pmatrix}n\cr i\end{pmatrix}\cdot i^2=n(n+1)\cdot 2^{n-1}
- 组合数相乘：
\begin{pmatrix}m\cr n\end{pmatrix}\cdot \begin{pmatrix}n\cr r\end{pmatrix}=\begin{pmatrix}m\cr r\end{pmatrix}\cdot\begin{pmatrix}m-r\cr n-r\end{pmatrix}
- 斐波那契数列相关：
\sum_{i=0}^{n}\binom{n-i}{i}=F_{n+1}
- 组合分析：
\sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}
多重集的排列组合
多重集的排列数
多重集是指包含重复元素的广义集合。设 S=\begin{Bmatrix} n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k \end{Bmatrix} 表示由 n_1 个 a_1， n_2 个 a_2，\cdots，n_k 个 a_k 组成的多重集。
多重集的排列数（多重组合数）：
\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^{k}{n_i}!}
可见，
\binom{n}{m}=\binom{n}{m,n-m}
多重集的组合数
简化问题：
对于整数 r(r\le n_i)，从 S 中选择 r 个元素组成一个多重集的方案数。
解法：问题可以转化为求 x_1+x_2+\cdots +x_k=r 的非负整数解的个数。考虑插板法，r 个球和 k-1 个板一共 r+k-1 个位置，分配 k-1 个给板，因此答案为：
\binom{r+k-1}{k-1}
一般问题：
对于整数 r，从 S 中选择 r 个元素组成一个多重集的方案数。即：
\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^{k}x_i=r
解法：
设 S_i 为满足条件的集合。\overline{S_i} 表示存在 x_i\ge n_i + 1 的集合（即不满足条件的集合）。则：
Ans=\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|
考虑容斥定理：
\left|\bigcup_{i=1}^k\overline{S_i}\right|=\sum_{i}\left|\overline{S_i}\right|-\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right|+\cdots +{(-1)}^k\left|\bigcap_{i=1}^k\overline{S_i}\right|
计算 \sum_{i}\left|\overline{S_i}\right| 时，我们考虑先拿出 n_i + 1 个 a_i，然后就变成了简化问题。后面的同理。因此上式可化为：
\sum_{i}\binom{r+k-1-(n_i+1)}{k-1}-\sum_{i,j}\binom{r+k-1-(n_i+1)-(n_j+1)}{k-1}+\cdots
因此：
Ans=\sum_{p=0}^{k}(-1)^p\sum_{A}\binom{r+k-1-p-\sum{n_A}}{k-1}
我们可以考虑枚举全部子集来计算。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
const int N = 25;
ll n, s, f[N];
int inv[N];
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % P) {
if (b & 1) ret = 1LL * ret * a % P;
}
return ret;
}
void init() {
for (int i = 1; i <= n; i++) {
inv[i] = ksm(i, P - 2);
}
}
int C(ll n, ll m) {
if (n < m || n < 0 || m < 0) return 0;
ll ret = 1;
for (ll i = n - m + 1; i <= n; i++) {
(ret *= (i % P)) %= P;
}
for (ll i = 1; i <= m; i++) {
(ret *= inv[i]) %= P;
}
return (int)ret;
}
int solve() {
ll ret = C(n + s - 1, n - 1);
for (int i = 1; i < (1 << n); i++) {
ll all = n + s - 1, p = __builtin_popcount(i);
for (int j = 0; j < n; j++) {
if ((1 << j) & i) all -= f[j] + 1;
}
if (p & 1) (ret += P - C(all, n - 1)) %= P;
else (ret += C(all, n - 1)) %= P;
}
return (int)ret;
}
int main(int argc, const char * argv[]) {
scanf("%lld%lld", &n, &s);
init();
for (int i = 0; i < n; i++) {
scanf("%lld", &f[i]);
}
printf("%d\n", solve());
return 0;
}
不相邻的组合数
问题1：从 n 个球中选出 r 个球，要求这 r 个球互不相邻，有多少种取法？
解：从 n-r+1 个球中任意选取 r 个球；剩下的 r-1 个球插空在这 r 个球中间。共：\binom{n-r+1}{r} 种。
问题2：从围成一圈的 n 个球中选出互不相邻的 r 个球有多少种不同的选法？
解：对球进行编号 1 至 n，对于任何可能的组合，都只有两种情况：包含 1 号球的和不包含 1 球。
包含1号球：首先选出 1 号球，然后需要从 3 号球至 n-1 号球取出 r-1 个互不相邻的球，根据上面的结论，我们可以得到组合数为 \binom{n-3-(r-1)+1}{r-1}=\binom{n-r-1}{r-1}；不包含1号球：我们需要从 2 号球至 n 号球取出 r 个互不相邻的球，其组合数为 \binom{n-1-r+1}{r}=\binom{n-r}{r}。综上，答案为：
\binom{n-r-1}{r-1}+\binom{n-r}{r}=\binom{n-r}{r}\cdot \frac{n}{n-r}