Now that you’ve decided on your outfit, you take a trip to the cinema with a friend. When you get there, you see that there are only two seats left and they are next to each other. In how many different ways can you and your friend occupy these two seats? Well, once seated, either you will be sitting on the left and your friend will be to the right of you or you are sitting on the right with your friend on your left. So there are two ways in total. This is very easy to see, but what if there were three of you and three seats left? In how many ways can you and your two friends occupy the three seats?

In my opinion, the answer is immediately unclear and, to someone with little or no experience of doing mathematics, the question I’ve just asked is an example of how a problem about counting how many of something there is can fail to be easy. It will sometimes be suggested or joked (or worse – boasted) by people who know very little mathematics that they can do little more than count. However, counting can be extremely difficult! As ‘research’, I once spent some time asking lots of different people this problem and very few answered correctly without hints, or being given some sort of method.

Think back the first post. When counting the number of outfits one could make from three tops and two pairs of jeans, one multiplies two by three to get the answer. So, if we are making up seating arrangements from three people and three seats, we multiply three by three to get nine… right? Well, no. (In fact, when doing my ‘research’ I sometimes asked people the problem about outfits first. When I did, the response of ‘nine’ to this new problem was very common it would be interesting to do this research properly and get some statistics).

Despite this common error, one can still link the solution to this problem to that of the previous problem. In order to do so, let’s focus on exactly why we multiplied three by two to get the answer in the previous post. Recall that the fundamental observation was that the number of available pairs of jeans from which to choose did not depend on which top was chosen, and vice-versa.

Can we apply a similar logic here? In order to make this really clear, suppose that one of your friends arrives early. Suppose that she takes the leftmost seat. Later, you and your other friend arrive… Now, there are only two seats left and they are next to each other. In how many different ways can you and your friend occupy these two seats? Ah! We already know this: There are two ways. Similarly, if your early friend takes the rightmost seat, there are still two ways for you and your other friend to occupy the two remaining seats. Lastly, if your early friend sits in the middle seat, there are still two ways in which the remaining seats can be occupied. So, this is promising: The number of ways in which the remaining two seats can be occupied does not depend on which seat your early friend takes. Looking at things the other way around, there are three ways in which your early friend can choose his seat and the number of ways in which in which this choice can be made doesn’t depend on how the remaining seats go on to be filled. So, we really can make the same fundamental observation: The number of ways in which the first seat can be filled (three) does not depend on the number of ways in which the other two seats can be filled (two) and vice versa. Hence the total number of ways to fill the seats is two times three, which is six.

More

Suppose that there are four friends and four seats. Again, one friend arrives early. In how many ways can she choose her seat? Obviously four. Then the other three arrive. There are three seats left. In how many ways can they sit down? Well, again we already know this. There are six ways. Crucially, the fundamental observation is still valid: The number of ways in which the first seat can be filled (four) does not depend on the number of ways in which the other three seats can be filled (six) and vice versa. Therefore there are 24 ways in which the four friends can sit down because 24 is six times four. You ought to be beginning to see a pattern.

For five friends and five seats we’d have 120 = 5 x 24 ways. To labour the point and reiterate what we’ve done, let’s briefly exposit an alternative approach: We arrived at 24 as the answer for the ‘four friends and four seats’ problem because 24 = 4 x 6 and because 6 is the answer to the ‘three friends and three seats’ problem. We arrived at 6 because 6 = 3 x 2 and  2 is the answer to the ‘two friends and two seats’ problem. Putting this all together, we have the rather elegant observation that the number of ways that five friends can sit in five seats is 5 x 4 x 3 x 2. Writing the mathematical expression in this way corresponds to reasoning thus: The first friend has five seats from which to choose, the next friend has four (since one is occupied), the next friend has three and the penultimate friend has two. The seat that the last friend to arrive will occupy is now determined by the other choices – it is whichever seat is left. Both arguments are valid and (therefore, as one would hope!) both answers are the same, i.e. 120 = 5 x 24 = 5 x 4 x 3 x 2.

For six people and six friends we have 720 = 6 x 120 = 6 x 5 x 4 x 3 x 2 ways.

Permutation

Rather than continuing to think about three friends and three cinema seats, in this final section we are a bit more abstract. One of the main points of abstraction is to truly understand the range of circumstances to which all of the thinking we have done in the previous section is applicable. This section will hopefully also give some idea to non-mathematicians about some of the ways in which a mathematician might encode the thinking of the previous sections.

We have already generalised to more friends and more seats. If you are not afraid of algebra you will probably see that for n friends and n seats there are n x (n-1) x (n-2) x … x 3 x 2 ways (the standard notation for this expression is n!).

So, finally, suppose we have n objects which can be put into some order. This abstract situation is genuinely extracting the salient points about the friends and seats example: There are n friends and their possible orderings are the possible ways in which they can sit down in n consecutive cinema seats. In how many ways can n objects be ordered? The answer is n!. Or, equivalently given n objects already in some order, in how many different ways can they be rearranged or permuted? If we include the permutation in which you do not do any rearranging, then the answer is again n!.


Advertisements