retagged by
11,091 views
23 votes
23 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)$
retagged by

9 Answers

Best answer
44 votes
44 votes
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
14 votes
14 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.

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

 

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

Related questions

43 votes
43 votes
5 answers
1
44 votes
44 votes
4 answers
2
Kathleen asked Sep 16, 2014
13,313 views
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 thateach is sorted in ascending...
19 votes
19 votes
4 answers
4
go_editor asked Dec 21, 2016
4,057 views
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}$$\bino...