https://youtu.be/fxrut5Rbke0

*Notes to a video lecture on http://www.unizor.com*

__Advanced Combinatorics - Problems 2.9.__

Try to solve these problems yourself and check against the answers that immediately follow each problem.

*Problem 1 - Vandermonde's identity*

Prove the following identity for any natural numbers

**,**

*m***and**

*n*

*r***)**

*r ≤ m+n***=**

*C*_{m+n}^{r}**Σ**

_{}*i*∈[

*0,r*]

**·**

*C*_{m}^{i}

*C*_{n}^{r−i}__Logic 1__(combinatorial):

Imagine, you have to pick a group of

**people from a set of**

*r***men and**

*m***women.**

*n*One obvious answer is direct usage of the formula for a number of combinations of

**objects from**

*r***objects, regardless of men/women composition in the group. The answer in this case is**

*m+n***, which is exactly an expression on the left of Vandermonde's identity.**

*C*_{m+n}^{r}On the other hand, we can differentiate groups by the number of men in them.

There are certain number of groups of

**people with**

*r***men (and, correspondingly,**

*0***women),**

*r−0*Then there are some groups with

**man (and, correspondingly,**

*1***women).**

*r−1*Some groups will have

**men (and, correspondingly,**

*2***women).**

*r−2*etc.

Some groups would have

**men (and, correspondingly,**

*r−1***woman).**

*1*Finally, some groups will have

**men (and, correspondingly,**

*r***women).**

*0*The number of groups counted separately by the number of men and women should be equal to the number

**for the total number of groups we came up with counting them without regard to men/women composition.**

*C*_{m+n}^{r}Let's determine now how many groups can be chosen with exactly

**men (and, correspondingly,**

*i***women) for each**

*r−i***from**

*i***to**

*0***and sum them up to get a total of groups of**

*r***people.**

*r*The number of groups of

**men out of all**

*i***men is**

*m***.**

*C*_{m}^{i}To each of these groups of

**(out of**

*i***) men we can add any group of**

*m***(out of**

*r−i***) women (there are**

*n***of them). So, the total number of groups composed of**

*C*_{n}^{r−i}**men and**

*i***women equals to**

*r−i***·**

*C*_{m}^{i}

*C*_{n}^{r−i}Summarizing this by the number of men in a group

**from**

*i***to**

*0***, we should get the total number of groups**

*r***of**

*C*_{m+n}^{r}**people out of all**

*r***available that we calculated in the beginning:**

*m+n***Σ**

_{}*i*∈[

*0,r*]

**·**

*C*_{m}^{i}

*C*_{n}^{r−i}The above is the right side of the Vandermonde's identity.

End of proof.

__Logic 2__(algebraic):

We will use Newton's binomial formula

**=**

*(a+b)*^{k}**Σ**

_{}*i*∈[

*0,k*]

**·**

*C*_{k}^{i}

*a*^{k−i}·b^{i}Let's use it for the following three cases.

(a)

**,**

*a=1***,**

*b=x***:**

*k=m***=**

*(1+x)*^{m}**Σ**

_{}*i*∈[

*0,m*]

*C*_{m}^{i}·x^{i}(b)

**,**

*a=1***,**

*b=x***:**

*k=n***=**

*(1+x)*^{n}**Σ**

_{}*i*∈[

*0,n*]

*C*_{n}^{i}·x^{i}(c)

**,**

*a=1***,**

*b=x***:**

*k=m+n***=**

*(1+x)*^{m+n}**Σ**

_{}*i*∈[

*0,m+n*]

*C*_{m+n}^{i}·x^{i}From obvious identity

**=**

*(1+x)*^{m+n}**·**

*(1+x)*^{m}

*(1+x)*^{n}we derive the corresponding equality between

**Σ**

_{}*i*∈[

*0,m+n*]

*C*_{m+n}^{i}·x^{i}and the product of

**Σ**

_{}*i*∈[

*0,m*]

**by**

*C*_{m}^{i}·x^{i}**Σ**

_{}*i*∈[

*0,n*]

*C*_{n}^{i}·x^{i}The first one is a polynomial of

*(m+n)*^{th}power. The second is a product of a polynomial of

*m*^{th }power by a polynomial of

*n*^{th }power, which is, in theory, also a polynomial of

*(m+n)*^{th}power. So, since they are equal for any argument

**, their coefficients at**

*x***at any particular power (from**

*x*

*0*^{th}to

*(m+n)*^{th}) should be the same.

The coefficients of the first polynomial are explicitly participating in the expression. Namely, for any

**∈**

*r***[**a coefficient at

*0,m+n*]**equals to**

*x*^{r}**.**

*C*_{m+n}^{r}Since we have to compare this with a coefficient of a product of two polynomials of powers

**and**

*m***with known coefficients, we have to come up with a coefficient of a product of two polynomials expressed in terms of coefficients of each one of them.**

*n*To obtain

**from a product of two polynomials, we can**

*x*^{r}take

**from the first and**

*x*^{0}**from the second (with their corresponding coefficients**

*x*^{r}**and**

*C*_{m}^{0}**) AND**

*C*_{n}^{r}take

**from the first and**

*x*^{1}**from the second (with their coefficients**

*x*^{r−1}**and**

*C*_{m}^{1}**) AND**

*C*_{n}^{r−1}take

**from the first and**

*x*^{2}**from the second (with their coefficients**

*x*^{r−2}**and**

*C*_{m}^{2}**) AND etc.**

*C*_{n}^{r−2}take

**from the first and**

*x*^{r−1}**from the second (with their coefficients**

*x*^{1}**and**

*C*_{m}^{r−1}**) AND, finally,**

*C*_{n}^{1}take

**from the first and**

*x*^{r}**from the second (with their coefficients**

*x*^{0}**and**

*C*_{m}^{r}**)**

*C*_{n}^{0}and sum up all of these results getting

**with a coefficient**

*x*^{r}**Σ**

_{}*i*∈[

*0,r*]

**·**

*C*_{m}^{i}

*C*_{n}^{r−i}This coefficient at

**of the product of two polynomials**

*x*^{r}**and**

*(1+x)*^{m}**should be equal to a coefficient**

*(1+x)*^{n}**at**

*C*_{m+n}^{r}**of the polynomial**

*x*^{r}**.**

*1+x)*^{m+n}That proves Vandermonde's identity.

## No comments:

Post a Comment