组合数学与计数入门学习笔记
RyexAwl
·
2020-07-03 22:12:52
·
个人记录
加法原理
完成一件事情有 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][0]=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 个球的方案数。
那么有:
$$
(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}
[x^k]\sum_{i=k}^n(1+x)^i&=[x^k](1+x)^k\times\frac{1-(1+x)^{n-k+1}}{1-(1+x)}\\
&=[x^k]\frac{(1+x)^{n+1}-(1+x)^k}{x}\\
&=[x^k]\frac{\sum_{i=0}^{n+1}\binom{n+1}{i}x^i-\sum_{j=0}^k\binom{k}{j}x^j}{x}\\
&=[x^k]\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}\\
&=[x^k]\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)
容斥原理与错排问题通项公式
更细致的探讨
对于错排问题，我们有一个递推式，即$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_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≤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) （严格来说应该为O(S+n) ）
代码：
#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;
}
特殊处理方法
捆绑法
如果要求若干物品相邻，则可以将它们作为一个整体来进行计数。
把$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= \left\{n_1a_1,n_2a_2,...,n_ka_k \right\} 是由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'= \left\{∞a_1,∞a_2,...,∞a_k \right\} 中取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}
广义二项式定理
在上面，我们已经得到了一般性二项式定理，(即n≥0 的情况)
(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}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 的生成函数，也被称为几何级数。
注意：上述结论均需满足|z|<1
与任一序列\left\langle a_n\right\rangle 的卷积为
c_n=\sum_{i=0}^na_i
$$\frac{A(z)}{1-z}$$
其中$A(z)$为$\left\langle a_n\right\rangle$的生成函数