[combinatorics] combinatorial identities (review of eight combinatorial identities | product of combinatorial identities 1 | proof | use scenario | general method for finding combinatorial numbers)

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 )

One 、 Review of combinatorial identities ( 8 individual )

---

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

Two 、 Combinatorial identity ( product )

---

Combinatorial identity ( product ) :

(

n

r

)

(

r

k

)

=

(

n

k

)

(

n

−

k

r

−

k

)

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

(rn​)(kr​)=(kn​)(r−kn−k​)

3、 ... and 、 Combinatorial identity ( product ) prove

---

1 .

(

n

r

)

(

r

k

)

\dbinom{n}{r}\dbinom{r}{k}

(rn​)(kr​) Combinatorial number analysis : This is the multiplication of two combinatorial numbers , It uses Step by step counting principle , Corresponding multiplication rule ;

( 1 ) First step :

(

n

r

)

\dbinom{n}{r}

(rn​) from

n

n

n Of the elements

r

r

r Elements ;

( 2 ) The second step :

(

r

k

)

\dbinom{r}{k}

(kr​) from

r

r

r Of the elements

k

k

k Elements ;

2 . The above choices may be repeated , The following counterexample can prove :

aggregate

S

=

{

a

,

b

,

c

,

d

,

e

}

S = \{ a, b, c, d, e \}

S={ a,b,c,d,e} , From this set

S

S

S Choose from

4

4

4 Elements , Two chestnuts :

①

{

a

,

b

,

c

,

d

}

\{a, b, c, d\}

{ a,b,c,d} , There are subsets

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d}

②

{

b

,

c

,

d

,

e

}

\{ b,c,d,e \}

{ b,c,d,e} , There are subsets

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d}

So from

5

5

5 Of the elements

4

4

4 individual , And then from

4

4

4 Of the elements

3

3

3 individual , Last There is a case of selecting duplicate subsets , There are two repetitions

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d} ;

3 .

(

n

k

)

(

n

−

k

r

−

k

)

\dbinom{n }{k}\dbinom{n-k}{r-k}

(kn​)(r−kn−k​) Combinatorial number analysis :

(

n

k

)

\dbinom{n }{k}

(kn​) Express from

n

n

n Of the elements , Directly select

k

k

k Elements come out , See how many methods there are ; chestnuts : Above

5

5

5 Direct selection in meta set

3

3

3 Number of element subsets ;

(

n

−

k

r

−

k

)

\dbinom{n-k}{r-k}

(r−kn−k​) yes The repeatability of the above selection method , How many times does each selection method appear ; chestnuts : Calculate each of the above

3

3

3 The number of repetitions of the element subset selection scheme ;

4 . Now let's start to study the above

(

n

−

k

r

−

k

)

\dbinom{n-k}{r-k}

(r−kn−k​) How is the repeatability calculated

Take the chestnuts above for example ,

3

3

3 A subset of

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d} The reason why it happened twice is ,

stay

4

4

4 A subset of

{

a

,

b

,

c

,

d

}

\{a, b, c, d\}

{ a,b,c,d} and

{

b

,

c

,

d

,

e

}

\{ b,c,d,e \}

{ b,c,d,e} All contain the same

3

3

3 A subset of

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d} ,

In the above

4

4

4 Subsets , except

3

3

3 Outside the subset , There are other added elements ,

• stay $\{a,b,c,d\}$

  a Elements

• stay $\{b,c,d,e\}$

  e Elements

stay

3

3

3 Subsets , Add different elements , It can become Different

4

4

4 A subset of , Here we directly ask for

3

3

3 How many ways to add subsets , constitute

4

4

4 Number of subsets ;

The added element is from The original

S

=

{

a

,

b

,

c

,

d

,

e

}

S = \{ a, b, c, d, e \}

S={ a,b,c,d,e} Collection , Get rid of

{

b

,

c

,

d

}

\{ b,c,d \}

{ b,c,d}

3

3

3 Selected from the elements after the subset ,

The selected set has

5

−

3

=

2

5-3 = 2

5−3=2 Elements ( It's equivalent to a formula

n

−

k

n-k

n−k ) ,

The number selected is

4

−

3

=

1

4-3=1

4−3=1 individual ( It's equivalent to a formula

r

−

k

r-k

r−k ) ;

from

n

−

k

n-k

n−k Of the elements

r

−

k

r-k

r−k Elements , The number of programmes is

(

n

−

k

r

−

k

)

\dbinom{n-k}{r-k}

(r−kn−k​) ;

5 .

(

n

r

)

(

r

k

)

=

(

n

k

)

(

n

−

k

r

−

k

)

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

(rn​)(kr​)=(kn​)(r−kn−k​) The left and right sides of are the counting results of the same combined number , So it's equal

Four 、 Combinatorial identity ( product ) purpose 、 A general method for finding combinatorial numbers

---

Combinatorial identity ( product ) :

(

n

r

)

(

r

k

)

=

(

n

k

)

(

n

−

k

r

−

k

)

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

(rn​)(kr​)=(kn​)(r−kn−k​)

encounter

(

n

r

)

(

r

k

)

\dbinom{n}{r}\dbinom{r}{k}

(rn​)(kr​) Product first , The case of re summation , If the sum is right

r

r

r Words of peace , namely

∑

r

=

0

n

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

r=0∑n​ , as follows :

Yes

∑

r

=

k

n

(

n

r

)

(

r

k

)

\sum\limits_{r=k}^{n}\dbinom{n}{r}\dbinom{r}{k}

r=k∑n​(rn​)(kr​) Sum up ;

Yes

r

r

r Sum up ,

r

r

r It's from

k

k

k Until

n

n

n ,

Previous items

(

n

r

)

\dbinom{n}{r}

(rn​) Next is the variable ,

The following items

(

r

k

)

\dbinom{r}{k}

(kr​) The last item is a variable ,

The previous general method : This makes it impossible to use the previous calculation method , The previous calculation method is , Constant to

∑

\sum

∑ Extract outside the symbol , The rest turns into Basic summation

∑

k

=

0

n

(

n

k

)

=

2

n

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

k=0∑n​(kn​)=2n , Or known Combinatorial identity , Combination formula , To simplify ;

How to deal with the situation : Two combinatorial numbers , One is that the next item is the cumulative variable , One is that the previous term is an additive variable , Multiply two combinatorial numbers The situation of ;

Above The product combination identity can change the above situation into Next Is the case of cumulative variables ;

Use the above Product combinatorial identity , Turn into :

∑

r

=

k

n

(

n

r

)

(

r

k

)

=

∑

r

=

k

n

(

n

k

)

(

n

−

k

r

−

k

)

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

r=k∑n​(rn​)(kr​)=r=k∑n​(kn​)(r−kn−k​)

After obtaining the above formula , Items obtained by analysis

∑

r

=

k

n

(

n

k

)

(

n

−

k

r

−

k

)

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

r=k∑n​(kn​)(r−kn−k​) ,

Ahead

(

n

k

)

\dbinom{n }{k}

(kn​) Item and Summation variables

r

r

r irrelevant ,

hinder

(

n

−

k

r

−

k

)

\dbinom{n-k}{r-k}

(r−kn−k​) The next item is related to Summation variables

r

r

r relevant ;

therefore

(

n

k

)

\dbinom{n }{k}

(kn​) term You can extract

∑

\sum

∑ Outside the symbol ;

=

(

n

k

)

∑

r

=

k

n

(

n

−

k

r

−

k

)

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

=(kn​)r=k∑n​(r−kn−k​)

The above formula can be used Variable limit , Substitution calculation ; Use

r

′

=

r

−

k

r' = r-k

r′=r−k Replace

r

r

r ;

original

r

r

r The range of phi is zero

k

k

k ~

n

n

n , be

r

′

=

r

−

k

r' = r-k

r′=r−k The range of phi is zero

0

0

0 ~

n

−

k

n-k

n−k , The substitution result is as follows :

=

(

n

k

)

∑

r

′

=

0

n

−

k

(

n

−

k

r

′

)

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

=(kn​)r′=0∑n−k​(r′n−k​)

according to Basic summation

∑

k

=

0

n

(

n

k

)

=

2

n

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

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

∑

r

′

=

0

n

−

k

(

n

−

k

r

′

)

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

r′=0∑n−k​(r′n−k​) As the result of the

2

n

−

k

2^{n-k}

2n−k ; The final calculation result is :

=

(

n

k

)

∑

r

′

=

0

n

−

k

(

n

−

k

r

′

)

=

2

n

−

k

(

n

k

)

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

=(kn​)r′=0∑n−k​(r′n−k​)=2n−k(kn​)