【组合数学】多项式定理 ( 多项式定理

多项式定理 :

设 n n n 为正整数 , x i x_i xi​ 为实数 , i = 1 , 2 , ⋯   , t i=1,2,\cdots,t i=1,2,⋯,t

     ( x 1 + x 2 + ⋯ + x t ) n \ \ \ \ (x_1 + x_2 + \cdots + x_t)^n     (x1​+x2​+⋯+xt​)n

= ∑ 满 足 n 1 + n 2 + ⋯ + n t = n 非 负 整 数 解 个 数 ( n n 1 n 2 ⋯ n t ) x 1 n 1 x 2 n 2 ⋯ x t n t = \sum\limits_{满足 n_1 + n_2 + \cdots + n_t = n 非负整数解个数}\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} =满足n1​+n2​+⋯+nt​=n非负整数解个数∑​(n1​n2​⋯nt​n​)x1n1​​x2n2​​⋯xtnt​​

上述多项式有 t t t 个项 , 这 t t t 项相加的 n n n 次方 ;

多项式中 ( x 1 + x 2 + ⋯ + x t ) n (x_1 + x_2 + \cdots + x_t)^n (x1​+x2​+⋯+xt​)n :

分步进行如下处理 :

第 1 1 1 步 : 从 n n n 个因式中 , 选 n 1 n_1 n1​ 个因式 , 每个因式贡献 1 1 1 个 x 1 x_1 x1​ , 总共贡献 n 1 n_1 n1​ 个 x 1 x_1 x1​ , 选取方法有 ( n n 1 ) \dbinom{n}{n_1} (n1​n​) 种 ;

第 2 2 2 步 : 从 n − n 1 n-n_1 n−n1​ 个因式中 , 选 n 2 n_2 n2​ 个因式 , 每个因式贡献 1 1 1 个 x 2 x_2 x2​ , 总共贡献 n 2 n_2 n2​ 个 x 2 x_2 x2​ , 选取方法有 ( n − n 1 n 2 ) \dbinom{n-n_1}{n_2} (n2​n−n1​​) 种 ;

⋮ \vdots ⋮

根据分步计数原理 , 乘法法则 , 将上面每步的种类个数相乘 , 就是所有的种类个数 :

     ( n n 1 ) ( n − n 1 n 2 ) ( n − n 1 − n 2 − ⋯ − n t − 1 n t ) \ \ \ \ \dbinom{n}{n_1} \dbinom{n-n_1}{n_2} \dbinom{n-n_1-n_2 - \cdots -n_{t-1}}{n_t}     (n1​n​)(n2​n−n1​​)(nt​n−n1​−n2​−⋯−nt−1​​)

展开后 , 很多都可以约掉 , 最终得到 :

= n ! n 1 ! n 2 ! ⋯ n t ! =\cfrac{n!}{n_1! n_2! \cdots n_t!} =n1​!n2​!⋯nt​!n!​

注意上面的式子是多重集的全排列数

= ( n n 1 n 2 ⋯ n t ) =\dbinom{n}{n_1 n_2 \cdots n_t} =(n1​n2​⋯nt​n​)

多项式定理 推论 1 :

上述多项式定理中 , 不同的项数 是方程

n 1 + n 2 + ⋯ + n t = n n_1 + n_2 + \cdots + n_t = n n1​+n2​+⋯+nt​=n

非负整数解个数 C ( n + t − 1 , n ) C(n + t -1 , n) C(n+t−1,n)

证明过程 :

1 . 每一项之前的系数 ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​) 含义 :

n 1 n_1 n1​ 代表 x 1 x_1 x1​ 的指数 , n 1 n_1 n1​ 相当于有多少个式子 , 在相乘的时候 , 取了 x 1 x_1 x1​

n 2 n_2 n2​ 代表 x 2 x_2 x2​ 的指数 , n 2 n_2 n2​ 相当于有多少个式子 , 在相乘的时候 , 取了 x 2 x_2 x2​

⋮ \vdots ⋮

2 . 一一对应关系 :

n 1 , n 2 , ⋯   , n t n_1, n_2, \cdots , n_t n1​,n2​,⋯,nt​ 的一组不同的选择 , 相当于

n 1 + n 2 + ⋯ + n t = n n_1 + n_2 + \cdots + n_t = n n1​+n2​+⋯+nt​=n

的一个解 , 对应了不同的 x 1 , x 2 , ⋯   , x n x_1 , x_2, \cdots, x_n x1​,x2​,⋯,xn​ 之前的项 ;

三个对应关系 :

不同的解 , n 1 , n 2 , ⋯   , n t n_1, n_2, \cdots , n_t n1​,n2​,⋯,nt​ 配置不一样 , 这些项 不同的配置个数 ,

相当于 n 1 + n 2 + ⋯ + n t = n n_1 + n_2 + \cdots + n_t = n n1​+n2​+⋯+nt​=n 的非负整数解个数 ,

又等同于 多项式 展开后的 项的个数 ;

因此求出 n 1 + n 2 + ⋯ + n t = n n_1 + n_2 + \cdots + n_t = n n1​+n2​+⋯+nt​=n 的非负整数解个数 ,

就对应了 n 1 , n 2 , ⋯   , n t n_1, n_2, \cdots , n_t n1​,n2​,⋯,nt​ 不同配置的个数 ,

对应了 多项式展开后项的个数 ,

结果是 C ( n + t − 1 , n ) C(n + t -1 , n) C(n+t−1,n)

该数还是多重集的组合数

推导过程 参考多重集组合问题 : 多重集 : S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ n i ≤ + ∞ S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty S={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞ 取 r r r 种元素的组合 , r ≤ n i r \leq n_i r≤ni​ , 推导过程如下 : 在 k k k 种元素中 , 取 r r r 种元素 , 每种元素取 0 ∼ r 0 \sim r 0∼r 个不等的元素 , 使用 k − 1 k-1 k−1 个分割线分割 k k k 种元素的位置 , k − 1 k - 1 k−1 个分割线相当于组成了 k k k 个盒子 , 在每个盒子中放 0 ∼ r 0 \sim r 0∼r 个不等的元素 , 放置的总元素的个数是 r r r 个 , 分割线个数是 k − 1 k-1 k−1 个 , 这里就产生了一个组合问题 , 在 k − 1 k-1 k−1 个分割线 和 r r r 个元素之间 , 选取 r r r 个元素 , 就是 多重集的 r ≤ n i r \leq n_i r≤ni​ 情况下的 组合个数 ; 结果是 : N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,r) 参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )

多项式定理 推论 3 :

∑ ( n n 1 n 2 ⋯ n t ) = t n \sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n ∑(n1​n2​⋯nt​n​)=tn

证明过程 :

多项式定理中

     ( x 1 + x 2 + ⋯ + x t ) n \ \ \ \ (x_1 + x_2 + \cdots + x_t)^n     (x1​+x2​+⋯+xt​)n

= ∑ 满 足 n 1 + n 2 + ⋯ + n t = n 非 负 整 数 解 个 数 ( n n 1 n 2 ⋯ n t ) x 1 n 1 x 2 n 2 ⋯ x t n t = \sum\limits_{满足 n_1 + n_2 + \cdots + n_t = n 非负整数解个数}\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} =满足n1​+n2​+⋯+nt​=n非负整数解个数∑​(n1​n2​⋯nt​n​)x1n1​​x2n2​​⋯xtnt​​

如果将 x 1 = x 2 = ⋯ = x t = 1 x_1 = x_2 = \cdots = x_t = 1 x1​=x2​=⋯=xt​=1 ,

就可以得到

     ( 1 + 1 + ⋯ + 1 ) n \ \ \ \ (1 + 1 + \cdots + 1)^n     (1+1+⋯+1)n

= ∑ 满 足 n 1 + n 2 + ⋯ + n t = n 非 负 整 数 解 个 数 ( n n 1 n 2 ⋯ n t ) 1 n 1 1 n 2 ⋯ 1 n t = \sum\limits_{满足 n_1 + n_2 + \cdots + n_t = n 非负整数解个数}\dbinom{n}{n_1 n_2 \cdots n_t}1^{n_1}1^{n_2}\cdots 1^{n_t} =满足n1​+n2​+⋯+nt​=n非负整数解个数∑​(n1​n2​⋯nt​n​)1n1​1n2​⋯1nt​

= ∑ 满 足 n 1 + n 2 + ⋯ + n t = n 非 负 整 数 解 个 数 ( n n 1 n 2 ⋯ n t ) = \sum\limits_{满足 n_1 + n_2 + \cdots + n_t = n 非负整数解个数}\dbinom{n}{n_1 n_2 \cdots n_t} =满足n1​+n2​+⋯+nt​=n非负整数解个数∑​(n1​n2​⋯nt​n​)