Number of ways to choose $n$ balls from $3n$ balls, distinguishable/indistinguishable.

Solution 1:

I would do something like that: U have $n$ black and $n$ white balls which are indistinguishable and $n$ coloured balls which are distinguishable. U want to choose $n$ balls.

Let's assume that in our "way" we want to take k coloured balls. Then, there is exactly ${n \choose k}$ ways of choosing those coloured balls from $n$. Then we have $n-k$ balls missing and we need to choose those from black and white balls. But those are indistinguishable ! That means, we are only interested in number of (say) black balls in our "chosing". The number of black balls can vary from $j=0$ to $j=n-k$, which gives us $n-k+1$ ways of choosing the rest. Now, it is obvious that number of coloured balls ($k$) can vary from $0$, to $n$. So, the total number is given by: $$ T=\sum_{k=0}^n(n-k+1){n \choose k} $$

Simplier: $$ T=\sum_{k=0}^n(n+1){n \choose k} - \sum_{k=1}^nk{n \choose k}$$

$\sum_{k=0}^n(n+1){n\choose k} = (n+1)2^n$

$\sum_{k=1}^nk{n\choose k} = n2^{n-1}$ $\ \ \ \ \ $ (*)

So:

$$ T = (n+1)2^n - n2^{n-1} = n2^n + 2^n - n2^{n-1} = 2^{n-1}(2n + 2 - n) = (n+2)2^{n-1} $$

(*) Little explanation: RHS counts the number of ways of choosing a "captain" and his "team" from n people, where the number of people in "team" can be any from 0 to n-1. And we can see, that LHS counts the same, k - {number of people in a "team" + 1} ( cause we are to choose the captain from those k people, and the rest of them will form our "team" with k-1 people ( here k vary from 1 to n, then k-1 from 0 to n-1 and that is exactly what are we looking for)

Solution 2:

Presage's answer has led me to the following solution: There are $2^n$ ways to select a subset $A\subset[n]$ of the $n$ distinguishable balls. Let $(A,A')$ be a complementing pair of such subsets. If $|A|=n-r$ then we have to select $r$ black or white balls. This can be done in $r+1$ ways. At the same time $|A'|=r$ forces us to select $n-r$ black or white balls, which can be done in $n-r+1$ ways. It follows that each complementing pair $(A,A')$ gives rise to $n+2$ admissible choices, so that we arrive at $(n+2)2^{n-1}$ in total.

Solution 3:

We have to choose $b$ black balls, $w$ white balls, and $c$ colored balls, where $b+w+c=n.$ How many ways are there to do this? If it doesn't matter which black balls we pick, there's only one way to do it: choose $b$ black balls. Similarly, there's only one way to choose $w$ white balls. There are $n$ different colored balls, so there are ${n\choose c}$ ways to choose the colored balls, and we see that all that really matters is the number of colored balls.

How many times does a particular value of $c$ come up? $b$ can take any value from $0$ to $n-c$ and then the value of $w$ is determined, so the value $c$ will come up $n-c+1$ times. The answer is therefore $$\sum_{c=0}^n(n-c+1){n\choose c}$$

I leave it you to simplify this expression.