Log In
0 votes

How many ways are there to:

  1. Put n distinguishable balls in r distinguishable boxes?
  2. Put n indistinguishable balls in r distinguishable boxes?
  3. Put n distinguishable balls in r indistinguishable boxes?
  4. Put n indistinguishable balls in r indistinguishable boxes? 

Where, $r \geq n$

in Combinatory
retagged by

2 Answers

0 votes

1. r^n

2. (r+n-1)Cn

3.its quite tricky,the fact that balls are distinguisable makes problem difficulty.

          problem is that {{b1,b2,b5},{b3,b4},{b6}} is one arrangement of these here the relative order of balls need to be                   preserved. i.e a bijection of <3,2,2> doesnt work

          here there are 3 baskets (partitions ) and 6 balls(elements) now the job is partitioning a set of size n into r partitions.  but                 here the partions will be mutually exclusive and exhaustive but maybe empty.

         so a trick to use is sum rule,where you calculate the number of ways of partitioning n balls in  r non empty partions,then (r-1)         non empty partions,(r-2),....2,1.

        so total ways=s(n,r)+s(n,r-1)+.......s(n,1)

4.a simple bijective mapting of sample space to <> 0001000101000...000010.   where 0 represents balls and  two 1's represnts a box. only job is to calculate diffrent number of such numbers where there are n zeros and (r-1) ones  given by ((n+r-1)Cr)/r! .

its simply extension of 2nd questions,assume 3 boxes which are distigusibale so a arrangemnt <3,2,4> represnts box 1 has 3 balls,box 2 has 2 balss and box 3 has 4 <4,2,3> represents another arrangment since boxes are distingusibale but   if there are indistinguabale then both above sequneces represnets same arrangement,so <4,2,3><4,3,2><2,3,4><2,4,3><3,2,4><3,4,2> maps to {4,2,3} thus there is divide by 6(3! or r!(general)) .



For the 3rd question. My understanding is like this. Its similar to question 1 except the boxes are indistinguishable. Now, assuming boxes are distinguishable, there are rn ways. But once you place the balls in boxes, the boxes are indistinguishable. So, divide by r!

Basically, label the boxes as {1,2,3......,r}. Now, they can be arranged in r! ways. But they have said boxes are indistinguishable, SO we divide by r!.  

I dont know what do you mean by order of balls.

0 votes

I too don't have answer key for this problem but here is my take at this,
Assuming one ball per box allowed
(1). $r * (r-1)*(r-2)*...*(r-n+1)$, because every ball is unique as is every box and we assume one ball per box, so we have r choices for the first ball, r-1 for the second ball and so on, at the same time we also need to count all permutations of placement of these balls.

(2). $\binom{r}{n}$, because in this case, which boxes are selected for placing the balls matter but which ball is kept in which box does not.

(3). 1, since $r \geq n$ and it does not matter in which box we put a ball.

(4). 1, since both balls and boxes are indistinguishable.

reshown by

Related questions

2 votes
0 answers
The number of ways six distinct balls be distributed into 3 distinct urns. If each urn contain at least one ball are ____
asked Jan 12, 2018 in Combinatory Rohit Gupta 8 273 views
0 votes
0 answers
in how many ways 4 different balls can be distributed in 5 different boxes so that no box contains all 4 balls
asked Nov 23, 2018 in Combinatory Sanjay Sharma 387 views
1 vote
1 answer
The number of ways in which $2n$ white and $2n$ black balls can be arranged such that no consecutive $n$ white balls are together, is ${}^{2n+1}C_2 + {}^{4n}C_{2n}$ ${}^{2n+1}C_2 - {}^{2n+1}C_1. {}^{3n}C_{n} (-1)^n + {}^{4n}C_{2n}$ ${}^{2n+1}C_2+ (-1)^n. {}^{2n+1}C_1 . {}^{3n}C_n + {}^{4n}C_{2n}$ ${}^{2n+1}C_2+ (-1)^n. {}^{3n}C_n . {}^{2n+1}C_1$
asked Mar 21, 2016 in Combinatory sampad 978 views
0 votes
2 answers
(Reference- A first course in probablity by Sheldon Ross [Example 5b and 5c of chapter 1]) Q1. Ten children are to be divided into an A team and a B team of 5 each. The A team will play in one league and the B team in another. How many different divisions are possible ... 5!))/2! How are these two questions different and how both the groups are similar in Q2 so we have to divide the result by 2!.
asked May 13, 2016 in Combinatory bitManiac 152 views