【组合数学】多项式定理 ( 多项式系数 | 多重集全排列 | 对应放球子模型方案数 | 多项式系数相关恒等式 )

一、多项式系数

下面 3 3 3 个数是等价的 :

① 多项式系数 ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​)

② 多重集全排列数

③ 不同的球放到不同盒子中 , 不允许有空盒 , 每个盒子放指定个数的球 方案个数 ;

1 . 多项式系数

多项式定理中

     ( 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​​

的 ① 多项式系数 ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​)

2 . 多重集全排列数 :

同时又代表了 ② 多重集的全排列数 n ! n 1 ! n 2 ! ⋯ n k ! \cfrac{n!}{n_1! n_2! \cdots n_k!} n1​!n2​!⋯nk​!n!​ , 可以简记为 ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​)

3 . 放球子模型方案个数

③ ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​) 可以代表放球模型的一个子类型的解个数 ,

n n n 不同的球 , 放到 t t t 个不同的盒子里 , 注意此处 球 和 盒子都有区别 ,

第 1 1 1 个盒子放 n 1 n_1 n1​ 个球 , 第 2 2 2 个盒子放 n 2 n_2 n2​ 个球 , ⋯ \cdots ⋯ , 第 t t t 个盒子放 n t n_t nt​ 个球 的方案数 ;

相当于多步处理 :

• 第 1 1 1 步 : 选择 n 1 n_1 n1​ 个球 , 放到 第 1 1 1 个盒子中 ; 选取方法有 ( n n 1 ) \dbinom{n}{n_1} (n1​n​) 种 ;
• 第 2 2 2 步 : 选择 n 2 n_2 n2​ 个球 , 放到 第 2 2 2 个盒子中 ; 选取方法有 ( n − n 1 n 2 ) \dbinom{n-n_1}{n_2} (n2​n−n1​​) 种 ; ⋮ \vdots ⋮
• 第 t t t 步 : 选择 n t n_t nt​ 个球 , 放到 第 t t t 个盒子中 ; 选取方法有 ( n − n 1 − n 2 − ⋯ − n t − 1 n t ) \dbinom{n-n_1-n_2 - \cdots -n_{t-1}}{n_t} (nt​n−n1​−n2​−⋯−nt−1​​) 种 ;

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

     ( 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​)

二、多项式系数恒等式

多项式定理推论 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

多重集全排列 :

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

递推式 :

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

证明上述递推式 :

左侧 ( n n 1 n 2 ⋯ n t ) \dbinom{n}{n_1 n_2 \cdots n_t} (n1​n2​⋯nt​n​) 是放球问题的解 ,

右侧第 1 1 1 项 ( n − 1 ( n 1 − 1 ) n 2 ⋯ n t ) \dbinom{n-1}{(n_1-1) n_2 \cdots n_t} ((n1​−1)n2​⋯nt​n−1​) 是 指定某个球 a 1 a_1 a1​ 必须落到第 1 1 1 个盒子中的方案个数 ;

右侧第 2 2 2 项 ( n − 1 n 1 ( n 2 − 1 ) ⋯ n t ) \dbinom{n-1}{n_1 (n_2 - 1) \cdots n_t} (n1​(n2​−1)⋯nt​n−1​) 是 指定某个球 a 1 a_1 a1​ 必须落到第 2 2 2 个盒子中的方案个数 ;

⋮ \vdots ⋮

右侧第 t t t 项 ( n − 1 n 1 n 2 ⋯ ( n t − 1 ) ) \dbinom{n-1}{n_1 n_2 \cdots (n_t -1)} (n1​n2​⋯(nt​−1)n−1​) 是 指定某个球 a 1 a_1 a1​ 必须落到第 t t t 个盒子中的方案个数 ;