| Main |
||||
| Applications |
Identities |
|||
| History |
FAQ |
Algorithms |
|
|
|
| Vandermonde's Convolution |
| The binomial coefficients tell us how many
ways we can choose k distinct objects from a set of n objects;
we can make the objects distinct by labeling them with the integers 1 through
n. We can also have separate subsets of objects, which
we could show by making the objects different colors, so that everything
in one subset would be red, another subset green, another blue, etc., until
every element is in one and only one subset. Now when we think of "n
choose k", we can see there are selection patterns that can be sorted
together naturally based on how many red, how many green, how many blue,
etc. For example, let's say there are seven scholarships that are going to be parcelled out among the eleven starting players on the offense of a college football team. The number "11 choose 7" = C(11, 7) = 330, so there are 330 different possible combinations. But the coaches have decided to split the players on offense into three sub-groups, the 3 backs, the 3 ends and the 5 linemen. Moreover, it has been decided that 2 scholarships will go to the backs, 2 more will go to the ends and remaining 3 will go to the linemen. With these restrictions, there are now only C(3,2)×C(3,2)×C(5,3) = 3×3×10 = 90 combinations. The applet allows you to create a set with up to six elements of red, six elements of green and six elements of blue; you can then select the number of objects you want to choose out of the created set, and the program will tell you how many different selections exist and how many of each color pattern exist. A simple generalization of Vandemonde's Convolution tells what is obvious combinatorially, that the sum of the numbers from every possible combination of colors must be the binomial coefficient C(n,k). This can seen in the identity below, which is Cat. #3100017 in our table of identities. (Vandemonde's Convolution only states this result about sets split into two equivalence classes.) This identity was communcated to us by Andrés Masegosa, but we give it in the form in which it is found in Concrete Mathematics. |
|
Instructions for the applet: The first three slider bars let you pick respectively how many red, green and blue objects will make up your set; the last slider bar lets you pick how many objects you want to pick from the set. To show the example of football players and scholarships from above, you could let red = 3, green = 3 and blue = 5, and number of objects chosen = 7. Under the large binomial coefficient, every legal combination of seven red, green and blue objects is shown and beside it is the number of different ways that particular combination can be done. When the number of objects to be chosen is greater than the size of the set, there is no way to do this, so the binomial coefficient is zero. When the number of objects to be chosen is zero, there is only one way to do this; you will get nothing and like it. It's fun to set the red, green and blue numbers to some positive values, then click on the slider bar for # of objects chosen to see the nuber of possible patterns first increase, then start to contract as k gets closer to n then finally surpasses it. |