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

excellent explaination

---

$$\text{First remove } kn \text{ balls from } m \text{ balls assuming that it already been allotted, then}$$$$\text{distribute } m-kn \text{ balls to } n \text{ boxes by Beggar's Theorem, so it will be } \binom{m-nk+n-1}{n-1}$$

---

options B

Answer 1

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 2

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}$

Answer 3

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)

Answer 4

A star bar problem

There are 1,2,3,4,5...n bags.

And in each 'k' balls are already placed.

So, k,k,k,k,k,k...upto n bags total 'kn' balls placed.

Now only 'm-nk' balls left

 

m-nk balls equal to stars

And n bags equal to n-1 bars.

 

Applying the star bars logic

(m - kn + n - 1) choose (n - 1) ways possible.

 

Answer 5

remeber the example of IODB template where deepaksir told 10 identical choclates distribute among 3 children where each child get at least one choclate... this type of question

total identical balls = m, disticnt box = n  and each box has at least kn balls m>= kn so see that now the stars = m - kn and the bars = n-1 so the ways as formula : (m-kn+n-1)C(n-1) . formula : (star + bar -1)C(bar -1)

Answer 6

Good Luck