Combination / Permuations Question

G

grapz

Junior Member
Joined
Jan 13, 2007
Messages
80
15 friends must be checked into 5 rooms in a hotel. HOw many ways is this possible if each room cannot have more than 4 people?


I have trouble understanding this problem, and dont' know where to begin
 
Are we to assume that the rooms are distinct? Are the rooms numbered?
 
Since people and rooms are distinct. This is a little tricky. pka will certainly correct me if I'm wrong.

\(\displaystyle \L\\\sum\frac{15!}{a!b!c!d!e!}\)

Sum over all a,b,c,d,e 5-tuples where a+b+c+d+e=15 with no letter > 4.
 
galactus said:
\(\displaystyle \L\\\sum\frac{15!}{a!b!c!d!e!}\)
Sum over all a,b,c,d,e 5-tuples where a+b+c+d+e=15 with no letter > 4.
Click to expand...
That is certainly a reasonable way to frame this answer. However, it does not lead to any closed form solution. But it is correct.

This is a very, very difficult problem. So difficult that I doubt that whoever set the problem has no idea how to solve it. You are being asked to count the number of mappings from a set of 15 to a set of 5 having the property that no set of pairs in the mapping has more than four members with the same second term.
 
I was thinking perhaps the sort of set up I posted was all that was required other than a closed-form solution. I may be wrong. Either way, as you said pka, it's a booger of a problem.

Correct me if I am in error, but using the numbers 1 through 4 that sum to fifteen, where 5 of them are required would be:

\(\displaystyle \L\\\left(\sum_{k=1}^{4}x^{k}\right)^{5}\)

By looking at the power of 15, the coefficient is 101. I believe the answer is 101 total such 5-tuples. That's quite the conundrum.
 
If you had used \(\displaystyle \sum\limits_{k = 0}^4 {}\) then that would give us 121, the number of ways to put 15 identical objects into 5 different cells with at most 4 is any cell. However, that allows some cell to be empty such as (4,4,4,3,0); that was not ruled out by the problem. But as I wrote above, we are mapping a set of 15 individuals to a set of 5 different rooms; the solution calls on us to count functions.
 
You must log in or register to reply here.
Top