If you look up combinatorics on Wikipedia, it’s described as ‘a branch of mathematics primarily concerned with counting’. You might be forgiven for thinking, if you have studied maths at school level but not encountered much university-level maths, that all mathematics is primarily concerned with counting, since it’s all about numbers.
Of course, once you reach higher levels of study, mathematics is revealed to be a rich, varied subject with great subtlety. Combinatorics is counting, but a bit harder.
One example of a problem in combinatorics is one we’ve already seen – in my post last November, on permutations.
Puzzle: if ten people are attending a party and want to stand in line for a photo, how many different orders could they stand in?
If you’d like to take a minute now to think about this, and carry on reading once you have an answer, you should do so now. The problem more generally can be stated as, if we have N objects, and want to put them in order in a line, how do we count the number of different ways we could do this?
Having once asked an audience to think about the number of different ways to shuffle a pack of cards, and being told there a several – a riffle shuffle, an overhand shuffle, a faro shuffle, the Mexican spiral shuffle, and so on, I’m always careful in how I word the question. But hopefully you understand that I mean, ‘How many different orderings could I place the objects in?’.
The answer, as disclosed in the previous blog post, can be found by thinking about how many options I have for each of the items in order – when choosing which item to put first, I have N choices from my N objects; then once I’ve chosen which one goes first, I have N-1 choices for the second, and then N-2 choices for the third, and so on. So the total number of possibilities is N × (N-1) × (N-2) × … × 1, also known as ‘N factorial’ and written N!. For 10 people, 10! = 3,628,800.
This can be applied in any situation where objects can be placed in different orders – but it also comes in to other problems, as we will see.
Puzzle: if the same ten people are at a party and everyone wishes to shake hands with everyone else in the room, how many handshakes will take place?
Again, take a moment to convince yourself of an answer to this. The question we’re asking here is, how many pairs of people are there in a room of 10 people (or, generally, how many pairs of objects are there in a set of N objects)?
One way to think about this is to realise that each of the 10 people in the room will shake hands with each of the other people in the room – which is 9 people. So, you might think the number of handshakes would be 10 × 9 = 90. But this is too many.
In fact, we’ve counted every handshake twice – once from each of the two people involved. So we can divide this number by 2 and get 45, which is the number of handshakes. In general, for N people, we’d have (N×(N-1))/2 handshakes.
Another way to approach it is to imagine that at the party, everyone is shaking hands immediately having stood in line for the photo. It doesn’t matter what order they’re in, but whoever’s at one end of the line could walk along the line and shake hands with the other 9, then go and sit down. Then the next person, who’s already shaken hands with the one person who’s sitting down, merely has to shake hands with the remaining 8 people in the line; then 7, then 6 and so on. So our total will be 9 + 8 + 7 + 6 + … + 1 = 45.
The fact that the number of pairs in N things matches with the sum of all the numbers up to N-1 is true in general, and a useful coincidence. There’s a story (possibly slightly exaggerated) about the young mathematician Gauss, who was annoying a teacher by being too good at mathematics and interrupting the class with clever ideas. The teacher angrily set Gauss the task of adding up all the numbers from 1 to 100, to see if that would give them some respite – but Gauss worked out the general formula, and realised that it was simply (101×100)/2 = 5,050 and answered immediately. Grr!
Puzzle: Now imagine the 10 people at a party would like to go home, and a taxi arrives with space for exactly four people. How many different sets of four people could be chosen to get in the taxi?
This problem is slightly more complicated than the previous examples – and in some ways combines both of them. Like our ordering problem, we can still approach it by thinking about how many options we have at each stage; with 10 people, we could choose from 10 to put in the first seat, then pick one from the remaining 9 to go in the second seat, then 8, then 7; so for the four seats, we’d have 10 × 9 × 8 × 7 = 5,040 ways to choose four people.
This isn’t strictly a factorial – it does count down and multiply the numbers together, but it stops before going all the way down to 1. However, this is a product of things multiplied together, so it can be thought of 10! ÷ 6!. If you were to write both factorials out in full in a fraction, with 10! on top and 6! below, you could see that the last 6 terms would cancel top and bottom, leaving behind the result we want.
So, to choose 4 (= 10 – 6) people from 10, we could calculate 10!/(10-4)!, or in general, to choose K people from N, N!/(N-K)!. But if this doesn’t match up with your answer, because you carefully wrote out and counted all the possibilities, that’s because we’ve missed one thing.
If we were to choose four people (say, A, B, C and D) to go in the taxi, this would be because person A was picked first from the full set of 10, then B picked from the set of 9, and so on. However, if by chance we had picked B from the full set of 10, then A from the set of 9, we’d have B, A, C and D going in the taxi – which is exactly the same outcome as A, B, C and D.
In this case, given the four people are getting in a taxi and it doesn’t matter what order they’re in, different orderings of the same set count as the same outcome. Luckily, we already have a way to deal with this! If we have four people, there are 4! = 24 ways to order the set, so we could divide our total by this, to find the number of unique sets to choose. Now our formula is 10!/(4! ×(10-4)!) (here, the 4! goes on the bottom of the fraction), giving the answer 5040/24 = 210.
The general formula is then N!/(K!(N-K)!). While this does look like an attempt to write down the noise a goose makes, it’s a very useful and important formula in mathematics – the function is sometimes called the Choose function, and called ‘N Choose K’ – the number of ways to have N things, and choose K of them.
It’s sometimes also called the Binomial formula, as it crops up in the coefficients of binomial expansions like (a + b)n, and by association, the numbers in Pascal’s triangle (mentioned, and briefly explained, in my December post).
With these simple tools, mathematicians (specifically, combinatorics…-acists?) have the power to count and enumerate increasingly complicated sets of things.
How did you get on with the puzzles? And have you ever had combinatorial problems like these confront you in your day-to-day life? You might!