Another formula

Anyone who knows about the Principle of Inclusion and Exclusion will suspect that it can be applied to the relationship between sampling with and without replacement.

In order to find the formula for sampling without replacement, we must be able to calculate, for each subset of the objects, the number of samples in which at least these (and possibly more) are repeated. Suppose that we are sampling k from n. Given a set of m objects, we can assure that these are all repeated by putting them each twice in the samle; the remaining k−2m then form an arbitrary sample with replacement from the whole set. So the required number is {n\choose m}{n+k-2m-1\choose k-2m}.

Applying PIE, we obtain the identity

\sum_{m=0}^{\lfloor k/2\rfloor}(-1)^m{n\choose m}{n+k-2m-1\choose k-2m}={n\choose k}.

About Peter Cameron

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

2 Responses to Another formula

  1. Hi Peter. I think there might be a power of -1 missing. Merry Christmas from a warm and sunny Dunedin.

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.