retagged by
893 views
0 votes
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$

retagged by

2 Answers

0 votes
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 balls.so 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 balls.now <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)) .

0 votes
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

0 votes
0 votes
0 answers
1
Sanjay Sharma asked Nov 23, 2018
1,491 views
in how many ways 4 different balls can be distributed in 5 different boxes so that no box contains all 4 balls
2 votes
2 votes
0 answers
2
Rohit Gupta 8 asked Jan 12, 2018
660 views
The number of ways six distinct balls be distributed into 3 distinct urns. If each urn contain at least one ball are ____
1 votes
1 votes
1 answer
3
sampad asked Mar 21, 2016
2,811 views
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...