为什么一直学不会。
前置知识
多项式恒等定理
设 \(F\) 为无限域，\(P,Q\in F[x_1,\cdots,x_m]\)；若 \(P(x)=Q(x)\) 对所有 \(x\in S\subseteq F^m\) 成立，则 \(P=Q\) 在 \(F[x_1,\cdots,x_m]\) 中恒成立。
采用反证法。
设 \(R(x)=P(x)-Q(x)\)，假设 \(R\) 为非零多项式。
设 \(n=\max(\deg P,\deg Q)\)，那么必有 \(\deg R(x)\le n\)。
\(S\) 中一定可以选出 \(n+1\) 个 \(x_i\)，满足 \(x_i\) 两两不同，且 \(\forall x_i,P(x_i)=Q(x_i)\)，也即 \(R(x_i)=0\)。
那么非零多项式 \(R\) 就至少有 \(n+1\) 个不同的根，也即 \(\deg R\ge n+1\)。这与前文所说的“\(\deg R(x)\le n\)”矛盾。
得证。
定义
广义二项式系数
定义广义二项式系数：
\[{n\choose m}=\frac{(n-1)(n-2)\cdots(n-k+1)}{m!},{n\choose 0}=1
\]
其中 \(n\in\mathbb{C},m\in\mathbb{N}\)。
可以发现 \(x\choose n\) 是 \(x\) 的 \(n\) 次多项式。
广义范德蒙德卷积
在广义二项式系数基础上，有广义范德蒙德卷积：
\[\sum\limits_{i=0}^n{a\choose i}{b\choose {n-i}}={{a+b}\choose n}
\]
其中 \(a,b\in\mathbb{C},n\in\mathbb{N}\)。
记左式为 \(P_n(a,b)\)，右式为 \(Q_n(a,b)\)；不难发现两者都是关于 \(a,b\) 的 \(n\) 次多项式。
经典范德蒙德卷积（\(a,b\in\mathbb{N}\)）证明见 link；从这里可以发现，存在无穷多个 \(a,b\)，满足 \(P_n(a,b)=Q_n(a,b)\)。
由多项式恒等定理，\(P_n,Q_n\) 必须恒等；因此可以直接扩展到任意实数。
得证。
广义二项式定理
在上面两个定义的基础上，得到广义二项式定理：
\[(a+b)^n=\sum\limits_{i=0}^{\infty}{n\choose i}a^ib^{n-i}
\]
形式幂级数通常只处理一个变量的整数次幂，因此下面只证明上式在 \(a=1,b=x\) 时的特例，也即：
\[(1+x)^n=\sum\limits_{i=0}^{\infty}{n\choose i}x^i
\]
设右式为 \(A_n(x)\)，那么我们的命题等价于：
\[A_n(x)A_m(x)=A_{n+m}(x)
\]
展开左式，得到：
\[A_n(x)A_m(x)=\sum\limits_{i=0}^{\infty}\Bigg(\sum\limits_{j=0}^i{n\choose j}{m\choose{i-j}}\Bigg)x^i
\]
展开右式，得到：
\[A_{n+m}(x)=\sum\limits_{i=0}^{\infty}{n+m\choose i}x^i
\]
那么命题改写为：
\[\begin{align*}
\sum\limits_{i=0}^{\infty}\Bigg(\sum\limits_{j=0}^i{n\choose j}{m\choose{i-j}}\Bigg)x^i&=\sum\limits_{i=0}^{\infty}{n+m\choose i}x^i\\
\sum\limits_{j=0}^i{n\choose j}{m\choose{i-j}}&={n+m\choose i}
\end{align*}
\]
这就是一个广义范德蒙德卷积的形式，所以得证。
应用
有一个核心性质：设形式幂级数 \(A=ax^n\) 表示达成状态 \(n\)（例如选 \(n\) 个物品或某变量取值为 \(n\)）的方案数为 \(a\)，\(B=bx^m\) 同理；那么 \(C=A\cdot B=abx^{n+m}\) 恰好表示达成状态 \((n+m)\) 的方案数为 \(ab\)。
这一性质是利用生成函数计数的重要基础。
例 \(1\)
求 \(\sum\limits_{i=1}^k v_i=n\) 的正整数解数量。
由插板法（link），这一问题的答案即为 \({n-1}\choose{k-1}\)。
考虑从生成函数视角得出同样结论。构造一个生成函数 \(f(x)\) 使得 \(v_i=m\) 时的贡献为 \([x^m]f(x)\)，则有：
\[f(x)=\sum\limits_{i=1}^{\infty}x^i
\]
每一项的系数都为 \(1\)，表示 \(x\) 的每一种取值的贡献都为 \(1\)。注意没有 \(x^0\)，因为 \(v\) 不能取 \(0\)。
这是单个变量的生成函数。推一下：
\[\begin{align*}
f(x)&=x+x^2+x^3+\cdots\\
xf(x)&=x^2+x^3+x^4+\cdots\\
xf(x)-f(x)&=(x^2+x^3+x^4+\cdots)-(x+x^2+x^3+\cdots)\\
(x-1)f(x)&=-x\\
f(x)&=\frac{x}{1-x}
\end{align*}
\]
我知道这是等比数列求和的惯用手段但就是想凑点字数。
上述推导要求 \(|x|<1\)，但我们只是想要得到结论，并不关心 \(x\) 的值，所以不用管这个要求。（利用形式幂级数环亦可证明）
于是我们得到了 \(f(x)\) 的封闭形式。
每个变量互相独立，因此整个左式的生成函数 \(g(x)\) 是各个变量生成函数之积，即：
\[g(x)=f(x)^k=\frac{x^k}{(1-x)^k}
\]
考虑如何求答案，也即 \([x^n]g(x)\)。
由广义二项式定理，有：
\[(1-x)^{-k}=\sum\limits_{i=0}^{\infty}{{-k}\choose i}(-x)^i
\]
注意到：
\[\begin{align*}
{{-k}\choose i}&=\frac{(-k)(-k-1)\cdots(-k-i+1)}{i!}\\
&=(-1)^i\cdot\frac{k(k+1)\cdots(k+i-1)}{i!}\\
&=(-1)^i\cdot{{k+i-1}\choose i}
\end{align*}
\]
回代：
\[\begin{align*}
(1-x)^{-k}&=\sum\limits_{i=0}^{\infty}(-1)^i\cdot{{k+i-1}\choose i}(-x)^i\\
&=\sum\limits_{i=0}^{\infty}(-1)^i\cdot{{k+i-1}\choose i}(-1)^ix^i\\
&=\sum\limits_{i=0}^{\infty}{{k+i-1}\choose i}
\end{align*}
\]
再回代：
\[\begin{align*}
g(x)&=\frac{x^k}{(1-x)^k}\\
&=x^k\cdot (1-x)^{-k}\\
&=x^k\cdot \sum\limits_{i=0}^{\infty}{{k+i-1}\choose i}x^i\\
&=\sum\limits_{i=0}^{\infty}{{k+i-1}\choose i}x^{i+k}
\end{align*}
\]
对于 \(x^n\)，对应有 \(i+k=n\)，即 \(i=n-k\)，回代得到 \([x^n]g(x)\):
\[\begin{align*}
[x^n]g(x)&={{k+i-1}\choose i}\\
&={{k+(n-k)-1}\choose{n-k}}\\
&={{n-1}\choose n-k}\\
&={{n-1}\choose k-1}
\end{align*}
\]
也就是说，答案即为：
\[{{n-1}\choose k-1}
\]
做完了。好像不如插板法？
