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.


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


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


About Peter Cameron

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

1 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.