Prove that the number of selections of $n$ things from two sets of $n$ identical things and $n$ other distinct things is $(n+2)\cdot 2^{(n-1)}$.
I have been trying to come up with a combinatorial proof but havent made any headway. Can anyone help me out with the proof?
Thanks in advance!!
First we will partition the problem in two subproblems.
The first is the selection of k things out of the distinguishible set. If we select k things out of an n-set we have $ \binom{n}{k} $ possibilities.
The second one is the selection of $ n-k $ items of lets say red and green balls. first we can select 0 red and n-k green, then 1 red and n-k-1 green and so on, leaving us with n-k+1 possibilies.
Putting the two together we get $ \binom{n}{k} (n-k+1) $ possibilities where you choose k things out of the distinguishible set. Summing over $ k = 1,2,...,n $ and using the binomial formula, we get: $$ \sum_{k=0}^n \binom{n}{k} (n-k+1) = \sum_{k=0}^n \binom{n}{k} (n-k) + \sum_{k=0}^n \binom{n}{k} = \sum_{k=0}^n \frac{n!}{k!(n-k)!} (n-k) + 2^n = \sum_{k=0}^n \frac{n!}{k!(n-k-1)!} + 2^n = n\sum_{k=0}^{n-1}\binom{n-1}{k} + 2^n = n2^{n-1} + 2^n = (n+2)2^{n-1}$$
Cheers