(An archive question of the week)
Last time we looked at some elementary problems in combinatorics, where we counted the number of ways to choose or arrange elements of a set. Let’s look at a somewhat more complicated problem, which will demonstrate issues that come up in interpreting such a problem and in choosing a way to solve it. We’ll be using each of the basic methods we saw last time (products, permutations, and combinations), each in its place.
The question: assigning rooms
Here is the question, from 2013:
Maximum Occupancy A hotel has four vacant rooms. Each room can accommodate a maximum of four people. In how many ways can six people be accommodated in the four rooms? There seems to be lots of different configurations, e.g., zero people in rooms 1 and 2, two in room 3, and four in room 4. I tried to use multisets but couldn't get the (n + r - 1)Cr formula to make sense.
Guy mentions knowing about multiset combinations, which I will be looking at in the future; briefly, that refers to “sets” in which an element can occur more than once. That idea was probably suggested by the fact that each room might be selected by more than one person. That might be a good thought, but before we choose the tools to use for a project, we have to be sure of our goals. So Doctor Ian wrote back, as we often do, asking for clarification:
The first thing to do is define what you mean by "ways." That is, consider this assignment: Room 1: Bob, Carol Room 2: Ted, Alice Room 3: Mick Room 4: Keith Is that a different "way" than this? Room 1: Mick, Carol Room 2: Keith, Alice Room 3: Bob Room 4: Ted Or are you just looking for the number of people that you can put in each room? And if that's the case, consider this assignment: Room 1: 2 people Room 2: 2 people Room 3: 1 person Room 4: 1 person Is that a different "way" than this? Room 1: 2 people Room 2: 1 person Room 3: 2 people Room 4: 1 person Or are you just looking for the number of ways to partition 10 items into 4 groups? And if so, is 0 a legitimate group size?
The first two examples illustrate the question, whether the people are to be considered “distinguishable”: that is, does it matter who is in a given room, or do we only care about how many are in each room? The third example shows how we would describe the first two under the assumption of indistinguishable people; the fourth, by comparison, illustrates the question, whether the rooms are to be considered distinguishable. If they are indistinguishable, then we only care about the numbers of people, not where they are.
Clarifications
I started pondering ways to solve this, under the interpretation that made most sense to me; meanwhile, Guy responded with more information as well as his own reading of the problem:
Thank you, Doctor Ian, for posing these questions. The way I read the question is that we have four rooms, A, B, C, and D. A room can have from zero to four occupants. We are asked for the number of ways six persons can be accommodated. I'm trying to envisage this as a stars and bars problem, but cannot get any of the multiple choice answers (4020, 4068, 4080, or 4096). As these are large numbers, I'd assume that ABCD = 0303 is different from ABCD = 3003. Although I'd like to solve this specific problem, I'm really more interested in gaining the intuition to know how to tackle counting problems in general.
He mentions here the “stars and bars” technique, which I plan to cover soon, and which is often used in connection with multisets. I won’t be using that, but perhaps we could.
He also shows us an idea he’s had for a notation for thinking about the problem, listing the number of people in each of the four rooms (A, B, C, and D) as a way to identify one way to assign them. (This implicitly assumes that the people are indistinguishable.)
He also tells us that this is a multiple-choice question, and gives the choices. I dislike multiple-choice questions in general, but this is a good example where listing choices can help in validating one’s interpretation of a problem and getting feedback on an answer. When a problem is multiple-choice and you don’t tell us the choices, that may handicap us. So now we are better prepared to answer the question.
I had already worked out an answer, which agreed with one of the choices, so I passed that information on to Doctor Ian, who said to take over the discussion. So I did, first confirming the interpretation:
Hi, Guy. I took a look at this question after Dr. Ian responded, and found that I could get one of the listed answers by interpreting the problem as treating not only the rooms as distinguishable, but also the people. I considered that likely because any other interpretation would probably produce smaller numbers; and this does seem like a reasonable reading of the exact words of the problem. We want to find the number of ways to assign people A, B, C, D, E, and F to rooms 1, 2, 3, and 4, such that each person has a room, and each room may have from 0 through 4 occupants.
I reversed the naming from Guy’s approach, using letters for names and numbers for rooms — not intentionally, but because it seemed most natural to me. It was also helpful to make a fresh start.
Rather than give you the answer, I want to give you a chance to find it, knowing what the correct interpretation is. My basic approach (which probably can be improved upon) was to first find the number of ways to assign each of the 6 people to one of the 4 rooms without any restrictions. The fact that this produced a number of assignments in the right ballpark was encouraging. Then I had to exclude all assignments that put 5 or 6 of them to the same room. I did this by subtracting the number of ways to do each (which required looking at the problem from different perspectives).
So I had chosen a subtractive strategy. This is probably not the only way, but it worked for me. (Details are coming!)
As to your broader question -- how to tackle such problems in general -- I've tried to describe my thinking above in a way that highlights some of the key ideas. While I may try different models, such as the stars and bars approach that you mentioned, I just look at a problem like this in as many different ways as possible, sometimes starting with the slots, sometimes with the people who go in them. Ultimately, I don't think there's necessarily any single technique that will shorten this exploratory phase. Rather, you must build up enough experience that you start to develop an intuition, however ineffable. (I don't claim to have that; others of us apparently do ... but don't try to explain it!)
My comment about starting with the slots or with the people is illustrated here:
Reverse Permutation Doubt
My comment about some of us having the necessary intuition mostly referred to Doctor Anthony, who will show up often as we look at combinatorics. He often solved these problems without explanation of the process by which he found the solution, sometimes astonishing me. I comfort myself with the knowledge that figuring something out along with a student can be more productive pedagogically than producing a fully-formed answer.
A near miss
Guy responded with his attempt based on my suggestion, which turns out to be almost correct:
Many thanks, Dr. Peterson, for your illuminating comments. I tried your approach as follows: 1) If there were no room capacity constraints, then the number of ways of allocating six people to four rooms would be 4^6 = 4096, I believe. Would you agree? Note that I am not distinguishing between rooms or between people. 2) From 4096 I then tried to deduct the number of ways that allocated 6 people to one room, which I take to be 4 (the six people would be in one of the four rooms), giving us 4096 - 4 = 4092. 3) From 4092 I then deducted the number of ways that allocated 5 persons to one room and one person to one of the other three rooms. I took this to be 4 times 3 = 12, giving us 4092 - 12 = 4080, or multiple choice answer (C). What do you think?
He also asked a more general question, which I’ll quote later.
Multiple models
I answered, starting with his first step:
This is the right thing to do; but it appears that you have a misunderstanding about what "distinguishable" means, which will affect what you do later. You ARE distinguishing between rooms, and between people!
I said this (as I’ll make clearer below) because his \(4^6\) is the number of ways to assign one of four distinct rooms to each of six distinct people.
I avoid blindly using formulas, in order to make sure I'm thinking correctly about them. What is it that you are doing when you apply the formula n^k to find the number of ways to assign one of n values to k things? I think of it like this.
We have 6 blanks (one for each person), each of which has to be filled in with a room number:
room: ___ ___ ___ ___ ___ ___
A B C D E F
For example, one such assignment would be
room: _3_ _1_ _2_ _3_ _1_ _1_
A B C D E F
We want to count how many ways this can be done. There are 4 ways to fill in the first blank, and for each of these there are 4 ways to fill in the second, and so on, for a total of 4*4*4*4*4*4 = 4^6 = 4096.
Are we distinguishing people? Absolutely -- each blank represents a different person. We don't treat them differently, but we do treat them as distinct individuals, which is the point here. EACH PERSON is assigned a room of his own. These two assignments are counted as different, even though each room has the same number of people:
room: _3_ _1_ _2_ _3_ _1_ _1_
A B C D E F
room: _1_ _1_ _1_ _2_ _3_ _3_
A B C D E F
Are we distinguishing rooms? Certainly -- each room has a number that we are using the represent it. Each person is assigned SOME PARTICULAR ROOM. These two assignments are counted as different, even though the same groups of people share rooms:
room: _3_ _1_ _2_ _3_ _1_ _1_
A B C D E F
room: _4_ _2_ _3_ _4_ _2_ _2_
A B C D E F
That's the key to my interpretation of the problem: we are not just recording how many people are in each room, as you did initially (this would amount to treating the people as indistinguishable), but which ones. Moreover, we are not ignoring which room has which number (equivalent to treating the rooms as indistinguishable).
So let's keep this in mind as we proceed.
Now we have a clear idea of what is being distinguished, and a model that respects those distinctions. (I used a blank per person rather than per room, because each person has to be in a room, whereas each room might have various numbers of people, including none.)
Guy had the right answer for this part of the problem (ignoring restrictions on occupancy), but the wrong model. So far, our answer to the problem is $$4^6\ -\ (\text{6 in one room})\ -\ (\text{5 in one room}).$$
Now I moved on to his second step (counting assignments that put 6 in a room, for which he counted 4):
This is correct. Note that, as I mentioned, we are looking at this part of the problem from a different perspective. Rather than thinking of the people as a list of blanks to fill in with room numbers, we are now thinking of the rooms as a list of blanks to fill in with people: Room 1: _A_B_C_D_E_F_ Room 2: _____________ Room 3: _____________ Room 4: _____________ We just have to choose ONE room to fill, and put all the people into it, so there is no NEED to distinguish the people. (That would mean keeping track of the order in which they enter the room, perhaps which bed they sleep in, which is irrelevant to the problem.) So there are 4 of our 4096 assignments that we leave out because they have 6 to a room, which is not allowed. We are still treating the people as distinct; there just happen to be no distinctions to make for this step. Note that in this model, we are really using the blanks as mere check-boxes; each is either chosen or not, and in this case we just had to choose one of them.
I made some additional comments on models:
Once we've done this counting, we have the following four cases to subtract from the list we got when we ignored constraints:
room: _1_ _1_ _1_ _1_ _1_ _1_
A B C D E F
room: _2_ _2_ _2_ _2_ _2_ _2_
A B C D E F
room: _3_ _3_ _3_ _3_ _3_ _3_
A B C D E F
room: _4_ _4_ _4_ _4_ _4_ _4_
A B C D E F
Also, note that we could have an even more general model, in which each combination of room and person is recorded:
Room 1: ___ ___ ___ ___ ___ ___
Room 2: ___ ___ ___ ___ ___ ___
Room 3: ___ ___ ___ ___ ___ ___
Room 4: ___ ___ ___ ___ ___ ___
A B C D E F
These would just be check-boxes; but this doesn't model our situation at all well, since there is nothing to keep the same person from being assigned several different rooms. (This would fit if we were just giving out keys to the rooms, rather than putting people in them.) This idea of fitting the model to the details of the problem is important both in solving the problem, and in thinking through what the problem means.
So far, our answer to the problem is $$4^6\ -\ {4 \choose 1}\ -\ (\text{5 in one room}).$$
Correcting the error
Now I dealt with his third step (counting assignments that put five in one room, for which he counted 12):
This is where you went wrong. We ARE distinguishing between persons, so, as you mention below, we have to count not just the number of ways to choose a 5-person room and a 1-person room, but also how we assign the people to those rooms, which amounts to simply choosing who goes in the single room. That multiplies the answer by 6.
Here are two sample assignments (among many) that have to be considered different:
room: _3_ _3_ _3_ _3_ _3_ _1_
A B C D E F
room: _3_ _3_ _3_ _1_ _3_ _3_
A B C D E F
Both were counted in the 4^6 possibilities, so both have to be subtracted from it.
Note that here we have to think about two models in two steps: the blank-per-room model for choosing the two rooms (choosing one to hold 1 person and one to hold 5), giving 12 possibilities ...
Room 1: _1_
Room 2: ___
Room 3: _5_
Room 4: ___
... and the blank-per-person check-box model for choosing the person to go in the singleton:
room: ___ ___ ___ ___ ___ _x_
A B C D E F
This gives a total of 72 possibilities.
So at this step we count permutations of 4 rooms taken 2 at a time (which Guy had done), and multiply by the combinations of 6 people taken 1 at a time.
Our final answer to the problem is $$4^6\ -\ {4 \choose 1} -\ _4P_2\ \cdot {6 \choose 1}\ =\ 4096\ -\ 4\ -\ 12\ \cdot\ 6 = 4020.$$
Now, here is the conclusion of Guy’s response, after showing his work and arriving at 4080:
In these word problems, so much depends on one's interpretation of the meaning of the words and on one's understanding of those words in the given context. I could imagine two different answers being "correct" given two interpretations of the meaning of the word problem. For example, if I thought we should distinguish between persons, then in case 3) I might calculate the number of ways of allocating 5 persons to one room and one (particular) person to one of the other three rooms as 4 times 3 times 6, where 6 is the number of ways I could choose 1 person from 6. This equals 72, giving us 4096 - 4 - 72 = 4020, or multiple choice answer (A). What is an unfortunate maths student to do?
Do you see what he has done? He found the correct solution, but thought it was wrong, because he thought he was not distinguishing people. I answered:
Yes, as we saw earlier, there are several ways you could interpret the words, though I think this interpretation does fit the wording best. In this case, seeing the multiple choices helped make that decision: they suggestively include each wrong answer you are likely to give for the problem AS RIGHTLY INTERPRETED. A well-worded problem should avoid this ambiguity of meaning, but will still require careful thinking about the implications of its meaning for the models we use. And (A) is the answer I got.
In conclusion:
I guess the thing to do is just to think very carefully about each problem, doing many different variations and pondering what you learned from each of them, so that you build up a sense of what possibilities there are to look for, and how to recognize them. There are whole books on "how to count," for this reason! Combinatorics is a big and challenging subject.
One final comment: It does seem reasonable to have interpreted the problem in terms of indistinguishable people. To answer that problem, I would use the stars and bars technique (coming soon!), and the same subtractions Guy used. I get 68 ways. Check and see if I’m right …