The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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)\)
asked in Combinatory by Veteran (59.5k points)
retagged by | 1.4k views

3 Answers

+19 votes
Best answer
As there have to be atleast $k$ balls in each bag, so firstly put $k$ balls in each bag i.e $\left(k*n\right)$ balls.

Then 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 equal to $\left(m-k*n\right)$, no restrictions on how many balls in each bag $!$

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

So when we solve it

We get

$C(m - k*n + n - 1, n-1 ) = C(m - k*n + n - 1, m- k*n )$
answered by Boss (42.6k points)
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.
+9 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.

answered by Active (2.4k points)
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}$
answered by Junior (557 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,000 questions
45,496 answers
48,633 users