[combinatorics] summary of combinatorial identities (eleven combinatorial identities | proof methods of combinatorial identities | summation methods)*

Combinatorial identity reference blog :

• 【 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 )
• 【 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 )
• 【 Combinatorial mathematics 】 Combinatorial identity ( Combinatorial identity Sum of product 1 | Sum of product 1 prove | Combinatorial identity Sum of product 2 | Sum of product 2 prove )

One 、 Eleven combinatorial identities

---

1 . Combinatorial identity ( recursion ) :

( 1 ) recursion 1 :

(

n

k

)

=

(

n

n

−

k

)

\dbinom{n}{k} = \dbinom{n}{n-k}

(kn​)=(n−kn​)①

( 2 ) recursion 2 :

(

n

k

)

=

n

k

(

n

−

1

k

−

1

)

\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}

(kn​)=kn​(k−1n−1​)②

( 3 ) recursion 3 ( Pascal / Yang Hui's trigonometric formula ) :

(

n

k

)

=

(

n

−

1

k

)

+

(

n

−

1

k

−

1

)

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

(kn​)=(kn−1​)+(k−1n−1​)③

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

3 . Change the upper term to sum :

∑

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​)⑧

4 . product :

∑

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​)⑨

5 . 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}⑩

( 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​)⑪

Two 、 Combinatorial identity Method of proof

---

1 . Known combinatorial identities are substituted into : Known

11

11

11 A combinatorial identity is substituted into

2 . binomial theorem

n

n

n It's a positive integer. , For everything

x

x

x and

y

y

y , There are the following theorems :

(

x

+

y

)

n

=

∑

k

=

0

n

(

n

k

)

x

k

y

n

−

k

(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}

(x+y)n=k=0∑n​(kn​)xkyn−k

(

n

k

)

\dbinom{n}{k}

(kn​) Express

n

n

n Yuan centralized retrieval

k

k

k Number of combinations of elements , yes Number of sets

C

(

n

,

k

)

C(n,k)

C(n,k) Another way of writing ;

Another common form (

y

=

1

y = 1

y=1 ) :

(

1

+

x

)

n

=

∑

k

=

0

n

(

n

k

)

x

k

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

(1+x)n=k=0∑n​(kn​)xk

Basic summation formula (

x

=

y

=

1

x = y =1

x=y=1 ) :

2

n

=

∑

k

=

0

n

(

n

k

)

2^n = \sum_{k=0}^n \dbinom{n}{k}

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

3 . Derivation of power series 、 integral

Derivation of power function : ( Very important )

• Primitive function :

  y

  =

  x

  n

  y = x^n

  y=xn

• Corresponding derivative :

  y

  ′

  =

  n

  x

  n

  −

  1

  y' = nx^{n-1}

  y′=nxn−1

The derivative of a constant is

0

0

0 ;

Four operations of derivative :

(

u

±

v

)

′

=

u

′

±

v

′

(u \pm v)' = u' \pm v'

(u±v)′=u′±v′

Reference resources :

• derivative - Baidu Encyclopedia
• Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1 prove ( binomial theorem + Derivation )

4 . Induction

Mathematical induction describe A proposition related to natural numbers

P

(

n

)

P(n)

P(n) ,

According to different questions , Set up

n

n

n The minimum value , Usually from

0

0

0 Start ,

( 1 ) The proof is divided into the following two steps :

① Inductive basis : First prove that Inductive basis , If it is proved that

P

(

0

)

P(0)

P(0) It's true ;

② Induction steps : according to Types of mathematical induction , Prove in different ways , Here you are First, mathematical induction and Second, mathematical induction Two kinds of induction ;

( 1 ) Mathematical induction :

① First, mathematical induction : from

P

(

n

)

P(n)

P(n) deduction

P

(

n

+

1

)

P(n + 1)

P(n+1)

P

(

0

)

P(0)

P(0) It's true

hypothesis

P

(

n

)

P(n)

P(n) It's true , prove

P

(

n

+

1

)

P(n + 1)

P(n+1) It's true

② Second, mathematical induction : All less than

n

n

n Of

P

(

0

)

,

P

(

1

)

,

⋯
 

,

P

(

n

−

1

)

P(0) , P(1), \cdots , P(n-1)

P(0),P(1),⋯,P(n−1) It's all true , deduction

P

(

n

)

P(n)

P(n) It's true ;

P

(

0

)

P(0)

P(0) It's true

Assume that all are less than

n

n

n The natural number of

k

k

k , proposition

P

(

k

)

P(k)

P(k) It's all true , namely

P

(

0

)

,

P

(

1

)

,

⋯
 

,

P

(

n

−

1

)

P(0) , P(1), \cdots , P(n-1)

P(0),P(1),⋯,P(n−1) It's all true , deduction

P

(

n

)

P(n)

P(n) It's true ;

Symbolized as :

P

(

0

)

∧

P

(

1

)

∧

⋯

∧

P

(

n

−

1

)

→

P

(

n

)

P(0) \land P(1) \land \cdots \land P(n-1) \to P(n)

P(0)∧P(1)∧⋯∧P(n−1)→P(n)

Reference resources : 【 Combinatorial mathematics 】 Introduction to combinatorics ( Combination thought 2 : Mathematical induction | Generalization of mathematical induction | Multiple inductive thoughts )

5 . Combinatorial analysis

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 ;

Reference resources :

• 【 Combinatorial mathematics 】 Combinatorial identity ( Combinatorial identity Sum of product 1 | Sum of product 1 prove | Combinatorial identity Sum of product 2 | Sum of product 2 prove ) Two 、 Combinatorial identity ( Sum of product ) 1 prove

The above proof method , According to specific certification requirements , Choose the appropriate proof method ;

3、 ... and 、 Combinatorial number Sum up $\sum$

---

For formulas containing combinatorial numbers Sum up

∑

\sum

∑ Method

1 . Use Pascal formula :

recursion 3 ( Pascal / Yang Hui's trigonometric formula ) :

(

n

k

)

=

(

n

−

1

k

)

+

(

n

−

1

k

−

1

)

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

(kn​)=(kn−1​)+(k−1n−1​)③

( 1 ) Merge item :

(

n

k

)

\dbinom{n}{k}

(kn​) Can be reduced to

(

n

−

1

k

)

+

(

n

−

1

k

−

1

)

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

(kn−1​)+(k−1n−1​) The sum of the ;

( 2 ) This recursion , Used to split items :

Can be

(

n

k

)

\dbinom{n}{k}

(kn​) Split into

(

n

−

1

k

)

+

(

n

−

1

k

−

1

)

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

(kn−1​)+(k−1n−1​) The sum of the ; In actual use , Often encounter some items listed , Yes

(

n

−

1

k

)

+

(

n

−

1

k

−

1

)

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

(kn−1​)+(k−1n−1​) The number of combinations of forms , Can be merged into one

(

n

k

)

\dbinom{n}{k}

(kn​) ;

( 3 ) It can also be used by deformation , Put one of them , Become the difference between two of them ;

take

(

n

−

1

k

)

\dbinom{n - 1}{k}

(kn−1​) Split into

(

n

k

)

−

(

n

−

1

k

−

1

)

\dbinom{n}{k} -\dbinom{n - 1}{k - 1}

(kn​)−(k−1n−1​) The difference between the ;

take take

(

n

−

1

k

−

1

)

\dbinom{n - 1}{k - 1}

(k−1n−1​) Split into

(

n

k

)

−

(

n

−

1

k

)

\dbinom{n}{k} -\dbinom{n - 1}{k}

(kn​)−(kn−1​) The difference between the ;

In a stack of summation combinatorial numbers , Split into the difference between two numbers , Can offset many combinations ;

It is often used for simplification in large sum formulas ;

2 . Sum of series :

3 . Observations and results , Prove by mathematical induction :

Guess the result of a sum , Then use induction to prove ;

4 . Use the known formula to sum :