A binomial identity
I'm trying to give a combinatorial proof of the following identity:
On the right side, is the number of -element subsets of a -element set, or the number of ways we can select different balls from a box containing balls...
The left side doesn't seem so straightforward. Let's say we have an -element set, and we wish to find the number of ways we can form a -element subset, where , and the number of ways we can pick a subset of that newly-formed -element set.
As a -element set has subsets, we can do this procedure in ways, for some .
But the next factor, is totally baffling. I'm not even sure that the above interpretation is correct. And the next problem would be to show that the whole left side of the problem, in fact, equals .
Many thanks in advance!
Let S be a set with 2n+1 elements. Partition S into n pairs of elements, with one single element left over. We want to choose a set of n elements from S. From each pair of elements we can select 0, 1 or 2 elements. Also, we can either select or not select the single element.
Start by selecting k pairs to choose one element from. There are ways of doing this ( ways of choosing which pairs, and 2 ways of choosing which element in each pair). To bring the total number of selected elements up to n, we then need to select both elements from exactly half of the remaining n-k pairs, if n-k is even. If n-k is odd then we have to select both elements from of them, together with the single element of S. In either case, there are ways of doing this.
That shows that .