2
$\begingroup$

Among $2n$ items, $n$ are the same. How many ways are there to choose $n$ items from $2n$ items?

So, first thought is: n are the same and n are different.

I can't understand how we get to $2^n$ with this solution:

The solution says:

  • We choose with $1$ way $n$ of the $n$ same items and with ${{n}\choose{0}}$ ways $0$ of the $n$ different items.
  • We choose with $1$ way $n-1$ of the $n$ same items and with ${{n}\choose{1}}$ ways $1$ of the $n$ different items.
  • We choose with $1$ way $n-2$ of the $n$ same items and with ${{n}\choose{2}}$ ways $2$ of the $n$ different items.
  • ...
  • We choose with $1$ way $0$ of the $n$ same items and with ${{n}\choose{n}}$ ways $n$ of the $n$ different items.

And end with summing: $$ {{n}\choose{0}} +{{n}\choose{1}} +{{n}\choose{2}} + \dots + {{n}\choose{n}} = \sum\limits_{i=0}^n {{n}\choose{i}} = 2^n \text{ ways}$$

$\endgroup$
3
  • 1
    $\begingroup$ Do you mean you don't understand the solution or just the last identity? $\endgroup$
    – Shuchang
    Sep 1 '13 at 12:11
  • $\begingroup$ What you wrote is the solution. When $n$ items are picked up, suppose that you have $k$ items that are the same. This $k$ is between $0$ and $n$. Now for each $k$ you have to pick the remaining $n-k$ items from $n$ remaining object. So the total way of picking $n$ items is your last sum. Now the identity comes from two different ways of counting the number of subsets of a set with $n$ elements and the proof is done. $\endgroup$
    – Arash
    Sep 1 '13 at 12:30
  • $\begingroup$ I was thinking if there is a hidden step: $$ 1 × {{n}\choose{0}} + 1 × {{n}\choose{1}} + 1 × {{n}\choose{2}} + \dots + 1 × {{n}\choose{n}} $$ and 1 explains that from n (or less) same numbers you have only $1$ way to choose? $\endgroup$ Sep 1 '13 at 12:45
2
$\begingroup$

Your idea can be carried out without mentioning binomial coefficients. We have $2$ boxes of balls. Box 1 has $n$ distinct balls, and Box 2 has $n$ identical balls. Call the set of balls in Box 1 by the name $A$.

To choose exactly $n$ balls, we choose any subset of $A$. If we have not chosen all the balls $A$, we grab enough balls from Box 2 to make up the total of $n$.

So there are exactly as many ways to carry out our task as there are ways to choose balls from Box 1. But the set $A$ has $2^n$ subsets, so there are $2^n$ ways to carry out our task.

$\endgroup$
4
  • $\begingroup$ How does that justify the case that we take n-2 balls from Box 1 $(2^{n-2})$ways to do that and 1 way for choosing 2 balls from Box 2. Should we have in this case $2^{n-2} × 1$ ways? $\endgroup$ Sep 1 '13 at 15:19
  • $\begingroup$ It is best not to try to break down the ways of taking balls from Box 1 into cases. Anyway, there are $\binom{n}{n-2}$ ways of taking $n-2$ balls from Box 1. Whatever we take from Box 1, the rest of what we do is completely determined. If I chose certain balls from Box 1, I must take enough from Box 2 to make up my total. $\endgroup$ Sep 1 '13 at 15:24
  • $\begingroup$ Completely determined? What do you mean by that? $\endgroup$ Sep 1 '13 at 15:27
  • 1
    $\begingroup$ Let $n=25$. Suppose I tell you which balls from Box 1 were chosen, and there are $17$ of them. Then you know that there must be $8$ balls from Box 2. Since the balls in Box 2 are all the same, there is only one way to pick them. $\endgroup$ Sep 1 '13 at 15:34
1
$\begingroup$

There are $2^n$ ways to pick some elements from the $n$ non-identical ones (there are $2^n$ subsets of the $n$ non-identical elements set). Then you can complete these elements to $n$ elements, by adding some identical elements.

It is easy to justify that this construction produces all sets and each of them uniquely.

$\endgroup$
0
$\begingroup$

The solution is true, maybe you don't understand the logic behind it.

$-$ First we choose $n$ of the same $n$ items, which leaves us with choosing 0 from the other $n$ "not-same" items. Beacuse the order is not important it can be caluclate using the combination formula $\binom{n}{k}$, in this case $k = 0$.

$-$ Second we choose $n-1$ items of the same $n$ items, which means we have to chose 1 from the other $n$ items. We calculate all these combination with the same formula, but this time $k = 1$.

$$...$$

$-$ And at last we chose 0 of the same $n$ items, which means we have to choose $n$ items from the other half. And all the combinations are given by the same formula.

Finally we add all binomial coefficient together and we get the identity:

$$ {{n}\choose{0}} +{{n}\choose{1}} +{{n}\choose{2}} + \dots + {{n}\choose{n}} = \sum\limits_{i=0}^n {{n}\choose{i}} = 2^n$$

The sum of all binomial coefficient is the same of all numbers in the $n^{th}$ row in the Pascal triangle. And we now that the sum of of all numbers in the $n^{th}$ row in the Pascal triangle is given by $2^n$.

I assume that you know how we obtain the Pascal triangle. If the sum in one row is $n$ the the sum of the next row is $2n$, that's because every number of the first row impacts two numbers of the next row. We know that the sum of the first row (we are counting from 0, so n = 0) in the Pascal's triangle is 1, the second row sum is 2, the third 4... And for the $n^{th}$ row the sum is $2^n$

You could even think like this. We'll observe only the n "non-same" numbers. There are two possibilities, it's either included in the $n$ chosen items or not. So we have 2 option for every item. Because the events are independent from each other the number of ways is:

$$2 \times 2 \times ... \times 2 = 2^n$$

If we choose $k$ items of the "non-same" items, then we just simply chose $n-k$ same items in order to choose $n$ items in total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.