Vandermonde's identity (or Vandermonde's convolution), named after Alexandre-Théophile Vandermonde, states that any combination of objects from a group of objects must have some objects from a group of objects and the remaining objects from a group of .
Mathematically, This identity can be useful when evaluating certain other sums, or doing difficult combinatorics problems.
We consider the binomial expansion of
Also, notice that, we can consider the expansion by observing that
Thus, we can conclude that the coefficient of in the above expansion is
Therefore, by comparing the coefficients of
Suppose there are boys and girls in a class and you're asked to form a team of pupils out of these students, with You can do this in ways. But, now we count in rather a different manner. To form the team, you can choose boys and girls for some fixed . There are ways to do this. Now, either you can have boys and girls, or boy and girls, or boys and girls, or . That is, there are ways to form the team.
Thus, we derive at our result
The above sum is a special case of Vandermonde's identity where
Thus, we get
Therefore, because of the identity , we get
I'll leave the combinatorial proof of this identity as an exercise for you to work out.
In the algebraic proof of the above identity, we multiplied out two polynomials to get our desired sum. Similarly, by multiplying out polynomials, you can get the generalized version of the identity, which is
You can also think of it combinatorially, by considering bags with each bag consisting of balls. Thus, you have a total of balls. Now you need to pick up balls in total. There are
ways to do it.
On a similar argument as stated above, we can also pick up balls by picking balls from bag #1, balls from bag #2, ..., and balls from bag #p. Thus for a fixed set of , there are ways to do it, and hence in total
This leads us to our desired result
Moving the LHS (in Vandermonde's identity) to RHS in the denominator yields
Each term in the above sum can be interpreted as a probability, that is, the probability distribution of the number of blue balls in draws without replacement from a bag containing blue and green balls. The resulting distribution is better known as hypergeometric probability distribution.
The identity was extended to non-integer arguments, by Wenchang Chu, and is known by the name Chu-Vandermonde Identity, which is stated as follows:
For general complex-valued and and any non-negative integer , it takes the form It can be re-written in terms of falling Pochhammer symbol as where and is known as the falling Pochhammer symbol (or descending factorial).
The Rothe-Hagen identity, named after Heinrich August Rothe and Johann Georg Hagen, is a further generalization of Vandermonde's identity, which extends for all complex numbers . It states that
Try the following problems:
As the well-known song goes, on the first day of Christmas my true love gave to me a partridge in a pear tree. On the second day of Christmas, my true love gave to me 2 turtle doves and a partridge in a pear tree. On day she gives me 1 of something, 2 of something else, ..., of something else. At the end of the first 16 days, how many gifts has my true love given to me in total?
At Peter's school, to progress to the next year, he has to pass an exam every summer. Every exam is out of 50 and the pass mark is always 25. To graduate from school, he must pass 10 exams. Since Peter's work ethic increases with age, his scores never decrease.
Let be the number of different series of marks Peter could have achieved, given that he left school without ever failing an exam. What are the last 3 digits of ?