Certain kinds of word problems tend to be easy to misinterpret or to misstate. That is particularly true in combinatorics. Let’s look at two of those, one recent and one a few years old, where we are assigning people to groups, and the wording is not quite clear.
Committees, with a condition
First, this is from Joash (who inspired last week’s post) in March:
The question states,
A committee of six is selected from ten people, of whom A and B are two. How many committees can be formed excluding A if B is included.
My answer was 8!/(3! * 5!) = 56, or in other words 8C5. My reasoning here is that B is guaranteed to be in the Committee, so we are now selecting from 9 people instead of 10. Then since we don’t want A to be in the Committee, we are selecting 8 people instead of 9. Since B is chosen, we have 8 people to choose from for 5 leftover Committee spots.
However the Textbook Answer is 8C6 + 8C5 + 8C5 = 140
I was confused at this answer. Is there any reason for this to be the answer instead of 8C5
Recall that 8C5 (the typed version of \(_8\!\mathrm{C}_5\)) is the number of ways to choose 5 out of 8 objects.
I answered:
Hi, Joash.
How do you conclude that B is guaranteed to be in the committee? Can’t the committee be CDEFGH, excluding both A and B?
It appears that the book’s approach is that there are three cases, including only A, only B, or neither, leading to 8C5, 8C5, and 8C6 respectively.
Alternatively, you could count all committees, and subtract those with both A and B: 10C6 – 8C4 = 140.
I suspect you are misreading “excluding A if B is included”. This means that you can’t choose both A and B, but you can choose only B, and you can also exclude B and either include or exclude A.
Clearly my interpretation is that of the author (or at least the author of the solution, which may not be the same person!), since we get the same answer.
Joash conceded that this makes sense, up to a point:
You’re right.
I assumed that the question was asking how many committees include B while excluding A though I realise now that the question allows a committee without A or B. Though in this case wouldn’t the answer be the amount of cases with neither A nor B + the amount of cases with only B. Why would the amount of cases with only A be important. I understand how your alternative makes sense but the textbook answer still seems a bit confusing to me
I explained this detail:
You have to read questions in this area very, very carefully — and then read again after you write your answer!
A committee of six is selected from ten people, of whom A and B are two. How many committees can be formed excluding A if B is included.
Can both A and B be included? No, because A can’t be there if B is.
Can only B be included? Yes, because A is excluded.
Can only A be included? Yes, because there is no restriction except when B is there.
Can neither A nor B be included? Yes, because there is no restriction except when B is there.
The key idea here is that there is a restriction when B is included, but not when B is not included.
So if B is not there, then A can be included. As in logic, when the condition is false, anything goes. This is discussed in a very different context in Why, in Logic, Does “False” Imply Anything?.
But now Doctor Rick pointed out something I hadn’t noticed:
Hi, Joash, I’d like to join the discussion with a comment from my perspective. You said,
the textbook answer still seems a bit confusing to me
I would say that it’s the problem that is a bit confusing. As Doctor Peterson said, you need to read questions on combinatorics very carefully; it is also important to write questions carefully, to avoid misreading.
And when you answer questions, it is important to try to see it from the asker’s perspective!
The question was:
A committee of six is selected from ten people, of whom A and B are two. How many committees can be formed excluding A if B is included?
My first impression was also different from that implied by the given solution. In effect, I inserted a comma in my mind:
How many committees can be formed excluding A , if B is included?
This appears to be what Joash saw: Taken this way, the problem requires B to be included, and then asks how many committees can be formed without A.
… or not?
Even in this reading, I see two possible interpretations. One is that the last phrase merely emphasizes that B can be on the committee. If I had written you before reading on, I would have asked you if this was one of a set of questions on the same scenario, and in a previous question, B had been excluded. That’s the only reason I could see for writing it the way I’m taking it here.
Sometimes context is needed in order to see why a phrase is present. Here, the phrase could be added in contrast to a previous question in which B was not allowed.
But that’s probably not the most likely meaning, if the comma were present:
The other possible reading, with the comma, is that A can’t be on the committee, and B must be on the committee. I think this is the way you read it initially.
As we have seen, the intended meaning is more like this:
How many committees can be formed, in which if B is included on the committee then A is excluded from it?
This way it’s clear that if B is not included, then nothing is implied about A; A may or may not be on the committee.
Joash was satisfied:
Yeah that makes sense. Thanks for the help.
I have to say, I hadn’t noticed the ambiguity, probably because I had scanned the entire question before thinking about the problem, and having seen that their answer had three terms, I was biased to read the problem the way they were clearly thinking about it. If I had approached the problem as Joash did, I might have noticed what Doctor Rick saw. Expectations make a difference. (And I usually do try to solve a problem before looking at any proposed solution, to avoid just this situation)
Doctor Rick is right that the problem is not written clearly, and Joash’s interpretation is a valid possibility for the words as written. Often, the hardest part of a word problem is the wording, and that is true for both the reader and the writer.
My guess is that the problem actually looked something like this:
A committee of six is selected from ten people, of whom A and B are two. How many committees can be formed …
(a) …
(b) excluding A if B is included?
(c) …
If it was written this way, with several parts of which this is only one, then it makes sense to read “excluding A if B is included” as “so that if B is included, then A is excluded (not allowed)”. But put together as a single sentence, “can be formed excluding A if B is included”, it is not unnatural to take it Joash’s way.
I also observe that the wording of the problem feels much more natural to a mathematician accustomed to compact statements of logic than to a normal human! Problems ought to be written so that they are clear to the ordinary reader, and also should not depend heavily on the presence or absence of punctuation.
Editing textbooks is not an easy task! And one of the things I learn as a Math Doctor is that students, in their own context, see things I don’t notice; while I, with no context, I sometimes see difficulties neither the student nor the author may have seen – or miss them all.
Six dorm rooms, with restrictions
Looking back for other ambiguous combinatorics problems, I found this question from Jonathan in October 2022:
I have the following question.
The job has fallen to you to assign 18 incoming freshmen to rooms in one particular dormitory. There are six rooms: two quads, two triples, and two doubles.
(1) In how many ways can the 18 freshmen be assigned to the rooms?
(2) After you submitted your list of assignments from part 1 to the Dean, she complained that some of them put men and women in the same room. If we designate one of the quads, one of the triples, and one of the doubles for women, in how many ways can the rooms be assigned to nine women and nine men?
I have worked the problem and have an answer to both parts. I would just appreciate confirmation that my method is correct.
(1) This is simply a multinomial with 18!/(4!3!2!)*6, since there are six ways of choosing which pair of each room to house them in.
(2) For the women we again have a multinomial, this time with 9!/(4!3!2!)*6, since again, there are six ways of choosing which pair of each room to house them in. For the men, it is just 9!/(4!3!2!). This does not need to be multiplied by six as the rooms have already been chosen for the women and so the men take the three rooms remaining. So the solution is 9!/(4!3!2!)*6*9!/(3!3!2!).
Does this reasoning look right?
Thank you for any help.
A multinomial coefficient is the number of ways to arrange a multiset consisting of \(n_1,n_2,\dots n_k\), respectively, of each of k distinct items; it is \(\displaystyle\frac{(n_1+n_2+\dots n_k)!}{n_1!n_2!\dots n_k!}\). For example, the letters of AAAABBBCC can be arranged in \(\displaystyle\frac{9!}{4!3!2!}\) ways, because there are 9 letters: 4 A’s, 3B’s, and 2C’s. We discussed this in Arranging Letters with Duplicates.
What Jonathan wrote for part 1 doesn’t quite fit this; his answer for part 2 is a product of two of them (with an extra 6 tossed in).
I answered, this time considering interpretation issues from the start:
Hi, Jonathan.
My answers are different from yours; that may be at least partly a matter of how we interpret the problem.
Can you explain your thinking in a little more detail?
There are some good ideas there, and it could be that his thinking has good justification based on his interpretation; so that’s important to ask. Before we can really discuss the method, we need to be sure we agree on the meaning of the problem.
We often advise students to state their interpretation of a problem, clarifying any possible ambiguities, so that if their interpretation differs from the teachers, they can get credit for correctly solving their own version of the problem. Here I did that:
Here’s how I understand the problem:
The job has fallen to you to assign 18 incoming freshmen to rooms in one particular dormitory. There are six rooms: two quads, two triples, and two doubles.
In how many ways can the 18 freshmen be assigned to the rooms?
The rooms might be
1: _ _ _ _
2: _ _ _ _
3: _ _ _
4: _ _ _
5: _ _
6: _ _
We need to put names in the blanks; rooms are distinguishable, as are names, but order doesn’t matter within a room.
This is probably the only reasonable interpretation of this part, but by paraphrasing the problem in detail, in the form of a concrete model, I help myself think clearly.
For more on what it means to be distinguishable, see Six Distinguishable People in Four Distinguishable Rooms.
I now modeled my interpretation in terms of arranging letters (a multiset):
An equivalent formulation would be to line the 18 people up in a row, and assign room numbers by permuting the string
111122223334445566
I’m not sure what you mean by “there are six ways of choosing which pair of each room to house them in”, and why you multiply by 6.
Similar questions will arise for the second part.
Here I made an alternative model, listing a room number for each person, rather than people in each room. For example, the permutation 316241431522351264 would put the second, sixth, ninth, and fifteenth people in room 1.
I think that “which pair of each room” should have been “which of each pair of rooms”; but it’s still unclear.
Jonathan reconsidered:
Hi Doctor Peterson
I have considered the problem again and I now see that my thinking was faulty, at least in the first part.
The way I initially thought about it is to choose 4 people to go into a quad room, then 3 to go into a triple room and finally 2 to go into a double room. Then I said that there is a choice of two quad rooms, two triple rooms and two double rooms. There are thus six ways of choosing the actual room each of the three chosen groups of people can go into, so that is why I multiplied by six. But this is where I believe I have gone wrong. Consider the 4 chosen for the quad room. By saying that there is now a choice of 2 quad rooms to go into, I have forced them all to be in one quad room or the other. Similarly for the other rooms. What I should do is to assign 6 groups of people: 4, 4, 3, 3, 2, 2; so that the multinomial becomes 18!/(4!4!3!3!2!2!). Does this sound more reasonable?
This answer agrees with my suggestion for part 1, arranging 111122223334445566. There is no need to separately decide which of the quad rooms to use; we can just treat them as two rooms. So this is the answer, $$\frac{18!}{4!4!3!3!2!2!}=77,189,112,000.$$
Continuing, he said,
For the second part I think my initial reasoning seems sound. The choices are constrained to one of the quad rooms, one of the triple rooms and one of the double rooms. So choose 4 for the quad, 3 for the triple and 2 for the double. There are six possible arrangements of the six rooms (2 of each type) so the solution I had seems to make sense. Do you think differently?
He is explaining his original answer, which was \(\displaystyle\frac{9!}{4!3!2!}\cdot\frac{9!}{4!3!2!}\cdot6\) (assuming there was a typo in one of his numbers there), as assigning the 9 women to one set of three rooms, and the 9 men to another, and also choosing which three rooms are for women. That make sense … but not quite:
I agree on part 1.
For part 2, reconsider that number 6.
Do you see why the 6 is wrong?
Jonathan now recognized the matter of interpretation:
Hi Doctor Peterson,
After more thought it appears it’s all in the wording of the question. It says that one of the quads, one of the triples and one of the doubles is designated for the women, which I take to mean that which of the three they can occupy is already decided. Hence I do not need to multiply the multinomials by six. If the question had, instead, said that I am able to choose which of each pair of rooms they can occupy, then I would need to multiply by six.
Is this how you interpret the question?
This is the interpretational issue: Does “we designate one of the quads, one of the triples, and one of the doubles for women” mean that this designation is part of our task, and needs to be taken into account? Or does the fact that this is put before “in how many ways can the rooms be assigned” imply that it is decided first, before we start counting ways? Most of what has been said has assumed the former, but I initially assumed the latter!
I agreed, but pushed for the missing piece:
Yes, my original interpretation of part 2 was that the rooms for men and women are preassigned, so we don’t need to select them as part of our process. I think the problem is a little ambiguous on that point.
But also, if you do consider selecting the rooms as part of the count, your 6 is wrong. How many ways are there to choose 1 of 2 quads, 1 of 2 triples, and 1 of 2 doubles?
He saw the problem:
Hi Doctor Peterson,
Yes, I see the mistake. There are three binary choices of rooms, so the correct number of ways to choose the rooms is 2^3 = 8, not 6. I corrected the difficult part of the solution and overlooked the more obvious error. Still, I got there in the end, I think.
So if we have to decide which of each pair of rooms is for women, we can do that in \(2\cdot2\cdot2=2^3=8\), and then we can do the two multinomials.
We were finished:
Yes, you’ve got it.
This whole field is full of subtleties and ambiguities.
So if we suppose that the men’s/women’s room have already been assigned, the number of ways to assign students to them is $$\frac{9!}{4!3!2!}\cdot\frac{9!}{4!3!2!}=1260^2=1,587,600.$$ If we have to decide, as part of our task, which of each pair of rooms is for women, then the number becomes $$\frac{9!}{4!3!2!}\cdot\frac{9!}{4!3!2!}\cdot2^3=1,587,600\cdot8=12,700,800.$$ As we would expect, this is considerably less than the first part.