程序员社区

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

文章目录

  • 一、多项式系数
  • 二、多项式系数恒等式

一、多项式系数


下面

3

3

3 个数是等价的 :

① 多项式系数

(

n

n

1

n

2

n

t

)

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

(n1n2ntn)

② 多重集全排列数

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

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(n1n2ntn)x1n1x2n2xtnt

① 多项式系数

(

n

n

1

n

2

n

t

)

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

(n1n2ntn)

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}

(n1n2ntn)

3 . 放球子模型方案个数

(

n

n

1

n

2

n

t

)

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

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

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}

    (n2nn1) 种 ;

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

    (ntnn1n2nt1) 种 ;

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

    

(

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)(n2nn1)(ntnn1n2nt1)

=

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}

=(n1n2ntn)

二、多项式系数恒等式


多项式定理推论 3 :

(

n

n

1

n

2

n

t

)

=

t

n

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

(n1n2ntn)=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!}

(n1n2ntn)=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)}

(n1n2ntn)=((n11)n2ntn1)+(n1(n21)ntn1)+(n1n2(nt1)n1)

证明上述递推式 :

左侧

(

n

n

1

n

2

n

t

)

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

(n1n2ntn) 是放球问题的解 ,

右侧第

1

1

1

(

n

1

(

n

1

1

)

n

2

n

t

)

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

((n11)n2ntn1) 是 指定某个球

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(n21)ntn1) 是 指定某个球

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(nt1)n1) 是 指定某个球

a

1

a_1

a1 必须落到第

t

t

t 个盒子中的方案个数 ;

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【组合数学】多项式定理 ( 多项式系数 | 多重集全排列 | 对应放球子模型方案数 | 多项式系数相关恒等式 )

相关推荐

  • 暂无文章

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