2
$\begingroup$

We choose uniformly a group of $k$ people selected from $n$. For $m \leq k$, calculate using inclusion-exclusion the probability that $m$ special people are in the group and then deduce that \begin{align} {n-m\choose k-m}=\sum_{j=0}^{m} (-1)^j {m\choose j} {n-j \choose k} \end{align}

Any suggestions? Thanks in advance!

$\endgroup$
1
$\begingroup$

With this problem the underlying poset consists of nodes $Q\subseteq [m]$ (the set of special people) which represent groups of $k$ people selected from the $n$ total where the elements of $Q$ are missing, or possibly more of the special people. The weights on the $Q$ are as usual $(-1)^{|Q|}.$ The cardinality of the groups represented at $Q$ is clearly ${n-|Q|\choose k}.$ Counting the groups presented at all $Q$ multiplied by their weight yields the closed form

$$\sum_{Q\subseteq [m]} (-1)^{|Q|} {n-|Q|\choose k} = \sum_{q=0}^m {m\choose q} (-1)^q {n-q\choose k}.$$

On the other hand, counting by computing the total weight contributed by each of the groups we find that a group that has all the special people only appears at $Q=\emptyset$ with total weight $(-1)^{|\emptyset|} = 1.$ A group that has exactly $P$ of the special people missing where $|P|\ge 1$ appears in all $Q\subseteq P$ for a total weight of zero since

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$

We conclude from these weights that the above sum counts exactly those groups with none of the special people missing, these having weight one, and the others having weight zero. Therefore it is equal to

$${n-m\choose k-m}$$

Here we have selected all $m$ special people first and choose $k-m$ people from the remaining set. Note. When $n-|Q| \lt k$ the set of groups represented at $Q$ is empty, so that for $m+k\gt n$ the nodes of the top $m+k-n$ rows of the poset represent zero possible groups. This does not affect the calculation of the sum of the weights, however, since a group with the special people from some $P$ missing is represented by the nodes of the embedded poset spanned by the two nodes $Q=P$ and $Q=\emptyset$ (which is entirely below $P$ rather than above where the potentially empty nodes are). None of the nodes of this poset are empty if $n-|P|\ge k$ which is a precondition for the group to be realized in the first place.

As a remark, observe that the sum is not difficult to evaluate. We get

$$\sum_{q=0}^m {m\choose q} (-1)^q [z^k] (1+z)^{n-q} = [z^k] (1+z)^n \sum_{q=0}^m {m\choose q} (-1)^q (1+z)^{-q} \\ = [z^k] (1+z)^n \left(1-\frac{1}{1+z}\right)^m = [z^k] z^m (1+z)^{n-m} = [z^{k-m}] (1+z)^{n-m} \\ = {n-m\choose k-m}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.