Yesterday, we sampled k objects from a set of n under four possible sampling rules.
Suppose that the n objects are of two different types, A and B, with a of type A and b of type B, where a+b = n. A given sample will have a certain number, say l, of type A objects, and k−l of type B.
With replacement, order significant
There are al·bk−l ways to make the selection, right?
Not quite. Since the selection is ordered, we have to specify which of the k sampling positions we obtained A objects: A first and second out of three is not the same as A second and third. So we have to multiply by .
Then summing over l gives
the Binomial Theorem for exponent k.
Without replacement, order not significant
I will skip over the other case of sampling with replacement for a moment. If we sample without replacement and with order not significant, there are ways of choosing the As and for the Bs. This time there is no complication about order of selection, so we obtain
the Vandermonde convolution.
Without replacement, order significant
Now return to the case we missed out. Write the “falling factorial”, the product of k numbers starting at n and decreasing by 1 each time, as (n)k. Now there are (a)l choices for the As, and (b)k−l for the Bs; but as in the first case we have to multiply by . We obtain
Now the binomial coefficient on the left is k!/l!(k−l)!. Dividing both sides by k! gives on the right. Putting the other two factorials on the left as denominators of the two falling factorials converts them into binomial coefficients, and we obtain the Vandermonde convolution again.
With replacement, order not significant
This time there are ways to choose the As, and for the Bs: we obtain
a dual form of the Vandermonde convolution.
The Vandermonde convolution arises by considering the coefficient of xk in the identity
The “dual form” in the preceding subsection arises similarly from