The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2k 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)$
asked in Combinatory by Veteran (52k points)
retagged by | 2k views

5 Answers

+30 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 )$

Correct Answer: $B$
answered by Boss (41k points)
edited by
0
Can you explain the ball and sticks method? How did you get the final answer. Please give some reference.
+3
0
x1 + x2 + ... + xn = m- k*n , x1,x2..xn >=0.

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

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
0

$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 https://drive.google.com/file/d/1aRHyIwITRSO1JOdNrbgNRrjpYj2ouwSd/view?usp=sharing

+10 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.6k points)
+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?
0

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

+1 vote

Simplest way possible: 10 sec 

answered by Junior (801 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 (747 points)
0 votes

We know that the no. of non-negative integral solution to the equation $x_{1} + x_{2} + x_{3} + ... + x_{k} = n$ where $(n≥k)$ and  $x_{i} \geq 0, i = \left \{ 1, 2, 3, ..., k \right \}$ is given by $\binom{n \ + \ k \ - \ 1}{k \ - \ 1}$ or $\binom{n \ + \ k \ - \ 1}{n}$.

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

Let, $x_{1}, \ x_{2}, \ x_{3}, \ ..., \ x_{n}$ be the no. of balls in the $n$ distinct bag respectively such that $x_{i} \geq k, i = \left \{ 1, \ 2, \ 3, \ ..., \ n \right \}$. As the total no. of balls is $m$, therefore, $x_{1} + x_{2} + x_{3} + ... + x_{n} = m$.

Now, let $y_{i} = x_{i} - k, \ i = \left \{ 1, 2, 3, ..., n \right \}$. Therefore, if $x_{i} \geq k$, then $y_{i} \geq 0$.

Now, $(x_{1}-k) + (x_{2}-k) + (x_{3}-k) + ... + (x_{n}-k) = m - nk$

$\Rightarrow 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 no. of non-negative integral solution to the above equation.

Therefore, the req. no. of ways is $\binom{m \ - \ nk \ + \ n \ - \ 1}{n \ - \ 1} = \binom{m \ - \ nk \ + \ n \ - \ 1}{m \ - \ nk}$.

Therefore, correct option- (B).

 

answered by (393 points)
Answer:

Related questions

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
49,535 questions
54,122 answers
187,321 comments
71,039 users