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

 

We can also take small values for m,n and k  and check for options.

Answer 2

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

Given :

$m$ balls
$n$ bags
each bag must contain at least $k$ balls

Let the bags be $X_{1}, X_{2}, X_{3}, X_{4} … X_{n}$

Now, each bag contain at least $k$ balls ie  $X_{i} \geqslant k$

Maximum limit, $X_{i} \leqslant m- (n-1)*k$

Therefore, $k \leqslant X_{i} \leqslant m- nk+k$

The number of combinations will be the coefficient of $X^{^{m}}$ in generating equation :

$(X^k \,+\, X^{k+1} \,+\, X^{k+2} \cdot \cdot \cdot \cdot \,+\, X^{m-nk+k})^n$

Taking $X^k$ common;

$X^{nk}(1 \,+\, X \,+\, X^{2} \cdot \cdot \cdot \cdot \,+\, X^{m-nk})^n$

Now, coefficient of $X^{(m-nk)}$ is required

Applying the GP sum, taking number of elements as $m-nk+1$, $a$ as $1$ and $r$ as $X$
 

$\frac{(1-X^{m-nk+1})^n}{(1-X)^n}$

Now, using the identity $\frac{1}{(1-X)^n} = \sum_{a=0}^{infinity} \, _{a}^{n+a-1}\textrm{C} \cdot x^a$

Put $a = m-nk$

$_{m-nk}^{n+m-nk-1}\textrm{C}$ which can be written as $_{n+m-nk-1-(m-nk)}^{n+m-nk-1}\textrm{C}$

That is,  $_{n-1}^{n+m-nk-1}\textrm{C}$

Answer 3

This can be easily solved using generating functions. For each bag, we need atleast k balls. So, no. of ways there can be 1 ball in a bag =0, 2 balls in a bag = 0 ... k balls in a bag = 1, k+1 balls in a bag = 1 and so on.

 

So, generating function for a bag will be $x^{k} + x^{k+1} + x^{k+2} +...$  which can be expressed as $f(x)=x^{k}/(1-x)$.

For n different bags, the generating function will be $(x^{k}/(1-x))^{n}$. For m balls, we need to find the coefficient of $x^{m}$ in this generating function.

Or we can say that we need to find the coefficient of $x^{m-nk}$ in $1/(1-x)^{n}$ which will be $\binom{m-nk+n-1}{m-nk}$

Answer 4

Answer will be (b)

$x_1+x_2+x_3+....+x_n = m$

$x_i \ge k$

so we can take

$y_1+k+y_2+k+y_3+k+....+y_n+k = m$

$\implies y_1+y_2+y_3+....+y_n = m-nk$

so number of ways the balls be placed in the bags if each bag must contain at least k balls is $^{m-nk+n-1}C_{n-1}$