TITLE: Combinatorics - Without order
QUESTION [5 upvotes]: You have 10 different types balls to choose from.
How many different ways are there to choose 5 balls such that no type of ball appears more than twice.
My attempt:
Case 1 (selecting different types): analogues to choosing 5 elements from a set of 10 - 10C5 = 252
Case 2 (1 element repeats twice) - 10C4 to select 4 objects and 4 to select which appears twice - 10C4*4 = 840
Case 3 (2 elements repeat) - 10C3 to select 3 objects and 3 to select which appears once - 10C3*3 = 360
Total : 252 + 210 + 360 = 1452
Thanks,

REPLY [1 votes]: Suppose you have $k$ different balls and you want to count how many ways you can choose $n$ balls with replacement such that each ball is chosen less than $\mu$ times. Let $x_i$ be the number of times you pick up ball $i$. Then we are counting the number of non-negative integer solutions to  
$$ x_1 + x_2 + ... + x_k = n $$  
where we have the constraint $x_i < \mu$ for each ball. We can solve this using inclusion exclusion. If $S$ is the set of unconstrained solutions and $P_i$ is the subset with $x_i \geq \mu$, then we have
$$ \begin{array}
 (| S - (P_1 \cup P_2 \cup ... \cup P_k )|
   &= & |S| \;\;-\;\; \sum_i |P_i| \;\;+ \;\;\sum_{i,j} |P_i \cap P_j| \;\; - \;\; ... \\
\; &= & {n+k-1 \choose k-1} \;-\; k {n+k-1-\mu \choose k-1} 
      \;+\; {k \choose 2} {n+k-1-2\mu \choose k-1} \;\;-\;\; ... \\ && \\
\; &= &\sum_{i=0}^\gamma \; (-1)^i {k \choose i} {n+k-1-i\mu \choose k-1}
\end{array}
$$  
Where $\gamma = \min \{k, \lfloor \tfrac{n}{\mu} \rfloor \}$. Plugging in the values $k=10, n=5, \mu=3$ solves the question you posed.  
$$ \begin{array} 
( \sum_{i=0}^{1} \; (-1)^i {10 \choose i} {14-3i \choose 9} = 1452
\end{array}
$$

I explained everything in a recent post solving a similar problem.
{"set_name": "stack_exchange", "score": 5, "question_id": 1126705}