Wednesday, December 7, 2016

Unizor - Combinatorics - Problem 2.9 - Vandermonde Identity

Notes to a video lecture on

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 mn and r(where r ≤ m+n):
Cm+nr = Σi∈[0,r]Cmi·Cnr−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 objects from m+n objects, regardless of men/women composition in the group. The answer in this case is Cm+nr, 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).
Some groups would have r−1 men (and, correspondingly, woman).
Finally, some groups will haver men (and, correspondingly, women).

The number of groups counted separately by the number of men and women should be equal to the number Cm+nr 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 Cmi.
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 Cnr−i of them). So, the total number of groups composed of i men and r−i women equals to

Summarizing this by the number of men in a group from 0 to r, we should get the total number of groups Cm+nrof r people out of all m+n available that we calculated in the beginning:

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]Cki·ak−i·bi

Let's use it for the following three cases.
(a) a=1b=xk=m:
(1+x)m = Σi∈[0,m]Cmi·xi
(b) a=1b=xk=n:
(1+x)n = Σi∈[0,n]Cni·xi
(c) a=1b=xk=m+n:
(1+x)m+n = Σi∈[0,m+n]Cm+ni·xi

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

The first one is a polynomial of(m+n)th power. The second is a product of a polynomial of mth power by a polynomial of nth 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 0th 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 xr equals to Cm+nr.

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 xr from a product of two polynomials, we can
take x0 from the first and xrfrom the second (with their corresponding coefficients Cm0and Cnr) AND
take x1 from the first and xr−1from the second (with their coefficients Cm1 and Cnr−1) AND
take x2 from the first and xr−2from the second (with their coefficients Cm2 and Cnr−2) AND etc.
take xr−1 from the first and x1from the second (with their coefficients Cmr−1 and Cn1) AND, finally,
take xr from the first and x0from the second (with their coefficients Cmr and Cn0)
and sum up all of these results getting xr with a coefficient
This coefficient at xr of the product of two polynomials(1+x)m and (1+x)n should be equal to a coefficient Cm+nr at xr of the polynomial 1+x)m+n.
That proves Vandermonde's identity.

No comments: