[combinatorics] combinatorial identity (sum of variable upper terms 1 combinatorial identity | summary of three combinatorial identity proof methods | proof of sum of variable upper terms 1 combinator

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 )

Review the combinatorial identities of summation under four variables : The combinatorial identity introduced earlier The number of combinations in

(

n

k

)

\dbinom{n}{k}

(kn​) , Is the next item

k

k

k Have been accumulating changes , have

∑

k

=

0

n

\sum\limits_{k=0}^{n}

k=0∑n​ Cumulative property , Previous item

n

n

n It is the same. ;

( 1 ) Simple and :

∑

k

=

0

n

(

n

k

)

=

2

n

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

k=0∑n​(kn​)=2n

( 2 ) Staggered and :

∑

k

=

0

n

(

−

1

)

k

(

n

k

)

=

0

\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0

k=0∑n​(−1)k(kn​)=0

( 3 ) Change the next term to sum 3 :

∑

k

=

0

n

k

(

n

k

)

=

n

2

n

−

1

\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

k=0∑n​k(kn​)=n2n−1

( 4 ) Change the next term to sum 4 :

∑

k

=

0

n

k

2

(

n

k

)

=

n

(

n

+

1

)

2

n

−

2

\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}

∑k=0n​k2(kn​)=n(n+1)2n−2

One 、 Combinatorial identity ( Change the upper term to sum 1 )

---

Change the upper term to sum 1 :

∑

l

=

0

n

(

l

k

)

=

(

n

+

1

k

+

1

)

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

l=0∑n​(kl​)=(k+1n+1​)

In the above formula , Combinatorial number

(

l

k

)

\dbinom{l}{k}

(kl​) in , Next

k

k

k It is the same. , Previous item

l

l

l It's always changing , Its value range is

0

0

0 ~

n

n

n ;

Several terms in this expression are

0

0

0 :

• When $l<k$
• When $l=k$
• When $l>k$

  1 Value ;

Two 、 Proof method of combinatorial identity ( Three )

---

1 . Method of proof : Two methods of proof have been used before , ① binomial theorem + Derivation , ② Use existing combinatorial identities to derive ;

The third kind of proof method is used here , ③ Combinatorial analysis , The method of combinatorial analysis is to construct a combinatorial counting problem , On the left and right are the solutions of the same counting problem ;

2 . 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 ;

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 ;

Reference resources : 【 Combinatorial mathematics 】 Binomial theorem and combinatorial identities ( binomial theorem | Three combinatorial identities recursion | recursion 1 | recursion 2 | recursion 3 Pascal / Yang Hui's trigonometric formula | Combination analysis method | Characteristics of recursive combinatorial identities ) 5、 ... and 、 Combination analysis method

3 . Summary of the use of combinatorial analysis methods : 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 ;

3、 ... and 、 Combinatorial identity ( Change the upper term to sum 1 ) prove

---

Now start to construct the selection problem :

1 . Specify the collection : Suppose there is

n

+

1

n+1

n+1 Collection of elements , Write it down as

S

=

{

a

1

,

a

2

,

⋯
 

,

a

n

+

1

}

S = \{ a_1 , a_2 , \cdots , a_{n+1} \}

S={ a1​,a2​,⋯,an+1​} ,

2 . Specify the counting problem to the right of the equal sign : From the above set

S

S

S in , selection

k

+

1

k+1

k+1 A subset of elements , The number of selection methods is

(

n

+

1

k

+

1

)

\dbinom{n + 1}{k+1}

(k+1n+1​) individual ;

3 . Specify the counting problem to the left of the equal sign : To the left of the equal sign is

∑

l

=

0

n

(

l

k

)

\sum\limits_{l=0}^{n} \dbinom{l}{k}

l=0∑n​(kl​) ;

Determine the type of counting problem ( Select by category ) : There is And no.

∑

\sum

∑ , This indicates that the counting problem adopts Classification and counting principle , Corresponding addition rule ; The counting problem must be classification selection ;

S

S

S aggregate , from

n

+

1

n+1

n+1 Of the elements

k

+

1

k+1

k+1 Elements ;

( 1 ) The first

1

1

1 class , Specify a specific element

a

1

a_1

a1​ , The subset must contain

a

1

a_1

a1​ , Only from the rest

n

n

n Of the elements

k

k

k individual , The number of options is

(

n

k

)

\dbinom{n}{k}

(kn​) ;

( 2 ) The first

2

2

2 class , And The first

1

1

1 Classes do not overlap ,
Not included

a

1

a_1

a1​ , But it must contain

a

2

a_2

a2​ ,
Not included

a

1

a_1

a1​ Then it's from

n

n

n Of the elements ( from

n

+

1

n+1

n+1 Remove one of the elements ) ,
Must contain

a

2

a_2

a2​ ( from

n

n

n Remove one more element , namely

n

−

1

n - 1

n−1 individual ) , Then it's from

n

−

1

n-1

n−1 Of the elements

k

k

k Elements ,
The end result is

(

n

−

1

k

)

\dbinom{n-1}{k}

(kn−1​)

( 3 ) The first

3

3

3 class , And The first

1

,

2

1,2

1,2 Classes do not overlap ,
Not included

a

1

,

a

2

a_1, a_2

a1​,a2​ , But it must contain

a

3

a_3

a3​ ,
Not included

a

1

,

a

2

a_1, a_2

a1​,a2​ Then it's from

n

−

1

n-1

n−1 Of the elements ( from

n

+

1

n+1

n+1 Remove

2

2

2 individual , namely

n

−

1

n-1

n−1 ) ,
Must contain

a

3

a_3

a3​ ( from

n

−

1

n-1

n−1 Remove one more element , namely

n

−

2

n - 2

n−2 individual ) , Then it's from

n

−

2

n-2

n−2 Of the elements

k

k

k Elements ,
The end result is

(

n

−

2

k

)

\dbinom{n-2}{k}

(kn−2​)

⋮

\vdots

⋮

( 4 ) The first

n

+

1

n + 1

n+1 class , And The first

1

,

2

,

⋯
 

,

n

1,2, \cdots , n

1,2,⋯,n Classes do not overlap ,
Not included

a

1

,

a

2

,

a

3

,

⋯
 

,

a

n

a_1, a_2 , a_3 , \cdots , a_n

a1​,a2​,a3​,⋯,an​ , But it must contain

a

n

+

1

a_{n+1}

an+1​ ,
Not included

a

1

,

a

2

,

a

3

,

⋯
 

,

a

n

a_1, a_2 , a_3 , \cdots , a_n

a1​,a2​,a3​,⋯,an​ Then it's from

1

1

1 Of the elements ( from

n

+

1

n+1

n+1 Remove

n

n

n individual , namely

1

1

1 ) ,
Must contain

a

n

+

1

a_{n+1}

an+1​ ( from

1

1

1 Remove one more element , namely

0

0

0 individual ) , Then it's from

0

0

0 Of the elements

k

k

k Elements ,
The end result is

(

0

k

)

\dbinom{0}{k}

(k0​)

5 . The above two counting problems are the same counting problem , from

n

+

1

n+1

n+1 Of the elements

k

+

1

k+1

k+1 Elements ;