Log In
17 votes

$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)$
in Combinatory
retagged by

very much simple approach,


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

8 Answers

36 votes
Best answer
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 by
Can you explain the ball and sticks method? How did you get the final answer. Please give some reference.
x1 + x2 + ... + xn = m- k*n , x1,x2..xn >=0.

How do we solve this???
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

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: , which is similar to the one answered above. Can you please explain? 

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.
best source to know about ball and stick method??

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

For better image


balls && sticks method 


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.

12 votes

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).

So, answer would be b.

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

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

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

2 votes

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



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



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

0 votes
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}$
0 votes
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}$
0 votes
apply the logic where b1,b2,>=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, where b1,b2,>=0 s0 c(m-nk+n-1,n-1)
0 votes


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


Related questions

30 votes
2 answers
$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\)
asked Sep 16, 2014 in Combinatory Kathleen 3.3k views
33 votes
3 answers
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$
asked Sep 16, 2014 in Combinatory Kathleen 4.7k views
17 votes
3 answers
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}$
asked Dec 21, 2016 in Combinatory jothee 1.5k views
23 votes
3 answers
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.
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.4k views