# Combination

The no. of ways of selecting n things out of 3n things of which n are of one kind and alike and n are of 2nd kind and rest are unlike is:

21
Shubhodip ·

Let x_p and x_q denote the two sets containing n things of two different kinds. So it matters only how many you select from there. Denote by x_i, 1 \le i \le n the rest of the things that are all different.

We are looking for number of solutions to the equation x_p + x_q + \sum_{i=1}^{n}x_i = n

Where x_p, x_q \in \left \{ 0,1, \cdots, n \right \}, x_i\in \left \{ 0,1 \right \}

Which is the coefficient of x^n in (1+ x+ x^2 + \cdots +x^n)^2(1+x)^n

or that in (1+ x+ x^2 + \cdots )^2(1+x)^n

wait : since you r in 9th, do u know these ?

341
Hari Shankar ·

A way of explaining accessible at school level would be:

Suppose k objects have been chosen out of the n dissimilar objects.

Then we have to choose n-k objects from out of the two other sets. The choices would go like 0 from the first set and (n-k) from the other, or 1 from set 1 and (n-k-1) from the other etc. This gives n-k+1 choices.

So we are looking for \sum_{k=0}^n (n-k+1) \binom{n}{k} = \sum_{k=0}^n (n+1) \binom{n}{k} - \sum_{k=0}^n k \binom{n}{k}

The first sum is just (n+1)2^{n}

The second one is

\sum_{k=0}^n k \binom{n}{k} = \sum_{k=0}^n (n-k) \binom{n}{k} = \frac{1}{2} \sum_{k=0}^n n \binom{n}{k}= n 2^{n-1}

Hence the required number of ways = (n+2) 2^{n-1}