配套视频：
https://www.bilibili.com/video/BV1T5411a7LJ

加法原理

完成一件事情有$n$类方法，每类方法分别有$a_1…a_n$种方法

那么完成这件事情的方法总数为

$$ \sum_{i=1}^n a_i $$

乘法原理

如果完成一件事情有$n$个步骤，每个步骤有若干种方法分别$a_1…a_n$

那么完成这件事情的方法总数为$a_1\times a_2…\times a_n$

排列数

从$n$个不同元素中取出$m(m <=n)$个元素的所有排列的个数，叫做从$n$个不同元素中取出$m$个元素的排列数，⽤符号$A_n^m$表示
$$ A_n^m=n(n-1)(n-2)(n-3)(n-4)…(n-m+1)=\frac{n!}{(n-m)!} $$

组合数

从$n$个不同元素中取出$m$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数。⽤符号$C_n^m$或$\binom{n}{m}$来表示
$$ \binom{n}{m}=\frac{n!}{m!(n-m)!} $$

组合恒等式

$$ \begin{aligned} \binom{n}{m}&= \binom{n}{n-m} \\\ \binom{n}{m}&=\frac{n}{m}\binom{n-1}{m-1} \\\ m\binom{n}{m}&=n\binom{n-1}{m-1} \\\ (n-m)\binom{n}{i}&=n\binom{n-1}{m} \\\ \binom{n}{m}&=\binom{n-1}{m-1}+\binom{n-1}{m} \end{aligned} $$

组合数的求法（组合恒等递推$O(nm)$求组合数）

for(int i=0;i<=n;i++){   
    c[i][j]=1;   
    for(int j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1]; 
} 

组合数求法（乘法逆元$O(n)$求组合数）

intC(int n,int m){return n<m?0:(longlong)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}
fac[0]=invfac[0]=invfac[1]=1;
for(int i=1;i<=n;i++)fac[i]=(longlong)fac[i-1]*i%mod;
for(int i=2;i<=n;i++)invfac[i]=(longlong)(mod-mod/i)*invfac[mod%i]%mod;
for(int i=2;i<=n;i++)invfac[i]=(longlong)invfac[i-1]*invfac[i]%mod;

二项式系数与二项式反演

杨辉三角

$$ \begin{aligned} &1\\\ &1\ 1\\\ &1\ 2\ 1\\\ &1\ 3\ 3\ 1\\\ &1\ 4\ 6\ 4\ 1 \end{aligned} $$
因为其每个数是左上与右上的数的和，即$f[i][j]=f[i-1][j]+f[i-1][j-1]$且有组合恒等$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$，且$\binom{0}{0}=f[0][0]=1$
因此杨辉三角第$i$行$j$个数即为$\binom{i}{j}$

$(x+1)^n$的系数

观察下面的等式与杨辉三角的关系:
$$ \begin{aligned} &(x+1)^0=1\\\ &(x+1)^1=x+1\\\ &(x+1)^2=x^2+2x+1\\\ &(x+1)^3=x^3+3x^2+3x+1\\\ &(x+1)^4=x^4+4x^3+6x^2+4x+1 \end{aligned} $$
我们发现系数的分布极其地像杨辉三角。
考虑组合意义：

有$n$个互不相同的球，每个我们可以选或者不选，求选出$k$个球的方案数。

$(x+1)^n$相当于是$n$个二项式$(x+1)$的乘积，如果我们在这$n$个等式中每次都可以选择$x$或$1$相乘,我们最少可以选$0$个$x$，最多可以选$n$个$x$。

那么有:

$$ (1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i $$

那么推广到$(a+b)^n$的情况，如果$a$选了$i$个，那么$b$必然选了$n-i$个，那么有:

$$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}(n≥0) $$

从式子的推导同样可以得到：
我们已经有$(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i$。
令$x=\frac{a}{b}$有
$$ (\frac{a}{b}+1)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{(-i)} $$
两边同时乘$b^n$
$$ (a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i} $$

特殊恒等

$$ \begin{aligned} a=1,b=1 \\\ \sum_{i=0}^n\binom{n}{i}=2^n \end{aligned} $$

$$ \begin{aligned} a=1,b=-1 \\\ \sum_{i=0}^n\binom{n}{i}(-1)^i=0 \end{aligned} $$

其中奇数项的和等于偶数项的和

二项式系数的应用与和式简单处理

化简:$\sum_{i=0}^n\binom{n}{i}i$

解：
$$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}i \ &=\sum_{i=0}^n\frac{n}{i}\binom{n-1}{i-1}i\\\ &=n\times \sum_{i=0}^{n-1}\binom{n}{i}\\\ &=n\times2^{n-1} \end{aligned} $$

化简$\sum_{i=0}^n\sum_{j=0}^i\binom{n}{j}$

（交换求和顺序）

解：
$$ \begin{aligned} \sum_{i=0}^{n} \sum_{j=0}^{i}\left(\begin{array}{l} n \\\ j \end{array}\right) &=\sum_{j=0}^{n}\left(\begin{array}{c} n \\\ j \end{array}\right) \sum_{i=j}^{n} 1 \\\ &=\sum_{j=0}^{n}\left(\begin{array}{c} n \\\ j \end{array}\right)(n-j+1) \\\ &=(n+1) \sum_{j=0}^{n}\left(\begin{array}{c} n \\\ j \end{array}\right)-\sum_{j=0}^{n} j\left(\begin{array}{c} n \\ j \end{array}\right) \\\ &=(n+1) 2^{n}-n 2^{n-1} \\\ &=(n+2) 2^{n-1} \end{aligned} $$

化简：$\sum_{i=k}^n\binom{i}{k}$

解：将其看成$\sum_{i=k}^n(1+x)^i$的$k$次幂系数和
$$ \begin{aligned} \sum_{i=k}^n(1+x)^i&=(1+x)^k\times\frac{1-(1+x)^{n-k+1}}{1-(1+x)}\\\ &=\frac{(1+x)^{n+1}-(1+x)^k}{x}\\\ &=\frac{\sum_{i=0}^{n+1}\binom{n+1}{i}x^i-\sum_{j=0}^k\binom{k}{j}x^j}{x}\\\ &=\frac{x(\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1})}{x}\\\ &=\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1} \end{aligned} $$
因为$j-1$不可能等于$k$，因此即为$\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}$的$k$次项的系数，$i-1=k$时，二项式系数为$\binom{n+1}{k+1}$
（也可以把$\binom{k}{k}$看成$\binom{k+1}{k+1}$归纳递推）

二项式反演

而对于两个数列有

$$ f_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_i $$

变形有

$$ f_n=\sum_{i=0}^{n}\binom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i $$

容斥原理

$$ \left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{T \subseteq\{1,2,3, \ldots, n\}}(-1)^{|T|-1}\left|\bigcap_{j \in T} S_{j}\right| $$

即对于若干个集合的并集的元素个数，相当于$i(1<=i<=n)$个集合的交集的个数的乘上容斥系数（若交集个数为奇数则为-1，若交集个数为偶数则为+1）和

证明：要证明容斥原理等价于我们要证明每个元素对答案的贡献都为1.

设元素$p$在$k$个元素出现过，那么$p$对答案的贡献为

$$ \sum_{i=1}^k(-1)^{(k-1)}\binom{k}{i}=0-(-1)^{(-1)}\times\binom{k}{0}=1 $$

集合反演

对于函数$f(S),g(S)$有

$$ f(S)=\sum_{T \subseteq S} g(T) \Leftrightarrow g(S)=\sum_{T \subseteq S}(-1)^{|S|-|T|} f(T) $$

证明

$$ \begin{aligned} & \sum_{T \subseteq S}(-1)^{|S|-|T|} f(T) \\\ =& \sum_{T \subseteq S}(-1)^{|S|-|T|} \sum_{Q \in T} g(Q) \\\ =& \sum_{Q \subseteq S} g(Q) \sum_{Q \subseteq T \subseteq S}(-1)^{|S|-|T|} \\\ =& \sum_{Q \subseteq S} g(Q) \sum_{T \subseteq(S \backslash Q)}(-1)^{|S \backslash Q|-|T|} \\\ =& \sum_{Q \subseteq S} g(Q) h(S \backslash Q) \end{aligned} $$

其中

$$ \begin{aligned} h(S) &=\sum_{T \subseteq S}(-1)^{|S|-|T|} \\\ &=\sum_{i=0}^{|S|}\left(\begin{array}{c} |S| \\\ i \end{array}\right)(-1)^{|S|-i} \\\ &=(1-1)^{|S|} \\\ &=[S=\varnothing] \end{aligned} $$

有

$$ \sum_{Q \subseteq S} g(Q)[(S \backslash Q)=\varnothing]=g(S) $$

容斥原理与错排问题通项公式

$n$封信和信箱⼀⼀对应，求把每封信都装错信箱的⽅案数。

对于错排问题，我们有一个递推式，即$D[n]=(n-1)\times (D[n-1]+D[n-2])$

我们可以得知其中全部装错信箱的方案=总方案$-$没有把所有信都装错的方案

即总方案$-$不满足要求的方案

而显然，对于总方案即$n$的全排列，为$n!$

而什么样的方案是不满足的？

我们把我们的信编号为$1,2,3,4,5....n$

其对应的邮箱编号为$1,2,3,4,5....n$

如果存在一个$i$，其对应的邮箱编号是$i$，那么不管其他的信件对应的邮箱的编号是几，这种方案一定不合法。

我们设$A_i$为第$i$封信送进所对应的$i$号邮箱的方案集合。

我们有$1$个邮箱所放的信件是确定的，而其他$n-1$个邮箱放什么信我们都不关心

而对于除了第$i$个邮箱的其他邮箱，每一次分别可以从$(n-1),(n-2),(n-3)…1$封信中挑选一个进去，即有$n-1$步，第$k$步有$(n-k)$种选法,那么其选择的方案总和为$(n-1)!$

即对于任意一个$i$，都有$|A_i|=(n-1)!$

而我们把所有信都装错的方案数就等价于

$$ n!- \left|\bigcup_{i=1}^{n} A_{i}\right| $$

那么我们只需要用容斥原理求出$A_i$的并集，即可容易地计算出答案

而要进行容斥，就需要知道
$$ \left|\bigcap_{j \in T \subseteq\{1,2,3, \ldots, n\}} A_{j}\right| $$
考虑最简单的情况
$$ \left|A_i\bigcap A_j\right| $$
$A_i$为第$i$个信箱装信$i$的方案
$A_j$为第$j$个信箱装信$j$的方案
因此$A_i \bigcap A_j$就等价于第$i$个信箱装信$i$且第$j$个信箱装信$j$的方案，其方案数为$(n-2)!$同理可推广到若干个集合的情况，即$k$个$A$集合的交的大小为$(n-k)!$

而我们要从$A_1,A_2,A_3,…,A_n$这些集合中，选若干个集合相交，选$k$个集合相交的个数为,则一共有$\binom{n}{k}$种选择方案。那么则有

$$ \begin{aligned} \left|\bigcup_{i=1}^{n} A_{i}\right| = \sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)! \end{aligned} $$

那么

$$ \begin{aligned} D[n]&=n!-\sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)! \\\ &=n!-\sum_{i=1}^n(-1)^{(i-1)}\frac{n!}{i!} \\\ \end{aligned} $$

[HAOI2008]硬币购物

共有四种硬币，其面值分别为$c_1,c_2,c_3,c_4$

$n$次询问，每次给定每种硬币的个数$D_i$和付款金额$S$，问共有多少种付款方式

$n≤10^3,S≤10^5$

暴力做法

我们可以把问题看作做$n$次多重背包，用单调队列优化，最优的复杂度为$O(n4s)$在这里不详细讨论

完全背包+容斥

对于每次询问，相当于给定四个限制，第$i$个限制即只能至多使用$i$个硬币支付。类似于错排，满足限制的方案数=全部方案数-不满足的方案数

而对于全部的方案数，相当于做体积为$S$的完全背包，而$S$至多为$10^5$，因此我们可以$O(4S)$预处理所有$S$。

而对于不满足条件的方案数

类似于错排，若不满足其中一个限制条件，一定是非法的，我们可以设$A_i$为第$i$种硬币不满足限制的方案集合。

那么不满足条件的方案数即
$$ \left|\bigcup_{i=1}^4 A_i\right| $$
而对于$|A_i|$，我们当前一共要支付$S$个硬币，而对于第$i$种只能支付$D_i$个，那么我们如果先把$D_i+1$个硬币付完剩下的支付方案（即从四种硬币中支付$S-C_i(D_i+1)$的金额）是一定不合法的，因为第$i$个硬币至少需要选零个，而如果选$0$个，最终还是多付了一个。

因此，第$|A_i|=F[S-C_i(D_i+1)]$

因为我们要求集合的并，因此，我们需要考虑容斥，而考虑容斥我们就需要求出集合的交

我们考虑任意最简单的情况：两个集合的交
$$ \left|A_i \bigcap\ A_j\right| $$
我们从定义出发，$A_i$为第$i$种硬币不满足限制的方案集合，而$A_j$为第$j$种硬币不满足限制的方案集合。

而显然，同时满足$i$种硬币不满足限制与$j$种硬币不满足限制这样的性质的集合，为它们的交。

同样地，我们可以把他们两个的$D_i+1$都先支付出去，那么则有
$$ \left|A_i \bigcap\ A_j\right|=F[S-C_i(D_i+1)-C_j(D_j+1)] $$

那么
$$ \begin{aligned} ans&=F[s]-\left|\bigcup_{i=1}^4 A_i\right| \\\ &=F[s]-\sum_{T \subseteq\{1,2,3,4\}} -1^{|T|-1}\left|\bigcap_{j \in T } A_{j}\right| \\\ &=F[s]-(-1)^{|T|-1}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)]\\\ &=F[s]+(-1)^{|T|}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)] \end{aligned} $$
那么我们可以状压枚举$T$算出答案。

总的复杂度为$O(4S+16n)$
代码：

#include <iostream>

using namespace std;

const int maxn = 10;

int c[maxn],d[maxn];

long long f[100010];

int main(){
    int n;
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i++){
        for (int j = c[i]; j <= 100010; j++){
            f[j] += f[j - c[i]];
        }
    }
    while(n--){
        int s;
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        long long ans = f[s];
        for (int i = 0; i < 1 << 4; i++){
            long long sum = 0,cnt = 0;
            for (int j = 0; j < 4; j++){
                if (i >> j & 1){ 
                    sum += c[j + 1] * (d[j + 1] + 1);
                    cnt++;
                }
            }
            //cout << sum << endl;
            long long t = s - sum;
            if (cnt % 2 == 0 && t >= 0 && sum != 0) ans += f[s - sum];
            else if (t >= 0 && sum != 0) ans -= f[s - sum];
        }
        cout << ans << endl;
    }
    //system("PAUSE");
    return 0;
}

特殊处理方法

捆绑法

如果要求若干物品相邻，则可以将它们作为一个整体来进行计数。
$ABCDE$五个人要排队，$A$和$B$要相邻，$C$和$D$要相邻，求有多少种排列方法。

把$AB$看作一个整体，$CD$看成一个整体。再计算$AB$与$CD$内部的相对顺序。

方案数:$3!\times2!\times2!=24$。

插空法

如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入其中，进行计数。

$ABCDEFG$七个人要排队,$ABC$三个人两两不相邻，求方案数。

先将$DEFG$四个人排好，中间有$5$个空位（包括其两侧的）,$ABC$只能插入到空位中。

方案数：$4!\times A_5^3=1440$

隔板法

把个相同的苹果分给$k$个人，要求每个人至少分到一个，求方案数。

把$n$个苹果排成一排，在其中插入$k-1$块隔板，表示$k$个人分到的部分。

插隔板的方法与分苹果的方案是一一对应的，那么方案数为$\binom{n-1}{k-1}$

那么如果有人可以分到$0$个苹果呢？

我们给每个人多分一个苹果，使得每个人至少分配到一个苹果，在分配完之后再将每个人的苹果拿走一个。

那么方案数为$\binom{n+k-1}{k-1}$

隔板法与不定方程整数解问题

求不定方程$x_1+x_2+x_3+x_4+....+x_k=n$的解的个数，要求$x_i>d_i$

设$y_i=x_i-d_i>0$

那么有$y_1+y_2+y_3+y_4+....+y_k=n-(d_1+d_2+d_3+d_4+....+d_k)$

那么原问题就等价于“分苹果”的问题，即有$n-(d_1+d_2+d_3+d_4+....+d_k)$个苹果，分给$k$个人，要求每个人分到的苹果都大于$0$
那么方案数为。
$$ \binom{n-(d_1+d_2+d_3+d_4+....+d_k)-1}{k-1} $$

多重集的排列数与组合数

设$S=${$n_1a_1,n_2a_2,…,n_ka_k $}是由$n_1$个$a_1$，$n_2$个$a_2$，$n_k$个$a_k$组成的多重集。

多重集排列数

多重集$S$的全排列，不考虑相同的元素，其全排列个数为$(\sum_{i=1}^kn_i)!$，但是因为存在若干个相同的元素，因此要把相同元素的贡献给除掉。

对于每种排列的每个$a_{i,j}$，我们都可以从$n_i$个$a_i$中挑选任意一个，其对答案的贡献满足乘法原理为$n_i!$

因此方案数为
$$ \frac{(\sum_{i=1}^kn_i)!}{\prod_{i=0}^kn_i!} $$

多重集的组合数

求从多重集$S$中取$r$个元素的组合数的。

不考虑$n_i$个元素的限制，即从多重集$S’=${$∞a_1,∞a_2,…,∞a_k$}中取$r$个元素的组合数。

我们设$a_i$取$x_i$个，那么原问题就等价于不定方程$\sum_{i=1}^kx_i=r\ (x≥0)$的解的个数。

等价于一共有$r$个苹果，分给$k$个人，可以有人拿$0$个苹果的方案数。

用隔板法计算，其方案为$\binom{r+k-1}{k-1}$

我们考虑第每个$a_i$的$n_i$的限制。

设不满足第$i$个限制的方案集合为$F_i$

那么答案即为$\binom{r+k-1}{k-1}-\left |\bigcup_{i=1}^nF_i \right |$

而$|\left |\bigcup_{i=1}^nF_i \right |$则可以用容斥原理计算。

类似[HAOI2008]硬币购物，我们先把$n_i+1$个拿出来，那么其余的我们不用管他，不管怎么安排，肯定都是非法方案。

显然有$\left|F_i\bigcap F_j \right|=\binom{r+k-1-(n_i+n_j+2)}{k-1}$

那么答案为
$$ \binom{r+k-1}{k-1}-\sum_{T \subseteq\{1,2,…,k\}}(-1)^{|T|-1}\binom{k+r-1-(\sum_{j \in T}n_j+|T|)}{k-1} $$

下降阶乘幂与上升阶乘幂

下降阶乘幂：$x^{\underline{m}}=n(n-1)(n-2)(n-3)…(n-m+1)$（$m$个因子）读作$x$直降$m$次。

上升阶乘幂：$x^{\overline{m}}=n(n+1)(n+2)(n+2)…(n+m-1)$($m$个因子) 读作$x$直升$m$次

显然有$n!=n^{\underline{n}}=1^{\overline{n}}$

负数上指标组合数

我们有$\binom{n}{k}=0\ (k<0)$即当组合数下指标为负数时，值为$0$

那么上指标为负数的时候呢？是否也为$0$呢？显然不是的

例如$\binom{0}{0}=\binom{-1}{-1}+\binom{-1}{0}=1$，其中$\binom{-1}{-1}=0$，那么显然有$\binom{-1}{0}=1$

那么我们应该如何计算出负数上指标的组合数呢？

有
$$ \binom{n}{m}=(-1)^m\binom{m-n-1}{m} $$
上述等式过程被称为反转上指标。

证明：
$$ \begin{aligned} \binom{n}{m}&=\frac{n!}{m!(n-m)!}\\\ &=\frac{n^{\underline{m}}}{m!}\\\ &=\frac{n(n-1)(n-2)…(n-m+1)}{m!}\\\ &=\frac{-1^m(-n)(1-n)(2-n)…(m-n-1)}{m!}\\\ &=-1^m\frac{(m-n-1)^{\underline{m}}}{m!}\\\ &=(-1)^m\binom{m-n-1}{m} \end{aligned} $$

广义二项式定理

在上面，我们已经得到了一般性二项式定理
$$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}(n≥0) $$
那么如果$n$为负数呢？这时候就需要广义二项式定理来处理了
$$ (a+b)^n=\sum_{k}\binom{n}{i}a^ib^{n-i} $$
（$n$可以为任意实数或复数，只需满足$|a/b|<1$确保和式绝对收敛）

证明可以利用泰勒级数一基复变量理论因为作者能力不足所以不展开叙述。

生成函数(母函数)

通常，我们用一个辅助变量$z$的幂级数来表示一个无限序列$\left\langle a_0,a_1,a_2,a_3…\right\rangle$的生成函数
$$ A(z)=\sum_{i=0}^{n}a_iz^i $$

卷积

我们定义$A(z)$为无限序列$\left\langle a_0,a_1,a_2,a_3…\right\rangle$的生成函数，$B(z)$为无限序列$\left\langle b_0,b_1,b_2,b_3…\right\rangle$的生成函数。
那么有$A(z)\times B(z)=a_0b_0+(a_0b_1+a_1b_0)z^1+(a_0b_2+a_1b_1+a_2b_0)z^2+(a_0b^3+a_1b^2+a_2b_1+a_3b_0)z^3$

用$\left[z^n\right]A(z)B(z)$表示$A(z)B(z)$中$z^n$的系数

有
$$ \left[z^n\right]A(z)B(z)=\sum_{i=0}^{n}a_ib^{n-i} $$
令$c_n=\left[z^n\right]A(z)B(z)=\sum_{i=0}^{n}a_ib^{n-i}$

我们称$\left \langle c_n \right \rangle$为序列$\left \langle a_n\right\rangle$与$\left \langle b_n \right \rangle$的卷积

生成函数与卷积对于求证组合恒等有着至关重要的作用。

由二项式定理可知$\left \langle \binom{n}{0},\binom{n}{1},\binom{n}{2}… \right\rangle$的生成函数为$A(z)=(1+z)^n$

同理，$\left \langle \binom{s}{0},\binom{s}{1},\binom{s}{2}… \right\rangle$的生成函数为$B(z)=(1+z)^s$

$$ A(z)B(z)=(1+z)^{s+n} $$

对于卷积序列$\left \langle c_m \right \rangle$有
$$ c_m=\sum_{i=0}^m\binom{n}{i}\binom{s}{m-i} $$
而对于
$$ \left[z^m\right]A(z)B(z) $$
因为$A(z)B(z)=(1+z)^{s+n}$根据二项式定理有
$$ \left[z^m\right]A(z)B(z)=\binom{s+n}{m} $$
那么有恒等式
$$ \sum_{i=0}^m\binom{n}{i}\binom{s}{m-i}=\binom{s+n}{m} $$
上述即为范德蒙德卷积。

我们来看另一个序列

$$ \left \langle (-1)^n\binom{r}{n}\right\rangle=\left\langle\binom{r}{0},-\binom{r}{1},\binom{r}{2},…\right\rangle $$

其生成函数
$$ G(z)=\sum_{k}\binom{n}{k}(-1)^kz^k=\sum_k(-z)^k=(1-z)^r $$
而有
$$ (1+z)^r(1-z)^r=(1-z^2)^r $$
让两边$z^n$相等
$$ \sum_{i=0}^{n}\binom{r}{i}\binom{r}{n-i}(-1)^i=(-1)^{n/2}\binom{r}{n/2} $$
（$n$为偶数时，当$n$为奇数时值为0）

特殊恒等式（重要）

$$ \frac{1}{(1-z)^{n+1}}=\sum_{k≥0}\binom{k+n}{k}z^k $$
（$n≥0$）
$$ \frac{z^n}{(1-z)^{n+1}}=\sum_{k≥0}\binom{n}{k}z^k $$

（$n≥0$）

证明：

对于等式一可以通过反转上指数进行处理

等式一:
$$ \begin{aligned} \frac{1}{(1-z)^{n+1}}&=(1-z)^{-n-1}\\\ &=\sum_{k}\binom{-n-1}{k}(-z)^k\\\ &=\sum_{k≥0}\binom{k-(-n-1)-1}{k}z^k(-1)^{2^k}\\\ &=\sum_{k≥0}\binom{k+n}{k}z^k\\\ &=\sum_{k≥0}\binom{k+n}{n}z^k \end{aligned} $$
对于等式二：
$$ \frac{z^n}{(1-z)^{n+1}}=\sum_{k≥0}\binom{k+n}{n}z^{n+k} $$
令$k’=n+k$有
$$ \frac{z^n}{(1-z)^{n+1}}=\sum_{k’≥0}\binom{k’}{n}z^{k’} $$

当$n=0$时有
$$ \frac{1}{1-z}=1+z+z^2+z^3+z^4+....=\sum_{k≥0}z^k $$
序列$\left\langle 1,1,1,1,....\right\rangle$的生成函数，也被称为几何级数。

与任一序列$\left\langle a_n\right\rangle$的卷积为

$$ c_n=\sum_{i=0}^na_i $$

$\left\langle c_n\right\rangle$的生成函数即为
$$\frac{A(z)}{1-z}$$
其中$A(z)$为$\left\langle a_n\right\rangle$的生成函数