C. L. Liu 3.38(b)

Question

Among $3n + 1$ objects, $n$ of them are identical. Find the number of ways to select $n$ objects out of these $3n + 1$ objects.

Comments

My partial solution is $\sum_{k = 0}^{n} \binom{2n+1}{n-k} = \sum_{k = 0}^{n} \binom{2n+1}{k}$

Is there a closed form for above solution, (if it's a correct solution)?

---

why using summation??

---

@Akriti

I first partitioned $3n+1$ objects into two disjoint sets, one having all $n$ identical objects (A) and other having rest of them (B).

Now to choose $n$ objects from $3n+1$, $k$ will be from set A. As they all are identical there is just one way to make this selection, rest of the $n - k$ will be chosen from B, using $\binom{2n+1}{n -  k}$, where $k$ ranges from 0 to n.

Answer 1

Among $3N + 1$ objects, $N$ are identical and $2N+1$ are different.

Therefore, Selection is like $N$ from identical and $0$ from different, $N-1$ from identical and $1$ from different, $N-2$ from identical and $2$ from different, $N-3$ from identical and $3$ from different and so on.

Total ways = $\binom{2N+1}{0}\left ( 1 \right ) + \binom{2N+1}{1}\left ( 1 \right )+ \binom{2N +1}{2}\left ( 1 \right )+...+\binom{2N+1}{N}\left ( 1 \right )$ .

$\sum_{K=0}^{N}\binom{2N+1}{K}$ total ways .

---

As a thumb rule, $\sum_{K=0}^{N}\binom{N}{K} = 2^{N}$

Hence, $\sum_{K=0}^{2N+1}\binom{2N+1}{K} = 2^{2N+1}$

But, we can say that $\sum_{K=0}^{N}\binom{2N+1}{K} = \frac{1}{2}\sum_{K=0}^{2N+1}\binom{2N+1}{K}= \frac{1}{2}\left ( 2^{2N+1} \right )= 2^{2N} = 4^{N}$.

Hence, the number of ways to select $N$ objects out of these $3N+1$ objects is $4^N$ .