[combinatorics] polynomial theorem (polynomial coefficients | full arrangement of multiple sets | number of schemes corresponding to the ball sub model | polynomial coefficient correlation identity)

One 、 Polynomial coefficients

---

below

3

3

3 The number is equivalent :

① Polynomial coefficients

(

n

n

1

n

2

⋯

n

t

)

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

(n1​n2​⋯nt​n​)

② The total permutation number of multiple sets

③ Put different balls in different boxes , Empty boxes are not allowed , Put a specified number of balls in each box Number of schemes ;

1 . Polynomial coefficients

Polynomial theorem

    

(

x

1

+

x

2

+

⋯

+

x

t

)

n

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

    (x1​+x2​+⋯+xt​)n

=

∑

full

foot

n

1

+

n

2

+

⋯

+

n

t

=

n

Not

negative

whole

Count

Explain

individual

Count

(

n

n

1

n

2

⋯

n

t

)

x

1

n

1

x

2

n

2

⋯

x

t

n

t

= \sum\limits_{ Satisfy n_1 + n_2 + \cdots + n_t = n Number of nonnegative integer solutions }\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}

= full foot n1​+n2​+⋯+nt​=n Not negative whole Count Explain individual Count ∑​(n1​n2​⋯nt​n​)x1n1​​x2n2​​⋯xtnt​​

Of ① Polynomial coefficients

(

n

n

1

n

2

⋯

n

t

)

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

(n1​n2​⋯nt​n​)

2 . The total permutation number of multiple sets :

At the same time, it represents ② The total permutation number of multiple sets

n

!

n

1

!

n

2

!

⋯

n

k

!

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

n1​!n2​!⋯nk​!n!​ , It can be abbreviated as

(

n

n

1

n

2

⋯

n

t

)

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

(n1​n2​⋯nt​n​)

3 . The number of ball sub model schemes

③

(

n

n

1

n

2

⋯

n

t

)

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

(n1​n2​⋯nt​n​) It can represent the number of solutions of a subtype of the ball release model ,

n

n

n Different balls , Put it in

t

t

t In a different box , Notice here The ball and There are differences between boxes ,

The first

1

1

1 A box for

n

1

n_1

n1​ A ball , The first

2

2

2 A box for

n

2

n_2

n2​ A ball ,

⋯

\cdots

⋯ , The first

t

t

t A box for

n

t

n_t

nt​ A ball Number of alternatives ;

Equivalent to multi-step processing :

• The first $n_1$

  1 Step : choice

• The first $n_2$

  2 Step : choice

• The first $n_t$

  t Step : choice

According to the principle of step-by-step counting , product rule , Multiply the number of categories in each step above , Is the number of all kinds :

    

(

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}

    (n1​n​)(n2​n−n1​​)(nt​n−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}

=(n1​n2​⋯nt​n​)

Two 、 Polynomial coefficient identity

---

Polynomial theorem inference 3 :

∑

(

n

n

1

n

2

⋯

n

t

)

=

t

n

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

∑(n1​n2​⋯nt​n​)=tn

Full Permutation of multiple sets :

(

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

(n1​n2​⋯nt​n​)=n1​!n2​!⋯nk​!n!​

recursion :

(

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

(n1​n2​⋯nt​n​)=((n1​−1)n2​⋯nt​n−1​)+(n1​(n2​−1)⋯nt​n−1​)+(n1​n2​⋯(nt​−1)n−1​)

Prove the above recursion :

left

(

n

n

1

n

2

⋯

n

t

)

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

(n1​n2​⋯nt​n​) It is the solution to the problem of putting the ball ,

Right side

1

1

1 term

(

n

−

1

(

n

1

−

1

)

n

2

⋯

n

t

)

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

((n1​−1)n2​⋯nt​n−1​) yes Specify a ball

a

1

a_1

a1​ Must fall to the first

1

1

1 Number of schemes in boxes ;

Right side

2

2

2 term

(

n

−

1

n

1

(

n

2

−

1

)

⋯

n

t

)

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

(n1​(n2​−1)⋯nt​n−1​) yes Specify a ball

a

1

a_1

a1​ Must fall to the first

2

2

2 Number of schemes in boxes ;

⋮

\vdots

⋮

Right side

t

t

t term

(

n

−

1

n

1

n

2

⋯

(

n

t

−

1

)

)

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

(n1​n2​⋯(nt​−1)n−1​) yes Specify a ball

a

1

a_1

a1​ Must fall to the first

t

t

t Number of schemes in boxes ;