retagged by
11,101 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

3 votes
3 votes

 

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

2 votes
2 votes

m identical balls are to be placed in n distinct bags. You are given that mkn, 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}$

edited by
1 votes
1 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
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}$
Answer:

Related questions

43 votes
43 votes
5 answers
1
44 votes
44 votes
4 answers
2
Kathleen asked Sep 16, 2014
13,322 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,065 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...