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 /images/graemlins/crazy.gif

[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 (http://www.math.sfu.ca/~alspach/pokerdigest.html) 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 /images/graemlins/grin.gif

[Hojglad]

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

[/ 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 /images/graemlins/grin.gif

[/ 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 /images/graemlins/grin.gif

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

[PairTheBoard]

chiachu:"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?"

Especially: "we are only interested in the passengers who get off together"

I don't see that anyone has correctly read the problem. As stated, the different combinations are determined by the subgroupings of identifiable passengers.

For example, suppose the passengers are A,B,C,D,E,F,G,H,I. Suppose A,C,E,G,I get of on Floor 2 and the rest, B,D,F,H get off on Floor 4. That's One distinct combination we're "interested in". Now suppose B,D,F,H get off on Floor 2 and the other group A,C,E,G,I get off on Floor 4. That's NOT another distinct combination because "we are only interested in the passengers who get off together" not on which floor they do so. HOWEVER, if A,B,C,D,E get off on Floor 2 and F,G,H,I get off on Floor 4 that IS another distinct combination because different passengers have gotten off together.

I would assume that passengers may get off on All Five Floors. There is nothing in the problem which specifically disallows departure on one of the floors so I would not try to conclude such a restriction. Nothing is said about when the 9 passengers got on the Elevator nor whether some of the 9 might want to get off on Floor 1 of the 5. If floor 1 is the Ground Floor it's possible some passengers get on to make the 9 and some then get off from their trip down. The KISS version is that 9 passengers are on the elevator going up where 5 stops are made. In either case I would assume that after visiting all 5 stops that all passengers have reached their floor and will have departed.

I believe this is the correct reading as chiachu states the problem. If he has paraphrased the problem incorrectly rather than giving us an exact quote for it then all I can say is, may the Lord have Mercy on his Soul.

I leave it to those who feel like the exercise to give a correct solution to the correct reading of the problem.

PairTheBoard

[chiachu]

wow i didnt even know this thread was still going. /images/graemlins/grin.gif

i quoted the problem exactly, but it is written terribly. Especially that one line that 'pairtheboard' quoted. Our profesor actually told us not to do the problem a few days ago, but im still curious to the solution.

After reading 'pairtheboard' take on the problem, i think he is correct in interpreting the question.

[PairTheBoard]

I'm afraid I can't see a slick way to do it ciachu. Grinding it out looks to be a real chore to me.

There's 1 way they can get off on 1 floor.

The number of ways they can get off on 2 floors is
C(9,8) + C(9,7) + C(9,6) + C(9,5) accounting for when they get off in groups of (8,1),(7,2),(6,3),(5,4).

Getting off on three floors can be done in groups of
(7,1,1) (6,1,2) (5,3,1) (5,2,2) (4,4,1) (4,3,2) (3,3,3)

where care must be taken in counting the ways eg. for (3,3,3) as C(9/3)C(6/3)/2 to eliminate double counting with order.

The rest can be ground out similiarly. If there's a slick way to do it I'd like to see it. Hell chiachu, you're the one studying combinatorics. You come up with it.

PairTheBoard