[combinatorial mathematics] binomial theorem and combinatorial identity (binomial theorem | three combinatorial identities | recursive formula 1 | recursive formula 2 | recursive formula 3 Pascal / Ya

One 、 binomial theorem

---

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

Two 、 Combinatorial identity ( recursion 1 )

---

(

n

k

)

=

(

n

n

−

k

)

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

(kn​)=(n−kn​)

Combination analysis method :

(

n

k

)

\dbinom{n}{k}

(kn​) Is to seek

k

k

k Subset selection method ,

(

n

n

−

k

)

\dbinom{n}{n-k}

(n−kn​) Is to seek

n

−

k

n-k

n−k Selection method of subset , There is a one-to-one correspondence between the two ;

In general ,

(

n

k

)

\dbinom{n}{k}

(kn​) Next item of , Not more than half of the above ;
If appear

(

10

8

)

\dbinom{10}{8}

(810​) , I can write this as

(

10

2

)

\dbinom{10}{2}

(210​)

3、 ... and 、 Combinatorial identity ( 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​)

The formula of substituting the combinatorial number , You can get Equal sign

=

=

= The values on both sides are equal ;

This formula is used to eliminate the coefficient , Examples are as follows :

Calculation

∑

k

=

0

n

k

(

n

k

)

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

k=0∑n​k(kn​) combined :

At this time, it needs to be eliminated

k

k

k coefficient ;

Use

n

k

(

n

−

1

k

−

1

)

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

kn​(k−1n−1​) Instead of

(

n

k

)

\dbinom{n}{k}

(kn​) , There is the following calculation process :

∑

k

=

0

n

k

(

n

k

)

=

∑

k

=

0

n

k

n

k

(

n

−

1

k

−

1

)

\begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} = \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \end{array}

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

You can add

k

k

k About , here

n

n

n It has nothing to do with summing variables , Now you can put

n

n

n Extract the addition symbol

∑

\sum

∑ outside ,

∑

k

=

0

n

k

(

n

k

)

=

∑

k

=

0

n

k

n

k

(

n

−

1

k

−

1

)

=

n

∑

k

=

0

n

(

n

−

1

k

−

1

)

\begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} &=& \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \\\\ &=& n \sum\limits_{k=0}^n \dbinom{n - 1}{k - 1} \end{array}

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

And then calculate

∑

k

=

0

n

(

n

−

1

k

−

1

)

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

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

Binomial theorem is :

(

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

According to the binomial theorem , You can get

(

1

+

1

)

n

=

∑

k

=

0

n

(

n

k

)

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

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

deduction :

(

1

+

1

)

n

−

1

=

∑

k

=

0

n

−

1

(

n

−

1

k

−

1

)

=

2

n

−

1

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

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

Then you can continue the subsequent calculation ;

Four 、 Combinatorial identity ( 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​)

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 ;

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 ;

The formula is proved by using the method of combinatorial analysis :

take

n

n

n Meta set selection

k

k

k A subset of , This is the number of set combinations ;

Specify one of the elements

a

a

a ;

① contain

a

a

a Elements :

k

k

k The subset contains

a

a

a The number of combinations of elements by

(

n

−

1

k

−

1

)

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

(k−1n−1​) ,

k

k

k The subset contains

a

a

a , Just divide

a

a

a Out of element , The rest

n

−

1

n-1

n−1 Of the elements , elect

k

−

1

k-1

k−1 Just one element ;

② It doesn't contain

a

a

a Elements :

k

k

k Subset does not contain

a

a

a The number of combinations of elements by

(

n

−

1

k

)

\dbinom{n - 1}{k}

(kn−1​) ,

k

k

k Subset does not contain

a

a

a , Just divide

a

a

a Out of element , The rest

n

−

1

n-1

n−1 Of the elements , elect

k

k

k Just one element ;

5、 ... and 、 Combination analysis method

---

Prove with the above Pascal / Yang hui triangle Take the formula as an example

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 collection :$n$
• Specify elements : A particular element $a$
• Specify the counting problem :
  • ① problem 1 :$n$
  • ② problem 2 :$n$

6、 ... and 、 Characteristics of recursive combinatorial identities

---

Use A relatively small number of combinations Express Relatively large number of combinations , It is called recursive combinatorial identity ;