生成函数即为母函数
设${a_n}$是任一数列，则形式幂级数$A(t)=sum_{i=0}^{∞}a_it^i$叫做数列${a_n}$的常生成函数
引理 1
以$M_k (k= 1, 2, ⋯, n)$表示不定方程 $x_1+ x_2+ x_3+ ⋯+ x_n= r$ 中的未知数 $x_k$ 的可取值所成之集
以 $a_r$ 表示不定方程 $x_1+ x_2+ x_3+ ⋯+ x_n= r$ 满足条件 $x_k∈M_k (k= 1, 2, ⋯, n)$的解的个数
则 $a_r$ 是$A (t) = prod_{k= 1}^n sum _{p ∈M_k}t^p$展开式中 $t^r$ 的系数
引理 2
设m 是任一有理数, 则对形式幂级数$A (t) = 1+ at(a≠0)$有 $(1+ at)^m =sum_{i=0}^{∞}dbinom{m}{i}a^it^i$
特别地有$(1-t)^{-n}=sum_{i=1}^{∞}dbinom{k+i-1}{i}t^i$
关于上式的证明：
$n=1$时换元$k=x^{-1}$，右边取一下数列的极限即可得到左边。然后对左右分别求n阶导数即得证
或者直接泰勒展开大概也可以
定理1
不定方程$x_1+x_2+x_3+...+x_n=r$的非负整数解的个数为$dbinom{n+r-1}{n-1}$
证明：构造函数$A(t)=(t^0+t^1+...)(t^0+t^1+...)...(t^0+t^1+...)$，显然解的个数为$t_r$的系数
$=(t^0+t^1+t^2+...)^n$
设$p=t^0+t^1+t^2+...$，有$p=1+pt$，那么$p=frac{1}{1-t}$
$p^n=(t^0+t^1+t^2+...)^n=(frac{1}{1-t}^n)=sum_{i=0}^{∞}dbinom{n+i-1}{i}t^i$
那么$t_r$的系数即为$dbinom{n+r-1}{r}=dbinom{n+r-1}{n-1}$
定理2
不定方程$x_1+x_2+x_3+...+x_n=r$的正整数解的个数为$dbinom{r-1}{n-1}$
证明：构造函数$A(t)=(t^1+t^2+...)^n$，显然解的个数为$t_r$的系数
设$p=t^1+t^2+...$，有$p=t+tp$，那么$p=frac{t}{1-t}$
$p^n=(t^1+t^2+...)^n=t^nsum_{i=0}^{∞}dbinom{n+i-1}{i}t^i$
其中$t^r$的系数为$dbinom{r-1}{r-n}=dbinom{r-1}{n-1}$
定理3
不定方程$x_1+x_2+x_3+...+x_n=r$满足条件$x_i>=k_i(k_i∈N^*,i=1,2,3...)$的非负整数解的个数为$dbinom{n+r-sum_{i=1}^{n}k_i-1}{n-1}$
证明：我们令$y_i=x_i-k_i$，问题转化为了定理1，套用定理1的公式即可解决
定理4
不定方程$x_1+x_2+x_3+...+x_n=r$满足条件$x_i<=k(i=1,2,3...)$的非负整数解的个数为$dbinom{n+r-1}{n-1}-sum_{j=1}^{n} (-1)^j dbinom{n}{j} dbinom{n+r-jk-1}{n-1}$
证明：在定理3的基础上容斥一下即可，即$ans=$总方案数-一个不满足条件其他任意+两个不满足条件其他任意...当然这个也可以靠生成函数，$A(t)=(t^0+t^1+...t^k)^n$，方案数就是$t^r$的系数
例题1：
不定方程$x_1+x_2+x_3+...+x_n=r$满足条件$x_i<=k$且$x_1+x_n<=k$的非负整数解的个数
构造生成函数$A(t)=(t^0+t^1+...+t^k)^{n-2}((t^0+t^1+...+t^k)^2mod t^{k+1})$，方案数即为$t^r$的系数
进一步化简得到$A(t)=(sum_{i=0}^{k}t_i)^{n-2}(sum_{i=0}^{k}(i+1)x_i)$