The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
173 views
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.
asked in Combinatory by (275 points) | 173 views
0
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
0
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

1 Answer

+4 votes
Best answer

$\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.

answered by Boss (13.7k points)
selected by
0
Thanku soumya29
0
@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?
+1
@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.
0
got it :)

and where to use Starling number 1st kind
0

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

0
Starling number of 1st kind is pascal triangle :)
+2
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$
0
Yeah. Same thing we do in case of de-arrangement, principle of inclusion-exclusion etc:)
0
@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

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

I mean why not S(1,0) is not 0??
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? :)
0

No , no :)

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

that is S(1,0), right?

 

+1
It's $S(2,1).$
+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 :)

Related questions



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

42,558 questions
48,550 answers
155,305 comments
63,516 users