Football formulae: the maths behind the UEFA Champions League draw

Didier Drogba
The Round of 16 of the UEFA Champions League football tournament kicked off this week with Arsenal, Manchester United and Celtic representing the remaining British interest in the competition. While the games themselves are sure to produce a flurry of 'remarkable' statistics, it was the draw for this stage of the competition (which took place in December) that raised a number of statistical eyebrows. (Easily distinguishable from other types of eyebrow by their tendency to take on the shape of common probability distributions.)
While the prospect of Arsenal playing Bayern Munich and Manchester United playing Real Madrid grabbed most of the headlines, some keen-eyed observers noticed a peculiar coincidence: the official draw generated exactly the same set of fixtures as in the preceding day's rehearsal. Naturally, (almost) everyone wanted to know "what were the chances of that?".
There are around two million ways to split 16 teams into eight pairs, but things aren't quite this simple, as there are a few restrictions placed on which teams can (and can't) play each other:
  1. Those teams who qualified as group winners in the previous stage of the competition can only be drawn against teams who qualified as group runners-up
  2. Two teams who were in the same group in the previous round cannot play each other in the round of 16
  3. Two teams from the same football federation cannot play each other in the round of 16
With these conditions, the number of ways of pairing up the 16 teams drops to 5,463, which is rather a lot smaller than two million, but still a fairly large number. It's tempting to conclude from this that the probability of the real draw matching the rehearsal was 1 in 5,463, and while the true figure is fairly close to this, it turns out the real-world mechanics of the draw mean it's not quite so simple (a fact I was first alerted to by John Haigh of the University of Sussex, and we'll have more on this in a magazine article in Significance in the coming months). In any case, it can be viewed as a fairly remarkable coincidence: you'd have a better chance, for example, of tossing a coin 12 times and getting 12 heads.
Another interesting side-effect of these conditions is how they affect the chances of various teams being drawn against one another. For example, if you were an Arsenal fan worrying about the prospect of playing the mighty Barcelona in the last 16, you may think your chances were 'only' one in six: there are eight group winners to be drawn against, but Schalke (from the same group) and Manchester United (fromt he same country) aren't 'valid' opponents. In reality, the odds are a little over one in five (and a quick glance at how many valid opponents Barcelona has goes some way to explaining this). In a similar vein, one can't help but feel slightly sorry for AC Milan, whose pairing with Barcelona was somewhat predictable: they had a relatively massive one in four chance of drawing the Spanish giants.
Finally, some credit is due to UEFA for avoiding the potential for fiasco these rules create. A naively conducted draw could very easily break down, with a runner-up 'running out' of valid opponents (for example, if the last two teams to be drawn were both Spanish). Fortunately, there is a neat theorem that helps anticipate this situation arising, although its most common example lies in a rather different context: pairing up men and women to get married. While we're not certain, it seems likely that UEFA employed something to this effect to save the embarrassment of an aborted draw.
We'll have a more thorough look at this surprisingly complex problem in an article in the print magazine of Significance in the coming months, so watch this (or rather that) space.