【组合数学】多项式定理 ( 多项式定理 | 多项式定理证明 | 多项式定理推论 1 项数是非负整数解个数 | 多项式定理推论 2 每项系数之和 )

韩曙亮

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

1.2K0

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

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

文章目录

一、多项式定理

多项式定理 :

设

为正整数 ,

x_i

为实数 ,

i=1,2,\cdots,t

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

上述多项式有

个项 , 这

项相加的

次方 ;

二、多项式定理证明

多项式中

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

分步进行如下处理 :

步 : 从

个因式中 , 选

n_1

个因式 , 每个因式贡献

个

x_1

, 总共贡献

n_1

个

x_1

, 选取方法有

\dbinom{n}{n_1}

种 ;

步 : 从

n-n_1

个因式中 , 选

n_2

个因式 , 每个因式贡献

个

x_2

, 总共贡献

n_2

个

x_2

, 选取方法有

\dbinom{n-n_1}{n_2}

种 ;

\vdots

步 : 从

n-n_1-n_2 - \cdots -n_{t-1}

个因式中, 选

n_t

个因式 , 每个因式贡献

个

x_t

, 总共贡献

n_t

个

x_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}

三、多项式定理推论 1

多项式定理推论 1 :

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

n_1 + n_2 + \cdots + n_t = n

非负整数解个数

C(n + t -1 , n)

证明过程 :

1 . 每一项之前的系数

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

含义 :

n_1

代表

x_1

的指数 ,

n_1

相当于有多少个式子 , 在相乘的时候 , 取了

x_1

n_2

代表

x_2

的指数 ,

n_2

相当于有多少个式子 , 在相乘的时候 , 取了

x_2

\vdots

n_t

代表

x_t

的指数 ,

n_t

相当于有多少个式子 , 在相乘的时候 , 取了

x_t

2 . 一一对应关系 :

n_1, n_2, \cdots , n_t

的一组不同的选择 , 相当于

n_1 + n_2 + \cdots + n_t = n

的一个解 , 对应了不同的

x_1 , x_2, \cdots, x_n

之前的项 ;

三个对应关系 :

不同的解 ,

n_1, n_2, \cdots , n_t

配置不一样 , 这些项不同的配置个数 ,

相当于

n_1 + n_2 + \cdots + n_t = n

的非负整数解个数 ,

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

因此求出

n_1 + n_2 + \cdots + n_t = n

的非负整数解个数 ,

就对应了

n_1, n_2, \cdots , n_t

不同配置的个数 ,

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

结果是

C(n + t -1 , n)

该数还是多重集的组合数

推导过程参考多重集组合问题 : 多重集 :

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty

取

种元素的组合 ,

r \leq n_i

, 推导过程如下 :

在

种元素中 , 取

种元素 , 每种元素取

0 \sim r

个不等的元素 ,

使用

k-1

个分割线分割

种元素的位置 ,

k - 1

个分割线相当于组成了

个盒子 , 在每个盒子中放

0 \sim r

个不等的元素 ,

放置的总元素的个数是

个 , 分割线个数是

k-1

个 , 这里就产生了一个组合问题 , 在

k-1

个分割线和

个元素之间 , 选取

个元素 , 就是多重集的

r \leq n_i

情况下的组合个数 ;

结果是 :

N= C(k + r - 1, r)

参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数推导 1 分割线推导 | 多重集组合数推导 2 不定方程非负整数解个数推导 )

四、多项式定理推论 2

多项式定理推论 3 :

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

证明过程 :

多项式定理中

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

如果将

x_1 = x_2 = \cdots = x_t = 1

就可以得到

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

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

= \sum\limits_{满足 n_1 + n_2 + \cdots + n_t = n 非负整数解个数}\dbinom{n}{n_1 n_2 \cdots n_t}

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

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

配置

数学

原理

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

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

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

配置

数学

原理

登录后参与评论

0 条评论

热度