当前位置：网站首页>[combinatorics] polynomial theorem (polynomial theorem | polynomial theorem proof | polynomial theorem inference 1 item number is the number of non negative integer solutions | polynomial theorem infe

[combinatorics] polynomial theorem (polynomial theorem | polynomial theorem proof | polynomial theorem inference 1 item number is the number of non negative integer solutions | polynomial theorem infe

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

List of articles

One 、 The polynomial theorem
Two 、 The polynomial theorem prove
3、 ... and 、 The polynomial theorem inference 1
Four 、 The polynomial theorem inference 2

One 、 The polynomial theorem

The polynomial theorem :

set up

$n$ As a positive integer ,

x_i

$x_{i}$ It's a real number ,

⋯

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

∑

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

The above polynomials have

$t$ The item , this

$t$ Items added

$n$ Power ;

Two 、 The polynomial theorem prove

In polynomials

(

⋯

)

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

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

Carry out the following processing step by step :

The first
1
1
$1$ Step : from
n
n
$n$ In a factor , choose
n
1
n_1
$n_{1}$ Personal factor , Each factor contributes
1
1
$1$ individual
x
1
x_1
$x_{1}$ , Total contribution
n
1
n_1
$n_{1}$ individual
x
1
x_1
$x_{1}$ , The selection methods are
(
n
n
1
)
\dbinom{n}{n_1}
$(n _{1} n)$ Kind of ;
The first
2
2
$2$ Step : from
n
−
n
1
n-n_1
$n - n_{1}$ In a factor , choose
n
2
n_2
$n_{2}$ Personal factor , Each factor contributes
1
1
$1$ individual
x
2
x_2
$x_{2}$ , Total contribution
n
2
n_2
$n_{2}$ individual
x
2
x_2
$x_{2}$ , The selection methods are
(
n
−
n
1
n
2
)
\dbinom{n-n_1}{n_2}
$(n _{2} n - n _{1})$ Kind of ;

⋮

\vdots

$⋮$

The first $t t n − n 1 − n 2 − ⋯ − n t − 1 n-n_1-n_2 - \cdots -n_{t-1} In a factor , choose n t n_t Personal factor , Each factor contributes 1 1 individual x t x_t , Total contribution n t n_t individual x t x_t , 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 : from

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

After deployment , Many can be asked out , The resulting :

⋯

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

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

Note that the above formula is the total permutation number of multiple sets

(

⋯

)

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

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

3、 ... and 、 The polynomial theorem inference 1

The polynomial theorem inference 1 :

In the above polynomial theorem , Different number of items It's the equation

⋯

n_1 + n_2 + \cdots + n_t = n

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

Number of nonnegative integer solutions

(

−

)

C(n + t -1 , n)

$C (n + t - 1, n)$

Proof process :

1 . The coefficient before each term

(

⋯

)

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

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

n
1
n_1
$n_{1}$ representative
x
1
x_1
$x_{1}$ The index of ,
n
1
n_1
$n_{1}$ Equivalent to how many formulas , When multiplying , Take it
x
1
x_1
$x_{1}$
n
2
n_2
$n_{2}$ representative
x
2
x_2
$x_{2}$ The index of ,
n
2
n_2
$n_{2}$ Equivalent to how many formulas , When multiplying , Take it
x
2
x_2
$x_{2}$

⋮

\vdots

$⋮$

$n_tnt representative x t x_txt The index of , n t n_tnt Equivalent to how many formulas , When multiplying , Take it x t x_txt$

2 . One-to-one correspondence :

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ A different set of choices , amount to

⋯

n_1 + n_2 + \cdots + n_t = n

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

A solution to , Corresponding to different

⋯

x_1 , x_2, \cdots, x_n

$x_{1}, x_{2}, \dots, x_{n}$ The previous item ;

Three corresponding relationships :

Different solutions ,

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ Different configuration , These items Number of different configurations ,

amount to

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = n$ Number of nonnegative integer solutions of ,

It is also equivalent to polynomial Expanded Number of items ;

So find

⋯

n_1 + n_2 + \cdots + n_t = n

$n_{1} + n_{2} + \dots + n_{t} = n$ Number of nonnegative integer solutions of ,

It corresponds to

⋯

n_1, n_2, \cdots , n_t

$n_{1}, n_{2}, \dots, n_{t}$ Number of different configurations ,

Corresponding Number of terms after polynomial expansion ,

The result is

(

−

)

C(n + t -1 , n)

$C (n + t - 1, n)$

This number is also the combinatorial number of multiple sets

Derivation process Refer to the multiple set combination problem :
Multiple sets :
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$
take
r
r
$r$ A combination of elements ,
r
≤
n
i
r \leq n_i
$r \leq n_{i}$ , The derivation process is as follows :

stay
k
k
$k$ Of the elements , take
r
r
$r$ Elements , Each element takes
0
∼
r
0 \sim r
$0 \sim r$ Different elements ,
Use
k
−
1
k-1
$k - 1$ Split by lines
k
k
$k$ The position of the elements ,
k
−
1
k - 1
$k - 1$ A dividing line is equivalent to
k
k
$k$ Boxes , Put... In each box
0
∼
r
0 \sim r
$0 \sim r$ Different elements ,
The total number of elements placed is
r
r
$r$ individual , The number of dividing lines is
k
−
1
k-1
$k - 1$ individual , Here comes a combinatorial problem , stay
k
−
1
k-1
$k - 1$ A split line and
r
r
$r$ Between elements , selection
r
r
$r$ Elements , Namely Of multiple sets
r
≤
n
i
r \leq n_i
$r \leq n_{i}$ Cases of Number of combinations ;
The result is :
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
$N = C (k + r - 1, r)$
Reference resources : 【 Combinatorial mathematics 】 Permutation and combination ( The combinatorial number of multiple sets | The repetition of all elements is greater than the number of combinations | The combinatorial number of multiple sets deduction 1 Division line derivation | The combinatorial number of multiple sets deduction 2 Derivation of the number of nonnegative integer solutions of indefinite equations )

Four 、 The polynomial theorem inference 2

The 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}$

Proof process :

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

If you will

⋯

x_1 = x_2 = \cdots = x_t = 1

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

You can get

(

⋯

)

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

$(1 + 1 + \dots + 1)^{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}1^{n_1}1^{n_2}\cdots 1^{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) 1^{n_{1}} 1^{n_{2}} \dots 1^{n_{t}}$