Combinatoric Homework Problem

[chiachu]

This is a homework problem that i can not figure out.

An elevator with 9 passengers stops at 5 different floors. If we are only interested in the passengers who get off together, how many possible distributions are there?

Thanks in advance for any help.

[fnord_too]

[ QUOTE ]
This is a homework problem that i can not figure out.

An elevator with 9 passengers stops at 5 different floors. If we are only interested in the passengers who get off together, how many possible distributions are there?

Thanks in advance for any help.

[/ QUOTE ]

Assumption: At least one person gets off at every stop.
Assumption: Which stop people get off at does not matter (that is, say two people get off at a stop, the only important thing is that these two people got off at the same stop, not that they got off at a specific stop.)

Since at least 1 person gets off at each stop, label the first person off at stop 1 "1", the first person off at stop 2 "2", etc.

(Arbitrarily lable the last four passengers 6, 7, 8, and 9)

How many ways can 4 distinct people get off at 5 stops? (If you have trouble with this bit, ask after you have chewed on it for a while. If the assumptions are invalid, let me know).

[chiachu]

my assumption after reading the problem was that:

- the 9 people are indistinguishable
- 0 people could get off on any floor
- the floor in which they got off on is significant

Whats stumping me is how to prevent from counting the same distribution more than once. Since we are only interested in the people who leave in a group of 2 or more, 61110 is the same distibution as 61101, 61011 and 60111 (where the first digit is the number of people getting off on the 1st floor, 2nd digit, 2nd floor etc.) And i have no idea how to handle this [img]/images/graemlins/crazy.gif[/img]

[gergery]

I’m new at this but
If the 9 are indistinguishable, then I’d think you would enumerate each case, then multiply by how those cases can occur.

So how can people get off the elevator?
9 people at one floor, no people at the other four floors (9,0,0,0,0)
8 people at one floor, 1 person at different floor (8,1,0,0,0)
7 people at one floor, 2 people at different floor (7,2,0,0,0)
7 people at one floor, 1 person at another floor (7,1,1,0,0)
etc, down to (2,2,2,2,1)

Then multiply each case by the ways it can be sorted –ie. pick.
(9,0,0,0,0) can be sorted in P(5,1) ways
(8,1,0,0,0) can be sorted in P(5,2) ways

Then add ‘em up.

Since the people are indistinguishable, you don’t need to then multiply by which people get off ie. (8,1,0,0,0) can be chosen C(9,8) ways.

[fnord_too]

The only way I can think to do that is just iterate through them.

9
8,1
7,2
7,1,1
6,3
6,2,1
6,1,1,1
5,4
5,3,1
5,2,1,1
5,1,1,1,1
4,4,1
4,3,2
4,3,1,1
4,2,2,1
4,2,1,1,1
3,3,3
3,3,2,1
3,3,1,1,1
3,2,2,1,1
2,2,2,2,1

so 21 if I have not missed any. There is probably a more ellegant way, but it does not leap to mind. (I wish I could remeber what Bell(?) and Sterling(?) numbers were.)

[gergery]

read these for an excellent summary of how to think thru different combinatoric problems

[chiachu]

thank you for the replys. I was hoping there was some sort of nice trick to do it... but oh well [img]/images/graemlins/grin.gif[/img]

[Hojglad]

[ QUOTE ]
thank you for the replys. I was hoping there was some sort of nice trick to do it... but oh well [img]/images/graemlins/grin.gif[/img]

[/ QUOTE ]
Stars and bars. 9 stars, 4 bars. Google for elaboration. That enumeration provided is nowhere close to correct.

Spoiler below (which gives the total number of ways that 9 passengers can get off on 5 floors assuming all passengers exit the elevator by the 5th floor):

<font color="white"> Solution: C(13,4) </font>

[gergery]

[ QUOTE ]
[ QUOTE ]
thank you for the replys. I was hoping there was some sort of nice trick to do it... but oh well [img]/images/graemlins/grin.gif[/img]

[/ QUOTE ]
Stars and bars. 9 stars, 4 bars. Google for elaboration. That enumeration provided is nowhere close to correct.

Spoiler below (which gives the total number of ways that 9 passengers can get off on 5 floors assuming all passengers exit the elevator by the 5th floor):

<font color="white"> Solution: C(13,4) </font>

[/ QUOTE ]

I don't think I've been this wrong answering a post in....well, ever.

[tpir90036]

[ QUOTE ]
thank you for the replys. I was hoping there was some sort of nice trick to do it... but oh well [img]/images/graemlins/grin.gif[/img]

[/ QUOTE ]
I only looked at it quickly but the "stars and bars" reference makes me think you can use multichoose.