当前位置：网站首页>[combinatorics] polynomial theorem (polynomial coefficients | full arrangement of multiple sets | number of schemes corresponding to the ball sub model | polynomial coefficient correlation identity)

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

2022-07-03 16:35:00 【Programmer community】

List of articles

One 、 Polynomial coefficients
Two 、 Polynomial coefficient identity

One 、 Polynomial coefficients

below

$3$ The number is equivalent :

① Polynomial coefficients

(

⋯

)

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

$(n _{1} n _{2} \dots n _{t} 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 + \cdots + x_t)^n

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

∑

full

foot

⋯

Not

negative

whole

Count

Explain

individual

Count

(

⋯

)

⋯

= \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 n_{1} + n_{2} + \dots + n_{t} = n Not negative whole Count Explain individual Count \sum (n _{1} n _{2} \dots n _{t} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{t}^{n_{t}}$

Of ① Polynomial coefficients

(

⋯

)

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

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

2 . The total permutation number of multiple sets :

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

⋯

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

$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$ , It can be abbreviated as

(

⋯

)

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

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

3 . The number of ball sub model schemes

③

(

⋯

)

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

$(n _{1} n _{2} \dots n _{t} n)$ It can represent the number of solutions of a subtype of the ball release model ,

$n$ Different balls , Put it in

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

The first

$1$ A box for

n_1

$n_{1}$ A ball , The first

$2$ A box for

n_2

$n_{2}$ A ball ,

⋯

\cdots

$\dots$ , The first

$t$ A box for

n_t

$n_{t}$ A ball Number of alternatives ;

Equivalent to multi-step processing :

The first $1 1 n 1 n_1 A ball , Put it in The first 1 1 In a box ; The selection methods are ( n n 1 ) \dbinom{n}{n_1} Kind of ;$
$1$ Step : choice
The first $2 2 n 2 n_2 A ball , Put it in The first 2 2 In a box ; The selection methods are ( n − n 1 n 2 ) \dbinom{n-n_1}{n_2} Kind of ; ⋮ \vdots$
$2$ Step : choice
The first $t t n t n_t A ball , Put it in The first t t In a box ; The selection methods are ( n − n 1 − n 2 − ⋯ − n t − 1 n t ) \dbinom{n-n_1-n_2 - \cdots -n_{t-1}}{n_t} Kind of ;$
$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 :

(

)

(

−

)

(

−

⋯

−

)

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

Two 、 Polynomial coefficient identity

Polynomial theorem inference 3 :

∑

(

⋯

)

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

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

Full Permutation of multiple sets :

(

⋯

)

⋯

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

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

recursion :

(

⋯

)

(

−

(

−

)

⋯

)

(

−

(

−

)

⋯

)

(

−

⋯

(

−

)

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

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