# GATE2003-34

3.4k views

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

1. $\left( \begin{array}{c} m - k \\ n - 1 \end{array} \right)$
2. $\left( \begin{array}{c} m - kn + n - 1 \\ n - 1 \end{array} \right)$
3. $\left( \begin{array}{c} m - 1 \\ n - k \end{array} \right)$
4. $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

retagged
1

very much simple approach,

0

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

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

As there have to be at least $k$ balls in each bag, so firstly put $k$ balls in each bag i.e., $\left(k*n\right)$ balls.

Now, we have total $\left(m-k*n\right)$ balls remaining.

We can use balls $\&$ sticks method now $!$

$n$ bags $= n$ variables, they need to be equal to $\left(m-k*n\right)$, no restrictions on how many balls in each bag $!$

$x_{1}+x_{2}+\ldots+x_{n}= \left ( m-k*n \right ),x_1,x_2\ldots x_n\geq 0.$

On solving, we get

$C(m - k*n + n - 1, n-1 ) = C(m - k*n + n - 1, m- k*n )$

Correct Answer: $B$

edited
0
Can you explain the ball and sticks method? How did you get the final answer. Please give some reference.
6
0
x1 + x2 + ... + xn = m- k*n , x1,x2..xn >=0.

How do we solve this???
7
One way to solve it

there are m balls

each bag must contain atleast k balls

So, after giving each bag k balls , there remain m-kn balls

now in remaining these balls we need to distribute in all bags by distribution method

C(m-kn+n-1, n-1) ways
2

Hey @Akash Kanase, if the balls were to be distinct then will this method still be applied. I am asking in reference to a question: https://gateoverflow.in/29329/entrepreneur-assign-different-tasks-employees-should-atleast?show=164847#c164847 , which is similar to the one answered above. Can you please explain?

0
If balls would have been different then first we would select all boxes at once and then select balls for them nC3 * n-3C3*n-6C3. Then suppose if remaining balls are ewual to remamining objects then n! else if remaining balls greater than boxes groupig and distribution.
0
best source to know about ball and stick method??
0
Rosen
2

$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$. if each bag must contain at least $k$ balls.

1

balls && sticks method

0

After filling each bag with kn balls remaining balls is m-kn. Now we can distribute over n-1 bags where each bag can have 0 or more balls. This video will help.

As there have to be atleast k balls in each bag, so firstly put k balls in each bag i.e k*n balls. Then after, (m - kn) identical balls are left which we have to put it in n distinct bags, so use this general formula:

C(n + m - kn - 1, n -1).

1
According to the general formula the answer would be C(n+m-kn-1, n).

how you got n-1?
0
yes i also can not understand.wht (n-1) in place of n?
1

In stars and bars problem when we divide into n parts then we use n-1 sticks ...not n sticks.

Concept Used:

Number of non-negative integral solution to the equation

$x_{1} + x_{2} + x_{3} + ... + x_{k} = n$

where, $(n≥k)$,

$x_{i} \geq 0,$ and

$i = \left \{ 1, 2, 3, ..., k \right \}$

$=\binom{n \ + \ k \ - \ 1}{k \ - \ 1}$ or $\binom{n \ + \ k \ - \ 1}{n}$.

Problem:

$m\ (m\geq nk)$ identical balls have to be placed in $n$ distinct bags such that each bag contains at least $k$ balls.

Solution:

Let $Bag_i$ contains $x_i$ number of balls where $i = \left \{ 1, \ 2, \ 3, \ ..., \ n \right \}$

Then sum of all the balls in each bag = $m$        where $(m\geq nk)$

$\implies$ $x_{1} + x_{2} + x_{3} + ... + x_{n} = m$.

$\because$ Each bag should contain atleast $k$ number of balls so we can write each of the $x_i$'s as sum of $y_i + k$

$\implies$ $(y_{1}+k) + (y_{2}+k) + (y_{3}+k) + ... + (y_{n}+k) = m$.

$\implies$ $y_{1} + y_{2} + y_{3} + ... + y_{n} = m - nk$.

Now, we have to find all such values of $y_{1}$, $y_{2}$, $y_{3}$,...,$y_{n}$ that satisfy the above equation.

In other words, the problem basically reduces to  finding the number of non-negative integral solution to the above equation.

$\therefore$ The required number of ways is $\binom{m \ - \ nk \ + \ n \ - \ 1}{n \ - \ 1} = \binom{m \ - \ nk \ + \ n \ - \ 1}{m \ - \ nk}$.

Therefore, correct option- (B).

edited by
0
I posted an answer to the wrong question. Now neither can i delete or remove. So converting this to a comment.
1 vote

Simplest way possible: 10 sec

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

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

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

## Related questions

1
3.3k views
$n$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is $^{2n}\mathrm{C}_n\times 2^n$ $3^n$ $\frac{(2n)!}{2^n}$ $^{2n}\mathrm{C}_n$
Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that each is sorted in ascending order, $B$ has $5$ and $C$ has $3$ elements, and the result of merging $B$ and $C$ gives $A$ $2$ $30$ $56$ $256$
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins? $3^{35}$ $3^{50}-2^{50}$ $\binom{35}{2}$ $\binom{50}{15} \cdot 3^{35}$ $\binom{37}{2}$
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.