记号 1 设 \(f(x)\) 是关于变元 \(x\) 的多项式, 则对正整数 \(n\), 记 \(\left[x^n\right] f:=f(x)\) 的 \(x^n\) 项系数.
例如, 若 $f(x)=-3+5 x+7 x^3$, 则 $\left[x^0\right] f=-3,\left[x^1\right] f=5,\left[x^2\right] f=0$, $\left[x^3\right] f=7$. 一般地, 由微积分中众所周知的泰勒公式可知, $$ \left[x^n\right] f=\frac{f^{(n)}(0)}{n!}, $$其中 \(f^{(n)}\) 为 \(f\) 的 \(n\) 阶导函数.
性质 2 设 \(f_1, \ldots, f_n\) 都是关于变元 \(x\) 的多项式, 记 \(f:=f_1 f_2 \cdots f_n\), 则对任意 \(k \geq 0\),
\[\left[x^k\right] f=\sum_{\substack{i_1+\ldots+i_n=k \\ i_j \geq 0, \forall j=1, \ldots, n}} \prod_{j=1}^n\left[x^{i_j}\right] f_j . \]证明： 直接用多项式乘法展开, 然后合并同类项即可, 这是显然的.
推论 3 (二项式定理). 对于正整数 \(n\), 成立
\[(1+x)^n=\sum_{k=0}^n\binom{n}{k} x^k . \]证明： 此定理众所周知, 但这里还是要象征性证明一下. 在 性质 2 中, 取 \(f_1=\) \(f_2=\cdots=f_n=1+x, f:=f_1 f_2 \cdots f_n=(1+x)^n\), 从而对每个 \(k \geq 0\),
\[\begin{aligned} {\left[x^k\right] f } & =\sum_{\substack{i_1+\ldots+i_n=k \\ i_j \geq 0, \forall j=1, \ldots, n}}\prod_{j=1}^n\left[x^{i_j}\right](1+x)=\sum_{\substack{i_1+\ldots+i_n=k \\ i_j=0,1}} 1 \\ & =\#\left\{\left(i_1, i_2, \ldots, i_n\right) \mid i_1+\cdots+i_n=k, i_j=0,1\right\} \\ & =\binom{n}{k} . \end{aligned} \]注意最后一个等号利用了1.1.3.
推论 4 若 \(I_1, I_2, \ldots, I_n\) 都是 \(\mathbb{Z}_{\geq 0}\) 的有限子集, 记多项式 \(f_j(x)=\sum_{i \in I_j} x^i\), \(j=1, \ldots, n\), 则关于未知数 \(x_1, \ldots, x_n\) 的不定方程
\[\left\{\begin{array}{l} x_1+x_2+\cdots+x_n=k \\ x_j \in I_j, \quad \forall j=1,2, \ldots, n \end{array}\right. \]的解的个数为 \(\left[x^k\right]\left(f_1 f_2 \cdots f_n\right)\).
证明：思考一下推论 3 是如何与1.1.3联系起来的，想明白以后则推论 4 是显然的。
习题 5
\[\begin{aligned} \binom{n+m}{k} & =\left[x^k\right](1+x)^{n+m}=\left[x^k\right]\left((1+x)^n(1+x)^m\right) \\ & =\sum_{\substack{i+j=k \\ i, j \geq 0}}\left(\left[x^i\right](1+x)^n\right) \cdot\left(\left[x^j\right](1+x)^m\right) \\ & =\sum_{\substack{i+j=k \\ i, j \geq 0}}\binom{n}{i}\binom{m}{j} . \end{aligned} \]习题 6 证明如下等式:
\[\sum_{k=0}^n k\binom{n}{k}=n \cdot 2^{n-1} \]证法一：(构造组合模型). 设想某个班级有 \(n\) 名同学, 需要从中挑选若干同学 (至少 1 人) 参加某小组活动, 参加小组活动的同学之中需要有 1 人担任组长, 那么总共有多少种活动安排方案.
一方面, 若选择 \(k\) 人参加活动 \((k=1,2, \ldots, n)\), 则有 \(\binom{n}{k}\) 种选法, 之后在参加活动的 \(k\) 人之中选出组长, 因此恰有 \(k\) 人参加的活动方案共有 \(k\binom{n}{k}\)种, 总共有 \(\sum_{k=1}^n k\binom{n}{k}=\sum_{k=0}^n k\binom{n}{k}\) 种活动方案.
另一方面, 先从全班 \(n\) 人之中选定组长, 然后依次询问剩余 \((n-1)\) 个人中的每一个人是否参加, 由此易知共有 \(n \cdot 2^{n-1}\) 种活动方案.
组合证法的构造过程总是值得品味的，希望读者不是走马观花一样机械式的验证证明。请问证明中挑选若干同学这一步是怎么想到的？
另证： (用微积分). 将等式 \((1+x)^n=\sum_{k=0}^n\binom{n}{k} x^k\) 两边对 \(x\) 求导, 得到
\[n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k} x^{k-1} \]然后令 \(x=1\), 得证.
标签：geq,right,1.3,多项式,sum,binom,left,ldots,乘法 From： https://www.cnblogs.com/Pizixsir-Math/p/18262160除了构造组合模型, 微积分也是强力的手段