Unizor - Combinatorics - Problem 2.9 - Vandermonde Identity

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, n and r(where r ≤ m+n):
C_m+n^r = Σi∈[0,r]C_mⁱ·C_n^r−i

Logic 1 (combinatorial):

Imagine, you have to pick a group of r people from a set of m men and n women.
One obvious answer is direct usage of the formula for a number of combinations of r objects from m+n objects, regardless of men/women composition in the group. The answer in this case is C_m+n^r, which is exactly an expression on the left of Vandermonde's identity.

On the other hand, we can differentiate groups by the number of men in them.
There are certain number of groups of r people with 0 men (and, correspondingly, r−0 women),
Then there are some groups with 1 man (and, correspondingly, r−1 women).
Some groups will have 2 men (and, correspondingly, r−2 women).
etc.
Some groups would have r−1 men (and, correspondingly, 1 woman).
Finally, some groups will haver men (and, correspondingly, 0 women).

The number of groups counted separately by the number of men and women should be equal to the number C_m+n^r for the total number of groups we came up with counting them without regard to men/women composition.

Let's determine now how many groups can be chosen with exactly i men (and, correspondingly, r−i women) for each i from 0 to r and sum them up to get a total of groups of r people.
The number of groups of i men out of all m men is C_mⁱ.
To each of these groups of i(out of m) men we can add any group of r−i (out of n) women (there are C_n^r−i of them). So, the total number of groups composed of i men and r−i women equals to
C_mⁱ·C_n^r−i

Summarizing this by the number of men in a group i from 0 to r, we should get the total number of groups C_m+n^rof r people out of all m+n available that we calculated in the beginning:
Σi∈[0,r]C_mⁱ·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ⁱ·a^k−i·bⁱ

Let's use it for the following three cases.
(a) a=1, b=x, k=m:
(1+x)^m = Σi∈[0,m]C_mⁱ·xⁱ
(b) a=1, b=x, k=n:
(1+x)ⁿ = Σi∈[0,n]C_nⁱ·xⁱ
(c) a=1, b=x, k=m+n:
(1+x)^m+n = Σi∈[0,m+n]C_m+nⁱ·xⁱ

From obvious identity
(1+x)^m+n = (1+x)^m·(1+x)ⁿ
we derive the corresponding equality between
Σi∈[0,m+n]C_m+nⁱ·xⁱ
and the product of
Σi∈[0,m]C_mⁱ·xⁱ by
Σi∈[0,n]C_nⁱ·xⁱ

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 x, their coefficients atx at any particular power (from 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∈[0,m+n] a coefficient at x^r equals to C_m+n^r.

Since we have to compare this with a coefficient of a product of two polynomials of powers m and n 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.
To obtain x^r from a product of two polynomials, we can
take x⁰ from the first and x^rfrom the second (with their corresponding coefficients C_m⁰and C_n^r) AND
take x¹ from the first and x^r−1from the second (with their coefficients C_m¹ and C_n^r−1) AND
take x² from the first and x^r−2from the second (with their coefficients C_m² and C_n^r−2) AND etc.
take x^r−1 from the first and x¹from the second (with their coefficients C_m^r−1 and C_n¹) AND, finally,
take x^r from the first and x⁰from the second (with their coefficients C_m^r and C_n⁰)
and sum up all of these results getting x^r with a coefficient
Σi∈[0,r]C_mⁱ·C_n^r−i
This coefficient at x^r of the product of two polynomials(1+x)^m and (1+x)ⁿ should be equal to a coefficient C_m+n^r at x^r of the polynomial 1+x)^m+n.
That proves Vandermonde's identity.