文章目录
一、多项式系数二、多项式系数恒等式
一、多项式系数
下面
3
3
3 个数是等价的 :
① 多项式系数
(
n
n
1
n
2
⋯
n
t
)
\dbinom{n}{n_1 n_2 \cdots n_t}
(n1n2⋯ntn)
② 多重集全排列数
③ 不同的球放到不同盒子中 , 不允许有空盒 , 每个盒子放指定个数的球 方案个数 ;
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非负整数解个数∑(n1n2⋯ntn)x1n1x2n2⋯xtnt
的 ① 多项式系数
(
n
n
1
n
2
⋯
n
t
)
\dbinom{n}{n_1 n_2 \cdots n_t}
(n1n2⋯ntn)
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}
(n1n2⋯ntn)
3 . 放球子模型方案个数
③
(
n
n
1
n
2
⋯
n
t
)
\dbinom{n}{n_1 n_2 \cdots n_t}
(n1n2⋯ntn) 可以代表放球模型的一个子类型的解个数 ,
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}
(n1n) 种 ;第
2
2
2 步 : 选择
n
2
n_2
n2 个球 , 放到 第
2
2
2 个盒子中 ; 选取方法有
(
n
−
n
1
n
2
)
\dbinom{n-n_1}{n_2}
(n2n−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}
(ntn−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}
(n1n)(n2n−n1)(ntn−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}
=(n1n2⋯ntn)
二、多项式系数恒等式
多项式定理推论 3 :
∑
(
n
n
1
n
2
⋯
n
t
)
=
t
n
\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n
∑(n1n2⋯ntn)=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!}
(n1n2⋯ntn)=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)}
(n1n2⋯ntn)=((n1−1)n2⋯ntn−1)+(n1(n2−1)⋯ntn−1)+(n1n2⋯(nt−1)n−1)
证明上述递推式 :
左侧
(
n
n
1
n
2
⋯
n
t
)
\dbinom{n}{n_1 n_2 \cdots n_t}
(n1n2⋯ntn) 是放球问题的解 ,
右侧第
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⋯ntn−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)⋯ntn−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)}
(n1n2⋯(nt−1)n−1) 是 指定某个球
a
1
a_1
a1 必须落到第
t
t
t 个盒子中的方案个数 ;