GATE CSE 2003 | Question: 34

Question

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ balls?

• A. $\left( \begin{array}{c} m - k \\ n - 1 \end{array} \right)$
• B. $\left( \begin{array}{c} m - kn + n - 1 \\ n - 1 \end{array} \right)$
• C. $\left( \begin{array}{c} m - 1 \\ n - k \end{array} \right)$
• D. $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

Comments

very much simple approach,

https://www.youtube.com/watch?v=5G92GoDifWI

---

Just in case someone is confused with the short trick used:

https://math.stackexchange.com/questions/910809/how-to-use-stars-and-bars

---

Total m balls and each contain at least k balls. So give k balls each n bags and remaining = (m – kn)

Now (m – kn) we have to permute in n bags So, C ( m-kn+n-1 , n-1).

Note : (n-1) because for n numbers we do (n-1) partitions. Find similarity from the no. of ways X+Y+Z = 12. how many X, Y,Z values possible. Here we do (3-1) partitions.

---

IODB TEMPLATE

Answer 1

apply the logic b1+b2+b3+....bn=m where b1,b2,b3....bn>=0 apply c(n=m-1,m)

so to make this equation valid first give k balls each in every bag so now balls rem=m-nk

so,b1+b2+b3+b4......bn=m-nk where b1,b2,...bn>=0 s0 c(m-nk+n-1,n-1)