Distinguishable objects in indistinguishable bins

White_Owl · 2010-03-22 03:31:49

The Rosen's book, problem 5.5 #50:
How many ways are there to distribute 5 distinguishable objects into 3 indistinguishable bins?

One approach to such problems I know is to imagine distinguishable objects as a long box with compartments, indistinguishable objects as balls and by looking at the balls and separators between compartments we are getting a string of "O" and "l" which can be permuted and that would be the answer...
The only problem here is that as far as I understand this approach, it works perfectly well if number of indistinguishable objects are greater than number of distinguishable. But if number of distinguishable is greater (like in the problem) I am getting strings like:

a, b, c, d, e here are distinguishable objects represented as compartments. But with this representation I always have some empty compartments - distinguishable objects which are not in any indistinguishable bins...

Another, more promising, approach is to just make a list from letters and separators: "abcde||", "abcd|e|", etc. That would accurately represent distinguishable objects and distinguishable bins. But the original problem states that bins should be indistinguishable, so "abcde||" == "|abcde|" == "||abcde"...
.....hmm....
The process of writing this topic gave me an idea. If we define objects as O and bins as B, then to get the answer it should be enough to count the number of permutations of the string (

) and divide them by number of bins. Am I right or not?

I spent a week thinking about this problem and now I can not believe the answer can be so simple...

White_Owl · 2010-03-22 03:51:43

No, the answer is not so simple.
"abcde||" == "|abcde|" == "||abcde" == "acdeb||" == "ecbad||" == etc...
All permutations of objects inside one bin should be treated as the same combination.
The number of combinations where all objects are inside one of the bins is

When we move one object to another bin we have

When we move two objects to another bin we have

etc...

But how to squeeze all that in one nice formula???

bobbym · 2010-03-22 10:49:29

Hi White_Owl;

I am getting 41 ways to put 5 distinguishable objects into 3 indistinguishable bins.

soroban · 2010-03-22 16:25:55

. .

Edit: Corrected a really silly error . . . *blush*
.

Last edited by soroban (2010-03-23 05:13:38)

bobbym · 2010-03-22 16:54:48

Hi;

Here is how I get 41:

First the number of ways to distribute 5 distinguishable objects into 3 indistinguishable bins.

http://2000clicks.com/MathHelp/Counting … Boxes.aspx

http://webcache.googleusercontent.com/s … l=en&gl=us

The answer is the sum of the stirling numbers of the second kind.

They are computed like this:

To distribute n distinguishable objects into k indistinguishable bins.

It can also be done by using the tables provided in the links

stirling2(5,1) + stirling2(5,2) + stirling2(5,3) = 1 + 15 + 25 = 41

By direct count, distribute a,b,c,d,e into 1,2 and 3 bins.

1 + 15 + 25 = 41

White_Owl · 2010-03-23 01:42:54

bobbym wrote:

Here is how I get 41:

To distribute n distinguishable objects into k indistinguishable bins.

Wow! Now I would need another week to decipher it.
Thank you.

White_Owl · 2010-03-23 02:24:18

soroban, Sorry, you made two mistakes:

soroban wrote:

And here you forgot the very first case with all objects together. So the final summation should be

bobbym · 2010-03-23 14:20:00

Hi White_Owl;

Now I would need another week to decipher it.

It is just the sum of the stirling numbers of the second kind. Actually soroban did a really nice job on this problem.

White_Owl · 2010-03-24 01:52:20

bobbym wrote:

It is just the sum of the stirling numbers of the second kind.

The problem with "stirling number of the second kind" is that I did not read about them yet

bobbym wrote:

Actually soroban did a really nice job on this problem.

Yes, he sure did.

White_Owl · 2010-03-25 09:04:55

Ok... I finished the chapter 5.5 and at the end of it I found the description of this formula. So I tried to do a manual calculation and received -41 (negative 41)... After a while I realized that I made a mistake in writing formula down and replaced the i with j in one place (powered -1 before the binom).
But now I have an interesting equality:

I wonder, is it correct or not? How do we prove the equations with in it? By induction?

bobbym · 2010-03-25 15:17:23

Hi;

I am not getting that as an identity yet, because when you try

You get:

8,-8

White_Owl · 2010-03-26 01:30:38

Ok, then how about this one?

bobbym · 2010-03-26 14:29:05

Hi White_Owl;

Not yet:

n = 5, k = 4 yields 151 / 3 for the LHS and 51 for the RHS.

Ricky · 2010-03-27 05:33:36

As a general principle in mathematics, if your formula is off for one number, it is probably off for infinitely many others.

Math Is Fun Forum

#1 2010-03-22 03:31:49

Distinguishable objects in indistinguishable bins

#2 2010-03-22 03:51:43

Re: Distinguishable objects in indistinguishable bins

#3 2010-03-22 10:49:29

Re: Distinguishable objects in indistinguishable bins

#4 2010-03-22 16:25:55

Re: Distinguishable objects in indistinguishable bins

#5 2010-03-22 16:54:48

Re: Distinguishable objects in indistinguishable bins

#6 2010-03-23 01:42:54

Re: Distinguishable objects in indistinguishable bins

#7 2010-03-23 02:24:18

Re: Distinguishable objects in indistinguishable bins

#8 2010-03-23 14:20:00

Re: Distinguishable objects in indistinguishable bins

#9 2010-03-24 01:52:20

Re: Distinguishable objects in indistinguishable bins

#10 2010-03-25 09:04:55

Re: Distinguishable objects in indistinguishable bins

#11 2010-03-25 15:17:23

Re: Distinguishable objects in indistinguishable bins

#12 2010-03-26 01:30:38

Re: Distinguishable objects in indistinguishable bins

#13 2010-03-26 14:29:05

Re: Distinguishable objects in indistinguishable bins

#14 2010-03-27 05:33:36

Re: Distinguishable objects in indistinguishable bins

Board footer