[combinatorics] combinatorial identity (sum of combinatorial identity products 1 | sum of products 1 proof | sum of combinatorial identity products 2 | sum of products 2 proof)

Combinatorial identity reference blog :

• 【 Combinatorial mathematics 】 Combinatorial identity ( Recurrence Combinatorial identity | Change the next term to sum Combinatorial identity Simple and | Change the next term to sum Combinatorial identity Staggered and )
• 【 Combinatorial mathematics 】 Combinatorial identity ( Change the next term to sum 3 Combinatorial identity | Change the next term to sum 4 Combinatorial identity | binomial theorem + Derivation Prove the combinatorial identity | Use known combinatorial identities to prove combinatorial identities )
• 【 Combinatorial mathematics 】 Combinatorial identity ( Review of eight combinatorial identities | Combinatorial identity product 1 | prove | Use scenarios )

One 、 Combinatorial identity ( Sum of product ) 1

---

Combinatorial identity ( Sum of product ) 1 :

∑

k

=

0

r

(

m

k

)

(

n

r

−

k

)

=

(

m

+

n

r

)

,

      

r

=

min

⁡

{

m

,

n

}

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

k=0∑r​(km​)(r−kn​)=(rm+n​),      r=min{ m,n}

Two 、 Combinatorial identity ( Sum of product ) 1 prove

---

1 . The combination analysis method uses : When using the combination analysis method to prove the combination number , Specify the set first , Specify elements , Specify two counting problems , On both sides of the formula are the counts of the same problem ;

( 1 ) Specify the collection : Specify the set in which the count is generated ;

( 2 ) Specify the counting problem : The following two counting problems are the counting of the same problem ;

• ① problem 1 : The left side of the equal sign represents the counting problem ;
• ② problem 2 : The right side of the equal sign represents the counting problem ;

( 3 ) Equivalent description : It shows that the two counting problems are the same ;

2 . Use Combinatorial analysis Method to prove :

( 1 ) Specify the collection : Define two sets ,

A

=

{

a

1

,

a

2

,

⋯
 

,

a

m

}

A = \{ a_1, a_2 , \cdots , a_m \}

A={ a1​,a2​,⋯,am​}

B

=

{

b

1

,

b

2

,

⋯
 

,

b

n

}

B = \{ b_1, b_2 , \cdots , b_n \}

B={ b1​,b2​,⋯,bn​}

( 2 ) Specify the count to the right of the equal sign :

(

m

+

n

r

)

\dbinom{m + n }{r}

(rm+n​) representative Count as follows :

From here Two sets of

m

+

n

m + n

m+n Of the elements , selection

r

r

r Elements , In this way, a selection problem is constructed ;

( 3 ) Specify the count to the left of the equal sign :

To the left of the equal sign Combinatorial number

∑

k

=

0

r

(

m

k

)

(

n

r

−

k

)

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k}

k=0∑r​(km​)(r−kn​) Count analysis :

First classification after Step by step : In the above formula , With product , There is a summation , It means that this is First classification ( The law of addition ) , Used in each category Step by step ( product rule ) Calculation ;

according to From two sets Elected by the

r

r

r Subset , How many

A

=

{

a

1

,

a

2

,

⋯
 

,

a

m

}

A = \{ a_1, a_2 , \cdots , a_m \}

A={ a1​,a2​,⋯,am​} The elements in the collection are classified ,

contain

A

A

A The elements in

k

k

k individual ,

The rest

r

−

k

r-k

r−k The element is taken from

B

=

{

b

1

,

b

2

,

⋯
 

,

b

n

}

B = \{ b_1, b_2 , \cdots , b_n \}

B={ b1​,b2​,⋯,bn​} aggregate ;

The logic of step-by-step processing is : First in

A

A

A Select from collection

k

k

k Elements , And then in

B

B

B Select from collection

r

−

k

r-k

r−k Elements ;

therefore

k

k

k Most take

r

r

r individual ( All from

A

A

A Take from set ) , Take the least

0

0

0 individual ( All from

B

B

B Take from set ) ;

( 4 ) The counts on the left and right sides of the above equation are the same , It's all in Take... From two sets

r

r

r The number of schemes per element ;

3、 ... and 、 Combinatorial identity ( Sum of product ) 2

---

Combinatorial identity ( Sum of product ) 2 :

∑

k

=

0

r

(

m

k

)

(

n

k

)

=

(

m

+

n

m

)

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}

k=0∑r​(km​)(kn​)=(mm+n​)

Four 、 Combinatorial identity ( Sum of product ) 2 prove

---

The formula is “ Combinatorial identity ( Sum of product ) 1” Special case of ,

It proves the above “ Combinatorial identity ( Sum of product ) 1” After formula , This formula is a corollary of the above formula ;

stay “ Combinatorial identity ( Sum of product ) 1” The formula

∑

k

=

0

r

(

m

k

)

(

n

r

−

k

)

=

(

m

+

n

r

)

,

      

r

=

min

⁡

{

m

,

n

}

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

k=0∑r​(km​)(r−kn​)=(rm+n​),      r=min{ m,n}

in , Make

r

=

n

r=n

r=n , It becomes a formula

∑

k

=

0

n

(

m

k

)

(

n

n

−

k

)

=

(

m

+

n

n

)

\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{n-k} = \dbinom{m + n }{n}

k=0∑n​(km​)(n−kn​)=(nm+n​)

(

n

n

−

k

)

\dbinom{n}{n-k}

(n−kn​) And

(

n

k

)

\dbinom{n}{k}

(kn​) It is equivalent. , So the formula can become :

∑

k

=

0

n

(

m

k

)

(

n

k

)

=

(

m

+

n

n

)

=

(

m

+

n

n

)

\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{n} =\dbinom{m + n }{n}

k=0∑n​(km​)(kn​)=(nm+n​)=(nm+n​)

therefore “ Combinatorial identity ( Sum of product ) 2” yes “ Combinatorial identity ( Sum of product ) 1” A special case of ;