【组合数学：二】鸽巢原理 | 二项式系数 | 多项式定理

【组合数学：二】

• 鸽巢原理
• 二项式系数
• • 多项式定理
  • 牛顿二项式定理
  • 练习题

鸽巢原理

• 定理：把 n + 1 n+1 n+1 个物体放进 n n n 个盒子，至少有一个盒子包含两个或更多的物体

• 应用：给定 m m m 个整数 a 1 , a 2 , ⋯   , a m a_1,a_2,\cdots,a_m a1​,a2​,⋯,am​ ，至少存在一个区间 [ L , R ] [L,R] [L,R]，满足 m ∣ ( a L + a L + 1 + ⋯ + a R ) m\Big|(a_L+a_{L+1}+\cdots +a_R) m∣∣∣​(aL​+aL+1​+⋯+aR​)

  证明：考虑 m m m 个前缀和 p r e [ n ] = ∑ i = 1 n a i pre[n]=\sum_{i=1}^n a_i pre[n]=∑i=1n​ai​

  若 m ∣ p r e [ i ] m\Big|pre[i] m∣∣∣​pre[i]，则结论直接成立

  否则，一定存在一对 i < j i<j i<j ，使得 p r e [ i ] ≡ p r e [ j ] ( m o d m ) pre[i]\equiv pre[j]\pmod m pre[i]≡pre[j](modm) ,于是区间和 [ i + 1 , j ] [i+1,j] [i+1,j] 的和一定被 m m m 整除

• 鸽巢定理加强版：设 q 1 , q 2 , ⋯   , a n q_1,q_2,\cdots,a_n q1​,q2​,⋯,an​ 是正整数。如果将

  q 1 + q 2 + ⋯ + q n − n + 1 q_1+q_2+\cdots+q_n-n+1 q1​+q2​+⋯+qn​−n+1

  个物体放入 n n n 个盒子内，那么或者第一个盒子至少有 q 1 q_1 q1​ 个物体，或者第二个盒子至少有 q 2 q_2 q2​ 个物体，……，或者第 n n n 个盒子至少有 q n q_n qn​ 个物体

• 推论：如果把 n ( r − 1 ) + 1 n(r-1)+1 n(r−1)+1 个物体放到 n n n 个盒子中，那么至少有一个盒子含有 r r r 个或更多个物体

二项式系数

• 二项式定理： ( x + y ) n = ∑ i = 0 n C n i x i y n − i (x+y)^n=\sum_{i=0}^nC_{n}^i x^iy^{n-i} (x+y)n=∑i=0n​Cni​xiyn−i

  定理：

  ∑ i 是 偶 数 C n i = ∑ i 是 奇 数 C n i = 2 n − 1 \sum_{i是偶数}C_n^i=\sum_{i是奇数}C_n^i=2^{n-1} i是偶数∑​Cni​=i是奇数∑​Cni​=2n−1

• 公式：

  ∑ i = 1 n i ⋅ C n i = n 2 n − 1 ∑ i = 1 n i 2 ⋅ C n i = n ( n + 1 ) 2 n − 2 \sum_{i=1}^n i\cdot C_n^i= n2^{n-1}\\ \sum_{i=1}^n i^2\cdot C_n^i= n(n+1)2^{n-2} i=1∑n​i⋅Cni​=n2n−1i=1∑n​i2⋅Cni​=n(n+1)2n−2

  证明：

  ( 1 + x ) n = ∑ C n i x i (1+x)^n=\sum C_n^ix^i (1+x)n=∑Cni​xi

  两边关于 x x x 求导，得到：

  n ( 1 + x ) n − 1 = ∑ C n i ⋅ i ⋅ x i − 1 n(1+x)^{n-1}=\sum C_n^i \cdot i\cdot x^{i-1} n(1+x)n−1=∑Cni​⋅i⋅xi−1

  带入 x = 1 x=1 x=1，得到：

  n 2 n − 1 = ∑ i ⋅ C n i n2^{n-1}=\sum i\cdot C_n^i n2n−1=∑i⋅Cni​

  若两边再乘以 x x x，再关于 x x x 求导，带入 x = 1 x=1 x=1，即可获得下一个式子

• 公式：

  ∑ i = 0 n ( C n i ) 2 = C 2 n n \sum_{i=0}^n (C_n^i)^2=C_{2n}^n i=0∑n​(Cni​)2=C2nn​

  证明：左边可以转化为：

  ∑ C n i C n n − i \sum C_n^i C_n^{n-i} ∑Cni​Cnn−i​

  相当于两个 n n n 个元素的集合，第一个集合选 i i i 个，第二个集合选 n − i n-i n−i 个

  相当于一个 2 n 2n 2n 个元素的集合，选 n n n 个

  推广到 范德蒙的卷积形式：

  ∑ C n i C m k − i = C n + m k \sum C_n^i C_m^{k-i}=C_{n+m}^k ∑Cni​Cmk−i​=Cn+mk​

• 公式：

  C r 0 + C r + 1 1 + ⋯ + C r + k k = C r + k + 1 k C_r^0+C_{r+1}^1+\cdots+C_{r+k}^k=C_{r+k+1}^k Cr0​+Cr+11​+⋯+Cr+kk​=Cr+k+1k​

  证明：可令 C r 0 = C r + 1 0 C_r^0=C_{r+1}^0 Cr0​=Cr+10​，一直使用帕斯卡公式替换即可。

多项式定理

• 多项式系数

  ( n n 1   n 2 ⋯ n 3 ) = n ! ∏ ( n i ! ) \begin{pmatrix} n\\ n_1\ n_2\cdots n_3 \end{pmatrix} =\frac{n!}{\prod (n_i!)} (nn1​ n2​⋯n3​​)=∏(ni​!)n!​

• 多项式定理：

  ( x 1 + x 2 + ⋯ + x t ) n = ∑ ( n n 1   n 2 ⋯ n 3 ) x 1 n 1 x 2 n 2 ⋯ x t n t (x_1+x_2+\cdots+x_t)^n= \sum \begin{pmatrix} n\\ n_1\ n_2\cdots n_3 \end{pmatrix} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} (x1​+x2​+⋯+xt​)n=∑(nn1​ n2​⋯n3​​)x1n1​​x2n2​​⋯xtnt​​

牛顿二项式定理

• 定理：设 α \alpha α 是实数。对于所有满足 0 ≤ ∣ x ∣ < ∣ y ∣ 0\le |x|<|y| 0≤∣x∣<∣y∣ ，我们有

  ( x + y ) α = ∑ k = 0 ∞ C α k x k y α − k (x+y)^{\alpha}=\sum_{k=0}^\infin C_{\alpha}^k x^k y^{\alpha-k} (x+y)α=k=0∑∞​Cαk​xkyα−k

  设 z = x / y z=x/y z=x/y，那么 ( x + y ) α = y ( 1 + z ) α (x+y)^\alpha =y(1+z)^\alpha (x+y)α=y(1+z)α

  于是我们问题等价转化为： ∣ z ∣ < 1 |z|<1 ∣z∣<1，求 ( 1 + z ) α (1+z)^\alpha (1+z)α

  我们有：

  ( 1 + z ) α = ∑ k = 0 ∞ C α k z k (1+z)^\alpha=\sum_{k=0}^\infin C_\alpha ^k z^k (1+z)α=k=0∑∞​Cαk​zk

  我们选择 α = − n \alpha=-n α=−n，带入得到：

  C α k = C − n k = − n ( − n − 1 ) ⋯ ( − n − k + 1 ) k ! = ( − 1 ) k C n + k − 1 k C_\alpha^k=C_{-n}^k=\frac{-n(-n-1)\cdots(-n-k+1)}{k!}=(-1)^kC_{n+k-1}^k Cαk​=C−nk​=k!−n(−n−1)⋯(−n−k+1)​=(−1)kCn+k−1k​

  带入直接可以得到：

  1 ( 1 + z ) n = ∑ k = 0 ∞ ( − 1 ) k C n + k − 1 k z k 1 ( 1 − z ) n = ∑ k = 0 ∞ C n + k − 1 k z k \frac{1}{(1+z)^n}=\sum_{k=0}^\infin (-1)^k C_{n+k-1}^k z^k\\ \frac{1}{(1-z)^n}=\sum_{k=0}^\infin C_{n+k-1}^k z^k\\ (1+z)n1​=k=0∑∞​(−1)kCn+k−1k​zk(1−z)n1​=k=0∑∞​Cn+k−1k​zk

  组合推导过程：

  1 ( 1 − z ) n = ( 1 + z + z 2 + ⋯   ) ⋯ ( 1 + z + z 2 + ⋯   ) \frac{1}{(1-z)^n}=(1+z+z^2+\cdots)\cdots(1+z+z^2+\cdots) (1−z)n1​=(1+z+z2+⋯)⋯(1+z+z2+⋯)

  通过第一个因子选 z k 1 z^{k_1} zk1​ 个，……，第 n n n 个因子选 z k n z^{k_n} zkn​ 个，我们有 ∏ z k i = z \prod z^{k_i}=z ∏zki​=z

  就是多重集合 n n n 元素的 r r r 组合，就是 C n + r − 1 r C_{n+r-1}^r Cn+r−1r​

练习题

• 化简求和：

  ∑ k = 0 n C n k r k \sum_{k=0}^n C_n^k r^k k=0∑n​Cnk​rk

  解：用二项式定理化简，得到：

  ∑ k = 0 n C n k r k = ∑ k = 0 n C n k r k ⋅ 1 n − k = ( 1 + r ) n \sum_{k=0}^n C_n^k r^k=\sum_{k=0}^n C_n^k r^k\cdot 1^{n-k}=(1+r)^n k=0∑n​Cnk​rk=k=0∑n​Cnk​rk⋅1n−k=(1+r)n

• 化简求和：

  ∑ k = 0 n ( − 1 ) k C n k 3 n − k \sum_{k=0}^n (-1)^k C_n^k 3^{n-k} k=0∑n​(−1)kCnk​3n−k

  解：用二项式定理化简，就是 ( 3 − 1 ) n = 2 n (3-1)^n=2^n (3−1)n=2n

• 化简求和：

  ∑ k = 0 n ( − 1 ) k C n k 1 0 k \sum_{k=0}^n (-1)^k C_n^k 10^k k=0∑n​(−1)kCnk​10k

  解：用二项式定理化简，就是：

  ∑ k = 0 n ( − 1 ) k C n k 1 0 k = ( − 1 ) n ∑ k = 0 n ( − 1 ) n − k C n k 1 0 k = ( − 1 ) n ( 10 − 1 ) n = ( − 1 ) n 9 n \sum_{k=0}^n (-1)^k C_n^k 10^k=(-1)^n\sum_{k=0}^n (-1)^{n-k} C_n^k 10^k=(-1)^n (10-1)^n=(-1)^n9^n k=0∑n​(−1)kCnk​10k=(−1)nk=0∑n​(−1)n−kCnk​10k=(−1)n(10−1)n=(−1)n9n

• 化简求和：

  ∑ k = 0 n ( − 1 ) k ( C n k ) 2 \sum_{k=0}^n (-1)^k (C_n^k)^2 k=0∑n​(−1)k(Cnk​)2

  解：当 n n n 为奇数时，容易得到

  ( − 1 ) k ( C n k ) 2 + ( − 1 ) n − k ( C n n − k ) = 0 (-1)^k(C_n^k)^2+(-1)^{n-k}(C_n^{n-k})=0 (−1)k(Cnk​)2+(−1)n−k(Cnn−k​)=0

  所以原式答案就是 0 0 0

  当 n n n 为偶数时，考虑 ( 1 − x 2 ) n = ( 1 + x ) n ( 1 − x ) n (1-x^2)^n=(1+x)^n(1-x)^n (1−x2)n=(1+x)n(1−x)n 的 [ x n ] [x^n] [xn]

  左边式子为： ( − 1 ) n / 2 C n n / 2 (-1)^{n/2}C_{n}^{n/2} (−1)n/2Cnn/2​

  右边式子为： ∑ i = 0 n C n i ⋅ C n n − i ⋅ ( − 1 ) i = \sum_{i=0}^n C_{n}^i \cdot C_n^{n-i}\cdot (-1)^i= ∑i=0n​Cni​⋅Cnn−i​⋅(−1)i= 原式

• 化简求和：

  ∑ i = 1 n ( − 1 ) i − 1 ⋅ i ⋅ C n i \sum_{i=1}^n (-1)^{i-1}\cdot i\cdot C_n^i i=1∑n​(−1)i−1⋅i⋅Cni​

  解：对二项式 ( x − 1 ) n (x-1)^n (x−1)n 展开求导，得到：

  ∑ i = 0 n i ⋅ ( − 1 ) n − i ⋅ C n i x i − 1 = n ( x − 1 ) n − 1 \sum_{i=0}^n i\cdot (-1)^{n-i} \cdot C_n^i x^{i-1} =n(x-1)^{n-1} i=0∑n​i⋅(−1)n−i⋅Cni​xi−1=n(x−1)n−1

  带入 x = 1 x=1 x=1，得到：左边 = 0 =0 =0

  注意到，原式为左边项或者左边项的负数，都是 0 0 0

• 化简求和：

  ∑ i = 0 n 1 i + 1 C n i \sum_{i=0}^n \frac{1}{i+1}C_n^i i=0∑n​i+11​Cni​

  解：对二项式 ( 1 + x ) n (1+x)^n (1+x)n 及其展开求积分，得到：

  ∫ ∑ i = 0 n C n i x i d x = ∫ ( 1 + x ) n d x \int \sum_{i=0}^n C_n^i x^i dx=\int (1+x)^n dx ∫i=0∑n​Cni​xidx=∫(1+x)ndx

  解得：

  ∑ i = 0 n 1 i + 1 C n i = ( 1 + x ) n + 1 1 + n + C \sum_{i=0}^n \frac{1}{i+1}C_n^i=\frac{(1+x)^{n+1}}{1+n}+C i=0∑n​i+11​Cni​=1+n(1+x)n+1​+C

  带入解得 C = − 1 1 + n C=-\frac{1}{1+n} C=−1+n1​

  带入 x = 1 x=1 x=1

  所以原式化简为： 2 n + 1 − 1 1 + n \frac{2^{n+1}-1}{1+n} 1+n2n+1−1​

• 化简求和：

  ∑ i = 0 n ( − 1 ) i 1 i + 1 C n i \sum_{i=0}^n (-1)^i\frac{1}{i+1}C_n^i i=0∑n​(−1)ii+11​Cni​

  解：对二项式 ( x − 1 ) n (x-1)^n (x−1)n 及其展开求积分，类似上面，带入 x = 1 x=1 x=1，然后发现上述式子 = 0 =0 =0

• 化简求和：

  ∑ i = 1 n C n k C n k − 1 \sum_{i=1}^nC_n^k C_n^{k-1} i=1∑n​Cnk​Cnk−1​

  解：带入范德蒙的卷积公式，得到：

  I = ∑ i = 1 n C n k C n n − k + 1 = C 2 n n + 1 I=\sum_{i=1}^nC_n^k C_n^{n-k+1}=C_{2n}^{n+1} I=i=1∑n​Cnk​Cnn−k+1​=C2nn+1​

  书本给的式子为：（可能是用组合推导得到的）

  1 2 C 2 n + 2 n + 1 − C 2 n n \frac{1}{2}C_{2n+2}^{n+1}-C_{2n}^n 21​C2n+2n+1​−C2nn​

  容易得到，这两个式子是等价的（带入化简即可）

• 化简求和：

  ∑ k = 1 k ⋅ ( C n k ) 2 \sum_{k=1}k\cdot (C_n^k)^2 k=1∑​k⋅(Cnk​)2

  解：考虑组合推导，式子化一下变成：

  ∑ k = 1 k ⋅ C n k ⋅ C n n − k \sum_{k=1}k\cdot C_n^k\cdot C_n^{n-k} k=1∑​k⋅Cnk​⋅Cnn−k​

  相当于有 n n n 个男生， n n n 个女生，选一个 n n n 个人的团队，且团队里有一位男队长的方案

  所以式子就是：

  I = n C 2 n − 1 n − 1 I=nC_{2n-1}^{n-1} I=nC2n−1n−1​

• 化简求和：

  ∑ r , s , t ≥ 0 r + s + t = n C m 1 r C m 2 s C m 3 t \sum_{\underset{r+s+t=n}{r,s,t\ge 0}} C_{m_1}^r C_{m_2}^s C_{m_3}^t r+s+t=nr,s,t≥0​∑​Cm1​r​Cm2​s​Cm3​t​

  解：考虑组合推导，就是在全集 m 1 + m 2 + m 3 m_1+m_2+m_3 m1​+m2​+m3​ 中选出 n n n 个元素的方案数，即：

  C m 1 + m 2 + m 3 n C_{m_1+m_2+m_3}^n Cm1​+m2​+m3​n​

• 化简求和：

  ∑ ∑ n i = n n i ≥ 0 ( n n 1   n 2 ⋯ n t ) \sum_{\underset{n_i\ge 0}{\sum n_i=n}} \begin{pmatrix} n\\ n_1\ n_2 \cdots n_t \end{pmatrix} ni​≥0∑ni​=n​∑​(nn1​ n2​⋯nt​​)

  解一：多项式系数，组合意义上就是共 n n n 个不同小球，放在 t t t 个不同盒子里，第 i i i 个盒子里有 n i n_i ni​ 个球的方案数

  所有情况求和，相当于每一个小球都可以放在不同的盒子里

  方案数自然就是 t n t^n tn

  解二：多项式定理，令 x i = 1 x_i=1 xi​=1，即可得到

• 化简求和：

  ∑ n 1 + n 2 + n 3 = n n i ≥ 0 ( n n 1   n 2   n 3 ) ( − 1 ) n 1 − n 2 + n 3 \sum_{\underset{n_i\ge 0}{n_1+n_2+n_3=n}} \begin{pmatrix} n\\ n_1\ n_2\ n_3 \end{pmatrix} (-1)^{n_1-n_2+n_3} ni​≥0n1​+n2​+n3​=n​∑​(nn1​ n2​ n3​​)(−1)n1​−n2​+n3​

  解：根据多项式定理，我们得到：

  ( x 1 + x 2 + x 3 ) n = ∑ ( n n 1   n 2   n 3 ) x 1 n 1 x 2 n 2 x 3 n 3 (x_1+x_2+x_3)^n=\sum \begin{pmatrix} n\\ n_1\ n_2\ n_3 \end{pmatrix} x_1^{n_1} x_2^{n_2} x_3^{n_3} (x1​+x2​+x3​)n=∑(nn1​ n2​ n3​​)x1n1​​x2n2​​x3n3​​

  我们令 x 1 = x 2 = x 3 = − 1 x_1=x_2=x_3=-1 x1​=x2​=x3​=−1，带入得到：

  ∑ ( n n 1   n 2   n 3 ) ( − 1 ) n 1 + n 2 + n 3 = ∑ ( n n 1   n 2   n 3 ) ( − 1 ) n 1 − n 2 + n 3 = ( − 3 ) n \begin{aligned} &\sum \begin{pmatrix} n\\ n_1\ n_2\ n_3 \end{pmatrix}(-1)^{n_1+n_2+n_3}\\ &= \sum \begin{pmatrix} n\\ n_1\ n_2\ n_3 \end{pmatrix}(-1)^{n_1-n_2+n_3}\\ &=(-3)^n \end{aligned} ​∑(nn1​ n2​ n3​​)(−1)n1​+n2​+n3​=∑(nn1​ n2​ n3​​)(−1)n1​−n2​+n3​=(−3)n​

  因为我们注意到 ( − 1 ) x = ( − 1 ) − x (-1)^{x}=(-1)^{-x} (−1)x=(−1)−x

• 化简求和：

  ∑ n 1 + n 2 + n 3 + n 4 = n n i ≥ 0 ( n n 1   n 2   n 3   n 4 ) ( − 1 ) n 2 + n 4 \sum_{\underset{n_i\ge 0}{n_1+n_2+n_3+n_4=n}} \begin{pmatrix} n\\ n_1\ n_2\ n_3\ n_4 \end{pmatrix} (-1)^{n_2+n_4} ni​≥0n1​+n2​+n3​+n4​=n​∑​(nn1​ n2​ n3​ n4​​)(−1)n2​+n4​

  解：我们构造多项式

  ( x 1 − x 2 + x 3 − x 4 ) n (x_1-x_2+x_3-x_4)^n (x1​−x2​+x3​−x4​)n

  并拆成相应的多项式

  带入 x i = 1 x_i=1 xi​=1，容易得到 I = 0 I=0 I=0