Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In how many ways can we select $n$ objects from a collection of size $2n$ that consists of $n$ distinct and $n$ identical objects?

The answer is $2^n$ and I really don't see how they get this. Selecting $n$ distinct from $2n$ is $\binom{2n}{n}$.

share|improve this question
    
Try working a small example: one white sock, one red sock, two black socks. Hint: sort the 12 possibilities in order by number of black socks. –  Eric Lippert Dec 17 '13 at 0:31

3 Answers 3

Let $A=\{a_1,\ldots,a_n\}$, where the $a_k$ are mutually distinguishable, and let $S$ be $A$ together with $n$ indistinguishable objects. An $n$-element subset $X$ of $S$ is completely determined when you know $X\cap A$: if $|X\cap A|=k$, the remainder of $X$ is just $n-k$ of the indistinguishable objects. $A$ has $2^n$ subsets, so there are exactly $2^n$ different possibilities for $X\cap A$ and therefore for distinguishable sets $X\subseteq S$ of cardinality $n$.

share|improve this answer

Note that the set of objects chosen is determined by which of the distinct objects are chosen and how many of the identical objects are chosen. For each of the $2^n$ subsets of the $n$ distinct objects, the number of identical objects we need to take in order to fill our quota of $n$ total objects is uniquely determined. Hence there are $2^n$ total ways to take $n$ total objects from $n$ distinct and $n$ identical objects.

share|improve this answer

Hint. If you choose $k$ elements from the $n$ distinct, and $n-k$ from the $n$ identical, there are:

$$\binom{n}{k}\cdot 1$$

ways to do this. Now sum from $k=0$ to $k=n$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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