Puzzles about partitions

Harry Hibberd

7 February 2019

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

I’ve spent some time working with partitions – puzzling over them, trying to figure out some things
about them, and making a few art objects which I’ve delighted in hanging on my walls. I’m half hoping that somewhere in the maths world there may be others interested in developing knowledge about them. And I wonder whether something seriously useful might come out of it!

So welcome to partition world!

And a good place to start is a little party trick.

Take ten playing cards, and divide this pack into any number of smaller packs, with any number of

Playing cards. Wikimedia Commons, CC BY-SA 3.0.

cards in each. Put the packs in order of size, largest on the left. Now take one card from each pack and make another pack. Arrange all the packs in order of size, largest on the left. Now repeat the process again, and then again. After each re-formation, think whether that particular set of numbers has occurred before. After repeating this, think what would you expect to happen eventually? Would you expect the process to go on forever, or would you expect to reach some final state which cannot be altered? If so what is it?

What would you expect to happen if you tried a different starting position? What if you try a
different number to start with, say eleven?

When you first try this with the familiar number 10, the answer is rather surprising! Try it!

This is a trick based on the Partitions of Ten ie all the ways in which the number 10 can be divided
into a number of sub-parts. We can use the term $P(n)$ to mean the number of partitions of $n$, that is, the number of different ways that a positive integral number $n$ can be divided into positive integral parts. Thus, for example, the partitions of 5 are, listed in reverse numeric order: 5; 4, 1; 3, 2; 3, 1, 1; 2, 2, 1; 2, 1, 1, 1; 1, 1, 1, 1, 1 ie 7 partitions in all. Listing in this “reverse numeric” order is an easy way to list all the possible partitions of any number.

This table gives the first 12 values of $P(n)$, and gives a feel for the rate at which $P(n)$ increases:

After this, $P(n)$ starts to increase very rapidly, for example $P(100)$ is 190,569,292!

To me the subject of partitions seems to parallel the subject of the factorisation of numbers but using the “+” sign instead of the “x”. Reverse numeric listing is one way to count to $P(n)$. Are there any other ways to count them?

A question about the above trick is – is it a fluke with the number ten that, whatever partition you
first choose, performing the trick always ends up at the partition 4, 3, 2, 1? The answer is probably
“no”, but why does it happen and what happens if you choose a number other than ten?

“Down-tree”: towards the root. Flickr, CC BY 2.0.

Let’s start by examining what the trick does. You can use a pack of ten cards to aid visualisation. Take any partition (grouping) as an example, say 4, 3, 1, 1, 1, and represent this by five small packs of cards of 4, 3, 1, 1, 1 respectively. Now take 1 from each pack, leaving only a 3-pack and a 2-pack, and in hand a pack of 5 cards which we place beside the above packs and get the grouping (partition) 5, 3, 2. Repeating this move gets us to 4, 3, 2, 1. But now doing the move on this partition reiterates to itself and forms the basis of the above trick. We might, therefore, regard this as the “root” of the process, and we might call this process going “down-tree” towards the root.

“Up-tree”. Flickr, Public Domain

We can see that the partition “above” our start point would also do the same thing. What partition is this? Well, if we reverse the process from our start at 4, 3, 1, 1, 1, we get the partition “above” it by taking the 4-pack and dealing it out to the four remaining packs to get 4, 2, 2, 2. So we have gone away from the root and appear to be climbing up a tree. We might call this reverse process going “up-tree”.

Sure enough, doing the same again and dealing out the 4-pack gets us to 3, 3, 3, 1, and doing it again (with any one of the 3-packs) gets us upwards to 4, 4, 2. But at this point, we have a choice because two different packs will both get us further upwards – if we take a 4-pack we will get 5, 3, 1, 1, whereas if we take the 2-pack we will get 5, 5. Taking this latter one we get upwards to 6, 1, 1, 1, 1. Doing it again with the 6-pack we will get to 2, 2, 2, 2, 1, 1, and then we can’t go any further because we don’t have a pack large enough to be able to deal one card to each of the remaining packs, and we are at an “end”.

Figure 1.

We can see that we have a unique “tree” of partitions opening up above the root and we can go either “up-tree” until we get to an end point as above or we go “down-tree” and get back to the root. Going up the tree of 10, if we take the right branch wherever there is a choice of two or more different sub packs gets us to all 42 of the different partitions of this number. Vice versa, going down-tree from any partition always gets us to the root. Figure 1 shows a plot of all these 42 partitions formed into a tree. Note that to save space in Figure 1 (and Figure 2) the partitions are written using superscript notation eg $42^3$ means 4, 2, 2, 2 and so on.

To repeat for the sake of clarity, with the packs forming any partition, to go down-tree, take one card from each pack to make a new pack, and put the packs in order of size: to go up-tree, take any pack which is at least equal to the number of remaining packs, deal one card out to each pack and deal any remainder out to make additional packs of one.

Now we have an answer to the question – what is special about the number ten? Of course it is the fact that it is a “triangular” number, namely 1+2+3+4, ie a number of the form:

$$ T(n) = \frac{1}{ 2} \, \times \, n \, \times \, (n+1). $$

Intuitively, any number like this will always form a tree of partitions which ends up at its root triangle and forms a root end. At this root, performing either the up-tree move or the down-tree move will reiterate to itself. So any number of the triangular series 1, 3, 6, 10, 15 and so on, will form a “tree” set, and the basic “trick “of getting to a single end point, or root, will work for any pack with one of these numbers. So if you had a normal playing deck of cards, and you started with 45 cards from it, you would automatically end up with the nine sub-packs of 9, 8, 7, 6, 5, 4, 3, 2, 1 whatever original set of sub-packs you chose from the 45-pack! But, as there over 89,000 partitions of 45, this may take you some time!

But now of course we have another fundamental question – what happens with non-triangular numbers? Well, let’s take another number as an example – what about eleven, the number just one greater than the triangular 10? How do we get to all of the 56 different partitions given in the table above?.

First let’s consider how the tree behaves in the neighbourhood of ten’s number triangle 4, 3, 2, 1 and consider the partition 5, 3, 2, 1. As described above, try going “down-tree” from here – take one from each pack to form a new pack, and put it together with the remaining reduced size packs. You will get 4, 4, 2, 1. Do it again and you will get 4, 3, 3, 1. Again, and you will get 4, 3, 2, 2. Again and you will get 4, 3, 2, 1, 1. Again and you will get 5, 3, 2, 1. You are back where you started after having gone round a small loop of 5 different partitions!

It might help to look at this in a slightly different way. Consider the eleven cards set out thus:

The extra card making up the eleven from the triangular ten appears to move down from left to right on the triangle line! Then it goes back to the top so a closed loop of 5 positions is formed.

Figure 2. Eleven

Now try going up-tree from the first arrangement 5, 3, 2, 1. If you take the 5-pack and deal it out to
the other 3 packs you get 4, 3, 2, 1, 1 which is in the loop. But you could also take the 3-pack and deal it out to get 6, 3, 2 and you are out of the loop, and starting to go up a tree again! In fact, this can happen with three different partitions in the root loop. It’s best to see this in a diagram (figure 2).

This is a coloured diagram of the tree of the partitions of eleven set out in a special way. Each of the leaf-like areas on the diagram represents a different partition and there are 56 such partitions in all. The central five leaves represent the root circle shown above. The two brown ones represent partitions from which movement is either up or down (4, 4, 2, 1 and 4, 3, 2, 1, 1), the three green ones represent partitions from which a movement out of the circle may be made. Thereafter, continuing uptree, only one movement may be made from the brown leaves, two different upward movements can be made from the green leaves, and three different upward movements from the purple leaves. The blue leaves all represent end points of the tree from which no upward movement may be made. Figure 1 is coloured in a similar manner.

So this is what happens with one non-triangular number. It is reasonable to assume that similar but larger partition trees will be made for all numbers of the form $T(n)+1$. Looking at the diagram above, one might suspect that all numbers of the form $T(n)-1$ will behave similarly also. A tree for nine, which is $T(4)-1$, tends to show this. But what of the trees for the infinity of numbers which are not of this form?

A small clue is given by the tree of eight, which is half way between 6, which is $T(3)$, and 10 which is $T(4)$ . Surprisingly the tree for eight actually has two root circles which are not connected to each other, and each of these gives rise to an independent tree which is not connected to the other one! The same is true for the tree of 12, and for the tree of 13, which both lie halfway between $T(4)$ which is 10, and $T(5)$ which is 15. But what about the great infinity of trees that grow above these heights?

Well, I hope that I’ve whetted your appetite to investigate other things about partitions. You could
start, for example, by investigating duals…!

Happy hunting!

Harry Hibberd

Cambridge graduate a long time ago, thereafter a professional engineer,
now a volunteer in a museum workshop. Harry dabbles in pictorial maths and
likes to make drawings and glass hangings to show them off. He also likes
films, especially those with train scenes in, and has a big collection on an
IMDb site. Visits family, children, grand-children, and dogs.

All articles by Harry