文章目录

一、多项式定理
二、多项式定理证明
三、多项式定理推论 1
四、多项式定理推论 2

一、多项式定理

多项式定理 :

设

$n$ 为正整数 ,

x_i

$x_{i}$ 为实数 ,

⋯

i=1,2,\cdots,t

$i = 1, 2, \dots, t$

(

⋯

)

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

$(x_{1} + x_{2} + \dots + 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}

$= 满足 n_{1} + n_{2} + \dots + n_{t} = n 非负整数解个数 \sum (n _{1} n _{2} \dots n _{t} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{t}^{n_{t}}$

上述多项式有

$t$ 个项 , 这

$t$ 项相加的

$n$ 次方 ;

二、多项式定理证明

多项式中

(

x

1

+

x

2

+

⋯

+

x

t

)

n

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

$(x_{1} + x_{2} + \dots + x_{t})^{n}$ :

分步进行如下处理 :

第

1

1

$1$ 步 : 从

n

n

$n$ 个因式中 , 选

n

1

n_1

$n_{1}$ 个因式 , 每个因式贡献

1

1

$1$ 个

x

1

x_1

$x_{1}$ , 总共贡献

n

1

n_1

$n_{1}$ 个

x

1

x_1

$x_{1}$ , 选取方法有

(

n

n

1

)

\dbinom{n}{n_1}

$(n _{1} n)$ 种 ;
第

2

2

$2$ 步 : 从

n

−

n

1

n-n_1

$n - n_{1}$ 个因式中 , 选

n

2

n_2

$n_{2}$ 个因式 , 每个因式贡献

1

1

$1$ 个

x

2

x_2

$x_{2}$ , 总共贡献

n

2

n_2

$n_{2}$ 个

x

2

x_2

$x_{2}$ , 选取方法有

(

n

−

n

1

n

2

)

\dbinom{n-n_1}{n_2}

$(n _{2} n - n _{1})$ 种 ;

⋮

\vdots

$⋮$

第
$t$ 步 : 从

n

−

n

1

−

n

2

−

⋯

−

n

t

−

1

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

$n - n_{1} - n_{2} - \dots - n_{t - 1}$ 个因式中, 选

n

t

n_t

$n_{t}$ 个因式 , 每个因式贡献

1

1

$1$ 个

x

t

x_t

$x_{t}$ , 总共贡献

n

t

n_t

$n_{t}$ 个

x

t

x_t

$x_{t}$ , 选取方法有

(

n

−

n

1

−

n

2

−

⋯

−

n

t

−

1

n

t

)

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

$(n _{t} n - n _{1} - n _{2} - \dots - n _{t - 1})$ 种 ;

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

(

)

(

−

)

(

−

⋯

−

)

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

$(n _{1} n) (n _{2} n - n _{1}) (n _{t} n - n _{1} - n _{2} - \dots - n _{t - 1})$

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

⋯

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

$= \frac{n !}{n _{1} ! n _{2} ! \dots n _{t} !}$

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

(

⋯

)

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

$= (n _{1} n _{2} \dots n _{t} n)$

三、多项式定理推论 1

多项式定理推论 1 :

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

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = 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}

$(n _{1} n _{2} \dots n _{t} n)$ 含义 :

n

1

n_1

$n_{1}$ 代表

x

1

x_1

$x_{1}$ 的指数 ,

n

1

n_1

$n_{1}$ 相当于有多少个式子 , 在相乘的时候 , 取了

x

1

x_1

$x_{1}$
n

2

n_2

$n_{2}$ 代表

x

2

x_2

$x_{2}$ 的指数 ,

n

2

n_2

$n_{2}$ 相当于有多少个式子 , 在相乘的时候 , 取了

x

2

x_2

$x_{2}$

⋮

\vdots

$⋮$

$n_t nt 代表 x t x_t xt 的指数 , n t n_t nt 相当于有多少个式子 , 在相乘的时候 , 取了 x t x_t xt$

2 . 一一对应关系 :

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ 的一组不同的选择 , 相当于

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = n$

的一个解 , 对应了不同的

⋯

x_1 , x_2, \cdots, x_n

$x_{1}, x_{2}, \dots, x_{n}$ 之前的项 ;

三个对应关系 :

不同的解 ,

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ 配置不一样 , 这些项不同的配置个数 ,

相当于

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = n$ 的非负整数解个数 ,

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

因此求出

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = n$ 的非负整数解个数 ,

就对应了

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ 不同配置的个数 ,

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

结果是

(

−

)

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 = {n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}, 0 \leq n_{i} \leq + \infty$
取

r

r

$r$ 种元素的组合 ,

r

≤

n

i

r \leq n_i

$r \leq n_{i}$ , 推导过程如下 :

在

k

k

$k$ 种元素中 , 取

r

r

$r$ 种元素 , 每种元素取

0

∼

r

0 \sim r

$0 \sim 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 \sim 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 \leq n_{i}$ 情况下的组合个数 ;
结果是 :

N

=

C

(

k

+

r

−

1

,

r

)

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

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

四、多项式定理推论 2

多项式定理推论 3 :

∑

(

⋯

)

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

$\sum (n _{1} n _{2} \dots n _{t} n) = t^{n}$

证明过程 :

多项式定理中

(

⋯

)

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

$(x_{1} + x_{2} + \dots + 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}

$= 满足 n_{1} + n_{2} + \dots + n_{t} = n 非负整数解个数 \sum (n _{1} n _{2} \dots n _{t} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{t}^{n_{t}}$

如果将

x

1

=

x

2

=

⋯

=

x

t

=

1

x_1 = x_2 = \cdots = x_t = 1

$x_{1} = x_{2} = \dots = x_{t} = 1$ ,

就可以得到

(

⋯

)

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

$(1 + 1 + \dots + 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}

$= 满足 n_{1} + n_{2} + \dots + n_{t} = n 非负整数解个数 \sum (n _{1} n _{2} \dots n _{t} n) 1^{n_{1}} 1^{n_{2}} \dots 1^{n_{t}}$

∑

满

足

⋯

非

负

整

数

解

个

数

(

⋯

)

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

$= 满足 n_{1} + n_{2} + \dots + n_{t} = n 非负整数解个数 \sum (n _{1} n _{2} \dots n _{t} n)$

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

文章目录

一、多项式定理

二、多项式定理证明

三、多项式定理推论 1

四、多项式定理推论 2

相关推荐

一个分享Java & Python知识的社区

文章目录

一、多项式定理

二、多项式定理 证明

三、多项式定理 推论 1

四、多项式定理 推论 2

相关推荐

一个分享Java & Python知识的社区

二、多项式定理证明

三、多项式定理推论 1

四、多项式定理推论 2