The Gateway to Computer Science Excellence
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 by Active (1.8k points)
retagged by | 442 views

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

by Active (2.3k points)


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.

by Active (1.8k points)
reshown by
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
50,737 questions
57,293 answers
104,916 users