Combinatorics: Multiple Methods, Subtle Wording

(A new question of the week)

With few new questions of general interest available this week, I thought I’d go back a few months to a couple little questions on a topic we haven’t dealt with lately, combinatorics. We’ll have one question each on permutations and combinations, showing some subtlety in both the methods we use and the wording of the problem.

Permutations with a constraint

Both questions came from Jonathan, in mid-August. Here is the first:

I have taken the following question from the book Basic Probability, Henk Tijms, 2021.

Five football players A, B, C, D and E are designated to take a penalty kick after the end of a football match. In how many orders can they shoot if A must shoot immediately after C? How many if A must shoot after C?

For the first question I have taken C and A to be one player. So the problem becomes one of the permutations of four players, CA, B, D and E. The solution is simple and is 4! = 24.

For the second question, I have broken it down into four parts and added them to obtain the total.

So, with C first (Cxxxx), there are 4! = 24 permutations.

With C second, (xCxxx), B, D or E can be first, so there are 3! +3! + 3!  = 18 permutations.

With C third (xxCxx), there are 3 ways to choose the first position (B, D or E), two ways to choose the second (one has been consumed in the first position), two for the last two positions (the remaining one of B, D or E occupying one place, A the other). So there are 3 × 2 × 2= 12 permutations.

Finally, with C fourth, as A is last there are 3! ways of filling the first three places. So there are 6 permutations.

Adding these gives 24 + 18 + 12 + 6 = 60 permutations.

The answers to both parts of the question agree with those given in the book.

My question is that my solution to the second part of the question seems clunky and brute-force; I can’t help thinking there is a more terse and elegant way of achieving the answer.

Do you have any suggestions?

His thinking is good. But is there a simpler way for the second problem? We’ll offer two.

A second way

Doctor Fenton answered:

Hi Jonathan,

Thanks for writing to the Math Doctors.

Another way to count the possibilities in the second question is to choose the two places for A and C.  There are ₅C₂ = 10 ways to do that, and they must be filled in the order C A from left to right.  Having chosen the two places for A and C, there are three remaining slots for the other three players, which can be filled in 3! = 6 ways, giving a total of 10*6 = 60 orders for the players.

So here we are first choosing two places to put A and C, and placing them in a fixed order so that C is first (e.g. _ C _ _ A); then filling in the remaining blanks with the other three players, B, D, and E (e.g. D C E B A). There are 10 ways to do the first part, and, for each of those, 6 ways to do the second.

A third way

I saw an alternative:

Hi, Jonathan. I want to add another way to do it!

The way I saw the problem, any arrangement will either have A before C, or C before A. In fact, they come in pairs, so exactly half will have A after C. So we can just count all arrangements (5! = 120) and divide by 2.

One of the things I enjoy about combinatorics is that there are so often more than one way to solve the same problem — and we need that, because it is so easy to make mistakes, and checking by doing it two ways increases my confidence.

Of the 120 arrangements, we can pair up each one (e.g. D C E B A) with the reversal, D A E B C). One fits the requirement, the other doesn’t. So there are the same number of arrangements that are allowed as those that are not.

Jonathan replied,

Doctors Fenton and Peterson, many thanks for your answers. Doctor Peterson, I had thought about halving the total but could not convince myself that it was correct as I was concerned what happens when A and C occupy the fourth and fifth slots. Thinking about it again, it makes sense. I am pleased I have confirmation that this more intuitive solution is correct — as you say, it gives one confidence. Thank you both again.

Taking the time to convince yourself that an intuitive feeling is right, is what makes you a mathematician! Too many students either go with whatever feels right (which sometimes works!), or are afraid to try unless they know from the start what to do. Getting an idea and testing it is something we all need practice with.

Combinations with a twist

Here is the second question, submitted the next day:

I have taken the following question from the book Basic Probability, Henk Tijms, 2021.

John and Pete are among 10 players who are to be divided into two teams A and B, each consisting of five players. How many formations of the two teams are possible so that John and Pete belong to a [sic] team?

I have reasoned thus:

The team with John and Pete can be formed ₈C₃ ways, giving 8!/(3!5!) = 56.

The answer is given as 112. I can see that this is double the answer I have, suggesting that the second team needs to be taken into account. But surely, once the first team is chosen the members of the second team are forced.

I am concerned I have I missed something fundamental here.

Are you able to put me right?

I have often commented that English can be the hardest part of a math problem. What does “John and Pete belong to a team” mean? In different contexts, it might mean that each of them belongs to a team, or that they belong to the same team, or that they both belong to some particular team. Jonathan has called our attention to the word “a”, which seems to be poorly chosen; but the main difficulty is a little deeper than that.

[Incidentally, in editing this post, I found the problem in the book online, and it actually says,

In my own dialect, “to a same team” is ungrammatical, or at least non-idiomatic; I have seen this form used by speakers of other languages, where perhaps there is a similar construction. I understand it here to mean that they are on the same team but we don’t care / know which it is.]

In general, in combinatorics we need to determine what entities are “distinct” or “distinguishable” (e.g. the players, and the teams), and what outcomes are to be counted as “different” (e.g. mere team membership as opposed to order within a team). There is something a little more subtle in this problem.

Named teams are distinguishable

I answered:

Hi, Jonathan.

The issue here is the subtlety of the wording of combinatorial problems. You’ve observed, I think, that “a team” is to be taken as meaning “the same team”; the wording could have been clearer. Similarly, we need to determine what differences to take into account in our answer.

The key is that the teams are given specific names, A and B, which makes them distinguishable. So having John and Pete on team A is different from having them on team B. So in counting, we need to first choose which team to put them on (2 ways), and then choose who else to put on that team (₈C₃ = 56). The total is then 2*56 = 112.

Jonathan’s method in effect put John and Pete on one team, chose 3 of the other 8 players to join them, and put the rest on the other team. So he is leaving the teams unnamed, just thought of as “our team” and “the other team”:

J P _ _ _ vs _ _ _ _ _

We need to also assign names to the two teams, in order to do what was asked:

A: J P _ _ _ vs B: _ _ _ _ _

or

A: _ _ _ _ _ vs B: J P _ _ _

This is why one of the first things I do when I’m faced with a problem like this is to ask, “Are the items (here, people) distinguishable? Are the groups (here, teams) distinguishable?” That often determines how I approach the problem. Also, I often find myself unsure!

Here, everything would change if “a team” were “team A”! It would also change if the teams had not been named, and we were just asked, “In how many ways can two teams be formed?”

If it were specified that John and Pete were on a specific named team, we would not have to choose, removing that factor of 2; if the teams were not named, we would likewise have no such choice. We would have indistinguishable teams.

Jonathan replied,

Doctor Peterson, Thank you for your answer. I understand this now. It appears to be all in the wording as you say. I the question as given, the teams are distinct. If the question asked, “How many ways could a team of five be made?“, then 56 would be correct. Is that so?

Here we are only making one team, and ignoring the 5 not on it:

Team: _ _ _ _ _

I responded:

Correct, assuming you are requiring John and Pete to be on that team. It would be different if you required that if either of them is on the team, then the other must also be on it.

That is, his calculation assumes John and Pete are on the one team, which makes this equivalent to his original calculation where he assumed they are on the first team:

On team: J P _ _ _ vs not on team: _ _ _ _ _

But if we only require them either both to be on the team, or both off, then we again have two cases to count:

On team: J P _ _ _ vs not on team: _ _ _ _ _, or On team: _ _ _ _ _ vs not on team: J P _ _ _

Jonathan asked,

Is there a distinction between the two?

I said,

Suppose the problem said this:

John and Pete are among 10 players, from whom 5 are to be picked for a special team. How many formations of the two teams are possible if John and Pete insist on being together, so that if one is on the team, then the other must be on it as well?

Then the possibilities include the ₈C₃ cases where both are on it, together with the ₈C₅ cases where neither is on it.

If two (indistinguishable) teams were being picked, there would be no difference, because one team would have both and the other would have neither; but here I’m starting from your question, “How many ways could a team of five be made?”.

Jonathan answered:

Thank you for clarifying this.

I can see the whole area of combinatorics is subtle and vexed and careful reading (and wording) is essential.

It is indeed!