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 *a ^{l}*·

*b*

^{k−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.

#### Comment

The Vandermonde convolution arises by considering the coefficient of *x ^{k}* in the identity

The “dual form” in the preceding subsection arises similarly from

Counting riffs and rotes amounts to counting finite sets of ordered pairs of weighted objects from the same class the first elements all distinct but the second elements permitting repetitions, such that the weights all sum to