Unizor - Combinatorics - Problem 2.9 - Vandermonde Identity
Вставка
- Опубліковано 17 гру 2024
- Unizor - Creative Minds through Art of Mathematics - Math4Teens
Notes to a video lecture on 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):
(m+n)C(r) = Σi∈[0,r](m)C(i)·(n)C(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 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).
etc.
Some groups would have r−1 men (and, correspondingly, 1 woman).
Finally, some groups will have r men (and, correspondingly, 0 women).
The number of groups counted separately by the number of men and women should be equal to the number (m+n)C(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 (m)C(i).
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 (n)C(r−i) of them). So, the total number of groups composed of i men and r−i women equals to
(m)C(i)·(n)C(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 (m+n)C(r) of r people out of all m+n available that we calculated in the beginning:
Σi∈[0,r](m)C(i)·(n)C(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](k)C(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](m)C(i)·x^i
(b) a=1, b=x, k=n:
(1+x)^n = Σi∈[0,n](n)C(i)·x^i
(c) a=1, b=x, k=m+n:
(1+x)^(m+n) = Σi∈[0,m+n](m+n)C(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](m+n)C(i)·x^i
and the product of
Σi∈[0,m](m)C(i)·x^i by
Σi∈[0,n](n)C(i)·x^i
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 at x 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 x^r equals to (m+n)C(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^0 from the first and x^r from the second (with their corresponding coefficients (m)C(0) and (n)C(r)) AND
take x^1 from the first and x^(r−1) from the second (with their coefficients (m)C(1) and (n)C(r−1)) AND
take x^2 from the first and x^(r−2) from the second (with their coefficients (m)C(2) and (n)C(r−2)) AND etc.
take x^(r−1) from the first and x^1 from the second (with their coefficients (m)C(r−1) and (n)C(1)) AND, finally,
take x^r from the first and x^0 from the second (with their coefficients (m)C(r)r and (n)C(0))
and sum up all of these results getting x^r with a coefficient
Σi∈[0,r](m)C(i)·(n)C(r−i)
This coefficient at x^r of the product of two polynomials (1+x)^m and (1+x)^n should be equal to a coefficient (m+n)C(r) at x^r of the polynomial 1+x)^(m+n).
That proves Vandermonde's identity.
Hey, that was a great class. I really enjoyed it! Keep up the good work!
Thabjs, Keep up studying! And refer others to this Web site. We need more smart people.
Interesting identity. It reminds me of the proof 2^n=sum_{i=0}^{n} nCr(n,i). The first approach is like when you see the identity is like counting all different subsets of {1,2,...,n} and the second approach is like when you expand (1+1)^n using the binomial formula.
Yes, you are absolutely correct.
I hope, you take the whole course on unizor.com, it's absolutely free and has no advertising. There are also lectures there about US Law and Constitution by Jesse Brogan.
I am planning to start there a new course "Physics 4 Teens".
It has been proven that studying Mathematics makes people more creative, more logical, simply smarter. Please share this video with your friends to make humanity smarter.
This lecture is a part of the educational Web site UNIZOR.COM dedicated to presentation of advanced course of Mathematics and Physics for teenagers interested in studying these subjects as tools to develop their creativity, analytic thinking, logic and intelligence.
You're my hero. Sorry that the sirens distracted your video a bit.
Glad you liked it. Please, share information about UNIZOR.COM with your friends and teachers.
Just quick question. In the beginning, why did you have r on the top when the sample size is m+n and you choose r, so it should be nCr(m+n, r) rather than nCr(r, m+)?
You probably were reading the description on UA-cam instead of on UNIZOR.COM. Unfortunately, UA-cam description allows no fine editing capabilities. That's why I always recommend to watch the lecture on UNIZOR.COM and read description there. In this case poor editing capabilities of UA-cam description played the role.
I think, we have a difference in symbolics only, which is easy to reconcile.
The symbol for a number of combinations of p objects out of q available that I use is based on a standard to use capital C with p (number of elements in a selected group) as a top index and q (total number of possible choices) as a bottom index. Another notation is C(q,p) where the first argument is the total number of possible choices and the second - number of elements in the selected group. Yet another notation is to use parenthesis with total number of possible choices q inside on the top and selected group size p inside on the bottom. Finally, there is a notation qCp.
All are equivalent and are just a matter of preference.
Now about the real meaning. In the beginning I was talking about selecting a group of r people from a set of m+n people. So, my total number of possible choices is m+n, the size of a selected group is r, so I used m+n as the bottom index and r as a top one. Using your notation, it should be either C(m+n,r) or (m+n)Cr.
So is it possible to so do rC(m+n) for Vandermonde's Identity. Essentially flipping it upside down. IE Sum C(k, n)C(r-k, m).
Not sure, what you mean. The number of people in a group r must not be greater than the total number of people m+n. So, rC(m+n) is always zero and, actually, meaningless.
The correct Vandermonde's identity in text-friendly notation should be
C(m+n,r)=(m+n)Cr=SUM{C(n,k)*C(m,r-k)}=SUM{nCk*mC(r-k)}
Zor Shekhtman like this
i.imgur.com/kJgv8MT.jpg
Yes, this is exactly the same. The total number of possibilities on the bottom of the parenthesis and number of elements you select is on the top.
I like the proof and the explanation, but that is a ridiculous looking letter 'r'
Thanks for a comment. By the way, this is a correct writing of a cursive letter "r" - look at printableworksheets.in/worksheet/cursive-lowercase-r