Dear Uncle Colin,

In reading Sir Dermot Turing’s XY&Z, he states that the number of species of cycle is 101 - and after a bit of thought, I figured out that that’s the number of partitions of the number 13. However, I couldn’t work out how to get 101! Can you help?

Erroneous Numbers - I Get Massive Answers

Hi, ENIGMA, and thanks for your message!

A partition of a number is a way of making it by adding. Possible partitions of 13 include 6+7, 5+5+3, 1+1+2+3+6 and - it would appear - 98 others. We don’t care about ordering (so 6+7 is the same as 7+6).

In my experience, partitions are a bit of a pain to count. However, there is a ((or rather, at least one)) way to count them systematically, based on what I’ll call the Largest Number Principle.

The idea is to classify each partition according to the biggest number remaining, and recursively give all of the possibilities. Rather than 13, I’ll do it with 6 to start with.

Largest Number Principle: 6

Possible largest numbers for 6 are 6, 5, 4, 3, 2 and 1.

If the largest number is 6, we’re done. There’s only one possibility. [1]

If the largest number is 5, the only way we can make 6 is by adding 1; there is one possibility. [1]

If the largest number is 4, the next biggest number could be 2 or 1. If it’s 2, we’re done; if it’s 1, we must have 4+1+1, so there are two possibilities. [2]

If the largest number is 3, the next biggest number could be 3, 2 or 1. If it’s 3, we’re done; if it’s 2, it must be followed by 1; if it’s 1, there must be three of them. That makes three new partitions. [3].

If it’s 2, then the next biggest number could be 2 or 1. If we start 2+2, we could finish +2 or +1+1; if we start 2+1, we finish with three more 1s. There are three possibilities here. [3]

Lastly, if the biggest number is 1, we must have six ones, and there’s only one partition. [1].

Altogether, that’s 11 partitions.

Largest Number Principle: 13

There are some shortcuts we can take. If we know the number of partitions for some smaller numbers, we can use that information to save writing everything out.

We’ve just seen that $P(6) = 11$; it’s also the case that $P(5)=7$, $P(4) = 5$, $P(3) = 3$, $P(2) = 2$ and $P(1) = 1$.

There is also the useful Rule of 2s: if the largest number is 2 and your target is $k$, the number of partitions available to you is $\floor{\frac{k}{2}}$. (If you wrote, say, 9 as 2+2+2+2+1, the last 2 can be turned into two 1s to make a new partition; the last 2 in that can be split, and so on.)

So, using the largest number principle again:

13 is done [1]

12 must be followed by 1 [1]

11 leaves 2 over, and there are $P(2)=2$ options. [2]

10 leaves 3 over, and there are $P(3)=3$ options. [3]

9 leaves 4 over, and there are $P(4)=5$ options. [5]

8 leaves 5 over, and there are $P(5)=7$ options. [7]

7 leaves 6 over, and there are $P(6)=11$ options. [11]

6 is where it gets tricky: we can’t just write down $P(7)$ because a) we haven’t worked it out, and b), one of the partitions has a 7 in it, and that’s a violation of the LNP. Instead, we can work recursively:

  • 6+6 leaves 1 over, which must be followed by 1 [1]
  • 6+5 leaves 2 over, giving $P(2) = 2$ [2]
  • 6+4 leaves 3 over, giving $P(3) = 3$ [3]
  • 6+3 leaves 4 over, which we need to split further
  • 6+3+3 leaves 1 [1]
  • 6+3+2 leaves 2 [2]
  • 6+3+1 must be followed by three 1s [1]
  • 6+2: we’re in rule-of-two territory here, with a target of 7; this adds three partitions [3]
  • 6+1: is followed by six ones [1]

So 6 adds 14 partitions.

5 needs splitting, too.

  • 5+5 leaves 3, which gives $P(3)=3$ [3]
  • 5+4 leaves 4, which gives $P(4)=5$ [5]
  • 5+3 leaves 5, which splits further:
  • 5+3+3 leaves 2, giving 2 [2]
  • 5+3+2, using rule-of-two, gives 2 [2]
  • 5+3+1 gives 1 [1].
  • 5+2, using rule-of-two, gives 4 [4]
  • 5+1 gives 1 [1].

So 5 adds 18 partitions.

4, similarly:

  • 4+4+4 gives 1 [1]
  • 4+4+3 gives 2 [2]
  • 4+4+2 gives 2 [2]
  • 4+4+1 gives 1 [1]
  • 4+3+3 gives $P(3) = 3$ [3]
  • 4+3+2 gives 3 (by rule of 2) [3]
  • 4+3+1 gives 1 [1]
  • 4+2 gives 4 (by rule of 2) [4]
  • 4+1 gives 1 [1]

4 also adds 18 partitions.

If gets simpler with 3:

  • 3+3+3+3 gives 1 [1]
  • 3+3+3+2 gives 2 [2]
  • 3+3+3+1 gives 1 [1]
  • 3+3+2 gives 3 [3]
  • 3+3+1 gives 1 [1]
  • 3+2 gives 5 [5]
  • 3+1 gives 1 [1]

That’s 14 altogether.

2 is very simple: using rule of 2, it’s six. [6].

And of course, there’s only one way with 1 as the biggest number. [1]

Adding all of those up gives 101.

I suspect that can be made simpler by developing rules of 3 and 4, but I don’t have the inclination right now. I shall leave that as an exercise!

Hope that helps,

- Uncle Colin