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

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.

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s