41 Advanced counting
The branch of mathematics called combinatorics is sometimes known as advanced
counting. It is not about adding up a column of figures in your head. ‘How many?’ is a
question, but so is ‘how can objects be combined?’ Problems are often simply stated,
unaccompanied by the weighty superstructure of mathematical theory – you don’t have
to know a lot of preliminary work before you can roll up your sleeves. This makes
combinatorial problems attractive. But they should carry a health warning: addiction is
possible and they can certainly cause lack of sleep.
A tale from St Ives
Children can start combinatorics at a tender age. One traditional nursery
rhyme poses a combinatorial question:
As I was going to St Ives,
I met a man with seven wives;
Every wife had seven sacks,
Every sack had seven cats,
Every cat had seven kits.
Kits, cats, sacks and wives,
How many were going to St Ives?
The last line contains the trick question. An implicit assumption is that the
narrator is the only person on his way ‘to’ St Ives, so the answer is ‘one’. Some
people exclude the narrator and for them the answer would be ‘none’.
The charm of the poem lies in its ambiguity and the various questions it can
generate. We could ask: how many were coming from St Ives? Again
interpretation is important. Can we be sure the man with his seven wives were all
travelling away from St Ives? Were the wives accompanying the man when he
was met, or were they somewhere else? The first requirement of a combinatorial
problem is that assumptions be agreed beforehand.
We’ll assume the entourage was coming along the single road away from the
Cornish seaside town and that the ‘kits, cats, sacks and wives’ were all present.
How many were there coming from St Ives? The following table gives us a
solution.