Home › GATE CSE › computerscience › Discrete Mathematics › How many ways to put 10 IDENTICAL balls into 4 D…
How many ways to put 10 IDENTICAL balls into 4 DISTINCT boxes (each box can hold 0 or more)?
A$\binom{10}{4} = 210$
B$4^{10}$
C$\binom{13}{3} = 286$
D$10!$
Answer & Solution
Correct answer: C. $\binom{13}{3} = 286$
1. STARS AND BARS: count solutions to $x_1 + x_2 + x_3 + x_4 = 10$ where $x_i \geq 0$.
2. Formula: number of non-negative integer solutions to $\sum x_i = n$ with $k$ variables is $\binom{n+k-1}{k-1}$.
3. Here $n = 10$, $k = 4$: $\binom{10+4-1}{4-1} = \binom{13}{3} = \dfrac{13!}{3!\,10!} = \dfrac{13 \cdot 12 \cdot 11}{6} = 286$.
4. Intuition: 10 stars + 3 bars to delimit 4 groups; arrange them in $\binom{13}{3}$ ways.
5. Option A is the wrong formula. Option B treats balls as DISTINCT (wrong). Option D is for ordered DISTINCT items.
_Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §1.5 (Stars and Bars)._
Related questions
A PREDICATE $P(x)$ isHow many DIFFERENT subsets of size 3 can be selected from a set of 7 elements?In how many ways can 7 people sit in a ROW?$\binom{n}{k} = \binom{n}{n-k}$. This identity reflectsHow many DIFFERENT 5-bit binary strings are there?The PIGEONHOLE PRINCIPLE states that if $n$ pigeons are placed into $m$ holes with $n > m$A function $f: A \to B$ is INJECTIVE (one-to-one) if$|A \cup B|$ (size of union) equals