kenneth rosen chapter 5 exercise 5.5 ques 51

Question

How many ways are there to distribute six distinguishable objects into four indistinguishable objects so that each of the boxes contain at least one object??

Plss tell how to solve questions based on distributing  Distinguishable objects into Indistinguishable boxes and Indistinguishable objects into indistinguishable boxes. I am not able to solve problem based on these.

Comments

in this way you can also try

           6 objects can be distributed to 4 indistinguishable object as--(1,1,1,3) &(1,1,2,2)

  Now total possibility=6!/1!*1!*1!*3!*3!+6!/1!*1!*2!*2!*2!*2!=65

l

---

Excellent thread for Sterling number. Even sterling number can be visualized as grouping and distribution. Here grouping will be (3,1,1,1) and (2,2,1,1). Now for each grouping find out number of such groups 6!/3! 3! + 6!/ 2!.2!. 2! .2! =65

---

@tusharp

I havenot got. Can u explain in a detail??

Answer 1

$\color{red}{Distinguishable \ Objects \ and \ Indistinguishable \ Boxes - }$
It's similar to the problem of - Number of ways to partition a set of r objects into n non-empty subsets.
It is given by $\color{green}{Stirling \ Number \ of \ 2^{nd} \ kind}-  \color{magenta}{S(r,n)} $
Recurrence Equation - $S(r+1,n)=S(r,n-1)+ n.S(r,n)$

For the above question - r =6 and n = 4.
S(6,4) -
1
1    1
1    3     1
1    7     6     1
1    15  25  10    1
1    31  90  $\color{Orange}{65}$    15   1

$\color{DarkBlue}{Note} - 65$ is obtained as $25 \ +\ 4*(10.)$ In the similar way, all the numbers are obtained.
For more detail  - Refer this

$\color{red}{Indistinguishable \ Objects \ and \ Indistinguishable \ Boxes - }$
Refer this.

Comments

Thanku soumya29

---

@Soumya

Can u tell me, how r u calculating starling number? I am not getting ur calculation

another question is do u know where Starling number 1st kind is used?

---

@Srestha..Start with 1.. Now, for any value (say c)...See the same column say(b) and previous column value(say a) of it's above row.. now c = a +k.b were k is column number.

---

got it :)

and where to use Starling number 1st kind

---

@Srestha..
I don't know much about stirling number of 1^st kind. 
Check this .It might help you :)

---

Starling number of 1st kind is pascal triangle :)

---

There is. a direct formula for starling number

Say starling number is $S\left ( m,n \right )$

and $T\left ( m,n \right )=$ number of ways to distribute $m$ distinct object to $n$ distinct boxes so that no boxes is left empty

Now $S\left ( m,n \right )=\frac{T\left ( m,n \right )}{n!}$

For example find $S\left ( 6,4 \right )$

So, first find $T\left ( m,n \right )$

$T\left ( 6,4 \right )=4^{6}-\binom{4}{1}\left ( 4-1 \right )^{6}+\binom{4}{2}\left ( 4-2 \right )^{6}-\binom{4}{3}\left ( 4-3 \right )^{6}$

                           $=4^{6}-\binom{4}{1}\left ( 3 \right )^{6}+\binom{4}{2}\left ( 2\right )^{6}-\binom{4}{3}\left ( 1\right )^{6}$

                          $=4096-2916+384-4=1560$

Now $S\left ( 6,4 \right )=\frac{1560}{4!}=65$

---

Yeah. Same thing we do in case of de-arrangement, principle of inclusion-exclusion etc:)

---

@Soumya

Can u remember what is initial condition here for making this triangle for the formula?$S(r+1,n)=S(r,n-1)+ n.S(r,n)$

1

1.    1

.........

---

@Srestha,
$S(0,0)=1\\and \ S(0,n)=S(r,0)=0 \ where \ n,r >0$

---

and what is n and r?

I mean why not S(1,0) is not 0??

---

$S(1,0)$ is 0 only.
$n,r \in N$

Base conditions are like-
No. of ways to distribute 0 objects in 0 boxes - it's 1 way only-doing nothing
No. of ways to distribute r objects in 0 boxes - you can't distribute them because you don't have any box. - 0 ways
No. of ways to distribute 0 objects in n boxes - you can't distribute them because you don't have anything to distribute  - 0 ways
 

@Srestha, Doing GO Classroom assignment? :)

---

No , no :)

then see in the triangle, how it happens? I markd the number in red

that is S(1,0), right?

 

---

It's $S(2,1).$

---

yes,I got it now :)

I done an example like 4 distinguishable object and 2 indistinguishable boxes

then if objects are $\left \{ a,b,c,d \right \}$

then no of ways will be

$\left \{ a,b,c \right \} ,\left \{ d \right \}$

$\left \{ a,b,d\right \} ,\left \{ c \right \}$

$\left \{ a,c,d\right \} ,\left \{ b \right \}$

$\left \{ b,c,d\right \} ,\left \{ a \right \}$

$\left \{ a,b\right \} ,\left \{ c,d \right \}$

$\left \{ a,c\right \} ,\left \{ b,d \right \}$

$\left \{ b,c\right \} ,\left \{ a,d \right \}$

And total is 7 ways according to triangle too

right?

thanks a lot :)

---

@srestha mam

@Soumya29 mam

is this problem can not be solved without using stirling numbers of the second kind,is there any alternative approach?