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