## Three formulae

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 kl of type B.

#### With replacement, order significant

There are al·bkl 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 ${k\choose l}$.

Then summing over l gives

$\sum_{l=0}^k{k\choose l}a^lb^{k-l} = (a+b)^k,$

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 ${a\choose l}$ ways of choosing the As and ${b\choose k-l}$ for the Bs. This time there is no complication about order of selection, so we obtain

$\sum_{l=0}^k{a\choose l}{b\choose k-l}={a+b\choose k},$

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)kl for the Bs; but as in the first case we have to multiply by ${k\choose l}$. We obtain

$\sum_{l=0}^k{k\choose l}(a)_l(b)_{k-l} = (a+b)_k.$

Now the binomial coefficient on the left is k!/l!(kl)!. Dividing both sides by k! gives ${a+b\choose k}$ 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 ${a+l-1\choose l}$ ways to choose the As, and ${b+k-l-1\choose k-l}$ for the Bs: we obtain

$\sum_{l=0}^k{a+l-1\choose l}{b+k-l-1\choose k-l}={a+b+k-1\choose k}$,

a dual form of the Vandermonde convolution.

#### Comment

The Vandermonde convolution arises by considering the coefficient of xk in the identity

$(1+x)^a(1+x)^b=(1+x)^{a+b}.$

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

$(1-x)^{-a}(1-x)^{-b}=(1-x)^{-(a+b)}.$

Advertisements

## About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

### One Response to Three formulae

1. Jon Awbrey says:

Counting riffs and rotes amounts to counting finite sets of ordered pairs of weighted objects from the same class $\mathcal{N},$ the first elements all distinct but the second elements permitting repetitions, such that the weights all sum to $n.$