The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
1.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 (59.4k points)
retagged by | 1.2k views

2 Answers

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

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

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? 

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


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

35,507 questions
42,828 answers
121,691 comments
42,183 users