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

韩曙亮

发布于 2023-03-28 18:27:16

3780

发布于 2023-03-28 18:27:16

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、多项式系数

下面

个数是等价的 :

① 多项式系数

\dbinom{n}{n_1 n_2 \cdots n_t}

② 多重集全排列数

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

1 . 多项式系数

多项式定理中

\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n

= \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}

的 ① 多项式系数

\dbinom{n}{n_1 n_2 \cdots n_t}

2 . 多重集全排列数 :

同时又代表了 ② 多重集的全排列数

\cfrac{n!}{n_1! n_2! \cdots n_k!}

, 可以简记为

\dbinom{n}{n_1 n_2 \cdots n_t}

3 . 放球子模型方案个数

③

\dbinom{n}{n_1 n_2 \cdots n_t}

可以代表放球模型的一个子类型的解个数 ,

不同的球 , 放到

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

第

个盒子放

n_1

个球 , 第

个盒子放

n_2

个球 ,

\cdots

, 第

个盒子放

n_t

个球的方案数 ;

相当于多步处理 :

步 : 选择

n_1

个球 , 放到第

个盒子中 ; 选取方法有

\dbinom{n}{n_1}

种 ;

步 : 选择

n_2

个球 , 放到第

个盒子中 ; 选取方法有

\dbinom{n-n_1}{n_2}

种 ;

\vdots

步 : 选择

n_t

个球 , 放到第

个盒子中 ; 选取方法有

\dbinom{n-n_1-n_2 - \cdots -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}

=\cfrac{n!}{n_1! n_2! \cdots n_t!}

=\dbinom{n}{n_1 n_2 \cdots n_t}

二、多项式系数恒等式

多项式定理推论 3 :

\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n

多重集全排列 :

\dbinom{n}{n_1 n_2 \cdots n_t} = \cfrac{n!}{n_1! n_2! \cdots n_k!}

递推式 :

\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)}

证明上述递推式 :

左侧

\dbinom{n}{n_1 n_2 \cdots n_t}

是放球问题的解 ,

右侧第

项

\dbinom{n-1}{(n_1-1) n_2 \cdots n_t}

是指定某个球

a_1

必须落到第

个盒子中的方案个数 ;

右侧第

项

\dbinom{n-1}{n_1 (n_2 - 1) \cdots n_t}

是指定某个球

a_1

必须落到第

个盒子中的方案个数 ;

\vdots

右侧第

项

\dbinom{n-1}{n_1 n_2 \cdots (n_t -1)}

是指定某个球

a_1

必须落到第

个盒子中的方案个数 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

模型

数学

原理

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

模型

数学

原理

登录后参与评论

0 条评论

热度