How to Prove this Multiset Identity by Combinatorial Proof

Question

I was wondering how to do a combinatorial proof of the following identity: $\bigl(\!\!\binom{n}{k}\!\!\bigr)$= $\bigl(\!\!\binom{n-1}{k}\!\!\bigr)$ + $\bigl(\!\!\binom{n}{k-1}\!\!\bigr)$ for all n, k ∈ N and not both equals to 0. The image of the question is here: image

A multiset is an unordered list of elements, repeats allowed. A multiset will be denoted M = h. . .i to distinguish it from an ordinary set. One can more formally define a multiset M to be a pair (X, m), where X is a set and m : X → N≥1 is a function. m is the multiplicity function, recording how many times a given element of the set X is included in the multiset M. So for example, if X = {a, b, c} and m(a) = 2, m(b) = 1, m(c) = 3, then M = ha, a, b, c, c, ci. 2 Just as looking at k-element subsets of a set of size n gives rise to the binomial coefficients, we can investigate interesting counting problems using the notion of multisets of a certain size.

Example Question: Denote by $\bigl(\!\!\binom{n}{k}\!\!\bigr)$ the number of k-element multisubsets of a set of size n. If n = 2, consider the set X = {a, b}. Then the set of multisubsets of X of size 2 is {⟨a,a⟩,⟨a,b⟩,⟨b,b⟩}, and the set of multisubsets of size 3 is {⟨a,a,a⟩,⟨a,a,b⟩,⟨a,b,b⟩,⟨b,b,b⟩}. Thus $\bigl(\!\!\binom{2}{2}\!\!\bigr)$ = 3 and $\bigl(\!\!\binom{2}{3}\!\!\bigr)$ = 4

Answer 1

Here is a combinatorial proof:

Let $x$ be one of the $n$ distinct elements of the underlying set $S$. The multisubsets of size $k$ can be partitioned into two different groups:

• The ones that include at least one copy of $x$, and
• The ones that don’t include $x$ at all.

The first group has $\bigl(\!\!\binom{n}{k-1}\!\!\bigr)$ multisubsets in it, because taking out one copy of $x$ corresponds uniquely to an arbitrary multisubset of $S$ of size $k - 1$.

The second group has $\bigl(\!\!\binom{n - 1}{k}\!\!\bigr)$ multisubsets in it, because these are the multisubsets of size $k$ with underlying set $S\setminus \{x\}$ which has $n - 1$ elements.

Therefore,

$$ \biggl(\!\!\!\binom{n}{k}\!\!\!\biggr) = \biggl(\!\!\!\binom{n}{k - 1}\!\!\!\biggr) + \biggl(\!\!\!\binom{n - 1}{k}\!\!\!\biggr). $$

Answer 2

Let X be a particular person in the group of n.

We are supposed to choose k members from that group and this is C(n, k).

To complete the above selection, we can split the selection by

either with X as a must (i.e. C(n - 1, k - 1)).... [X is already a member, we only need to choose k - 1 persons from the remaining n - 1 group.]

OR

must exclude X (i.e. C(n - 1, k)).....[X must not be chosen, there are n - 1 candidates availble and need to choose k.]

Added: X is either selected as a member or NOT as a member. The two events are mutally exclusive. Thus, "OR"ing the two events end up with C(n - 1, k - 1) + C(n - 1, k). This is exactly C(n, k).