This site is supported by donations to The OEIS Foundation.

# User:Peter Luschny/IntegerPartitionTrees

BREAKING NEWS, Jan 20 2011, Ken Ono:

"We prove that partition numbers are ‘fractal’ for every prime.
These numbers, in a way we make precise, are self-similar in a
shocking way." [1]

## Contents

Integer Partition Trees

Peter Luschny — Jan 20 2011

**KEYWORDS:**
integer partition, partition tree, prime encoded partition,
Young's lattice, Fenner-Loizou tree, fractal order, self-similarity.

**Concerned with sequences: ** A000041, A036035, A036036, A053445, A063008,
A080576, A080577, A182937, A182911.

## How to put integer partitions in a linear order?

We suggest to choose as a starting point a partial ordering
of the integer partitions which reflects the inner structure
of the set of all integer partitions and which can be easily generated
and pleasantly displayed. In other words, to start with a binary tree
of the set of integer partitions of n. These trees will
represent our *canonical partial order of integer partitions*.
Relative to these trees we derive different linear orders of the set of integer partitions.
We will look only at some of the most interesting cases.

To the right edge of the tree we will refer to as the trunk of the tree. These binary trees of
integer partitions of n can be generated in a natural way.
D. E. Knuth writes: "All partitions of *n* into *m* parts appear on
level *n - m* in lexicographic order." (TAOCP 4, fasc. 3, 7.2.1.4, exercise 10.)
One can add: "All partitions of n with largest part k appear on the left subtree
of 'k11..1', (n-k times 1)." Knuth gives reference to a more general tree-generating
algorithm by T. I. Fenner and G. Loizou, Comp. J. 23 (1980), 332-337.

### Linear orderings derived from the tree

The first linear orderings are now defined by reading the levels from top to bottom and from left to right (western style) or from top to bottom and from right to left (eastern style). For example the partitions of 6 are then ordered as shown in the table below.

[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [2, 2, 1, 1], [3, 1, 1, 1], [2, 2, 2], [3, 2, 1], [4, 1, 1], [3, 3], [4, 2], [5, 1], [6] |
[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [3, 1, 1, 1], [2, 2, 1, 1], [4, 1, 1], [3, 2, 1], [2, 2, 2], [5, 1], [4, 2], [3, 3], [6] |

Another simple operation is to replace each partition in the tree by it's conjugate partition. The western and eastern style variant then become respectively

[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1] |
[6], [5, 1], [4, 1, 1], [4, 2], [3, 1, 1, 1], [3, 2, 1], [3, 3], [2, 1, 1, 1, 1], [2, 2, 1, 1], [2, 2, 2], [1, 1, 1, 1, 1, 1] |

More generally, let us define a linear ordering by associating a traverse to the tree. We define it recursively. The start is always at the root of the tree. Now assume that you have already reached a node of the tree. Now you can do three things: Continue the travel through the tree by visiting the left child (L), or by visiting the right child (R) or by inspecting the data associated with the node (V). Thus we have six different ways to define a traverse: VLR, VRL, LVR, RVL, LRV and RLV.

We will look only at three cases:

VLR | RVL | VRL |

[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [2, 2, 1, 1], [2, 2, 2], [3, 1, 1, 1], [3, 2, 1], [3, 3], [4, 1, 1], [4, 2], [5, 1], [6] |
[1, 1, 1, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [4, 2], [4, 1, 1], [5, 1], [6] |
[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [3, 1, 1, 1], [4, 1, 1], [5, 1], [6], [4, 2], [3, 2, 1], [3, 3], [2, 2, 1, 1], [2, 2, 2] |

All three of these linear orderings have descriptive interpretations in view of the tree. In the case VLR a caterpillar traverses the periphery of the tree starting at the left hand side of the root and records a node whenever he passes the node's left edge. Similarly in the case VRL a caterpillar traverses the periphery of the tree starting at the right hand side of the root and records a node whenever he passes the node's right edge. In the case RVL the caterpillar starts at a leaf and climbs up to the trunk of the tree. Having reached the trunk it jumps down to the next leaf and climbs up again...

In more conventional terms VLR is the preorder traversal of the entire tree and gives the lexicographic order of the integer partitions. As a personal aside, the VRL is the method I use when I list integer partitions with paper and pencil for small n. The first half is extremely simple and the second half is not much harder especially when you can look at the already written first half. I leave it to the reader to work out the details of algorithm. Interestingly I never saw this method discussed in the literature in spite of the fact that it is a natural 'dual' of the lexicographic order of the integer partitions.

For the sake of completeness we record also the 'co-variants', the orderings after substitution of a partition by it's conjugate.

VLR* | RVL* | VRL* |

[6], [5, 1], [4, 2], [3, 3], [4, 1, 1], [3, 2, 1], [2, 2, 2], [3, 1, 1, 1], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1] |
[6], [3, 3], [4, 2], [5, 1], [2, 2, 2], [3, 2, 1], [4, 1, 1], [2, 2, 1, 1], [3, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1] |
[6], [5, 1], [4, 1, 1], [3, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [2, 2, 1, 1], [3, 2, 1], [2, 2, 2], [4, 2], [3, 3] |

### Popular orderings on OEIS

By definition the parts of a partition form a weak monotone sequence of positive integers. Additionally a convention on the type of monotony is added: nonincreasing or nondecreasing. This fixes a representative in the equivalence class. Thus [3, 2, 1] and [1, 2, 3] should not be regarded as different, but as equivalent and by current standards [3, 2, 1] represents the integer partition.

As each linear (or total) ordering has a dual ordering each linear ordering of IPs also has a dual ordering, the dual of which is the ordering we started from. Will the real ordering please stand up? Again we fix by convention which of the two orderings is the 'forward' one and which is the 'reverse' one. In the 'forward' ordering [1,1,...,1] (n-times 1) precedes [n].

In parenthesis let us look here at the fine-print: We do **not** define an operator rev(.)
(reverse list) and describe a transformation. We define an *attribute* of the
ordering. This has the advantage that we do not have to refer to something already
defined by other means. Observe how much simpler this is than to say (taken from a
comment on OEIS) "the integers are in reverse order of the partitions in
A-St-order." They are in reverse order because [1,1,..,1]
precedes [n], whatever A-St-order means. Parenthesis closed.

Thus a way to characterize orderings of IPs is to give a triple [traverse, increase/decrease, forward/reverse]. There is no mathematical content whatsoever associated with this classification; it is only a way to disambiguate constructs found in real life and in particular on OEIS.

In the database of OEIS one frequently find the names 'Abramowitz and Stegun ordering' (or 'A-St ordering'), 'Maple ordering' and 'Mathematica ordering'.

Mathematica results from 'IntegerPartitions' are given in as VLR, with decreasing parts and as a reverse list. The 'Abramowitz and Stegun ordering' ("A. & St.") is the VLR* ordering with increasing parts. The 'Maple ordering' has also increasing parts and the results are given as a forward list.

VLR, increasing parts, forward list | A080576 | "Maple" |

VLR, decreasing parts, reverse list | A080577 | "Mathematica" |

VLR*, increasing parts, reverse list | A036036 | "A. & St." |

VRL, decreasing parts, forward list | A182937 | "Peter's" |

### Prime encoded partitions

There is a simple way to make integer partitions more compact.
Given an integer partition [e_{1}, e_{2},...,e_{k}] we can associate
the product p_{1}^e_{1}*p_{2}^e_{2}*...*e_{k}^p_{k}
where p_{i} is the i-th prime. The point is that we can reconstruct the partition from the integer by the
fundamental theorem of arithmetic.

VLR , p < q, [1..1] < [n] | A000000 | "Maple" | 1,2,6,4,30,12,8,210,60,36,.. |

VLR , p > q, [1..1] > [n] | A063008 | "Mathematica" | 1,2,4,6,8,12,30,16,24,36,.. |

VLR*, p < q, [1..1] > [n] | A036035 | "A. & St." | 1,2,4,6,8,12,30,16,24,36,.. |

VRL , p > q, [1..1] < [n] | A000000 | "Peter's" | 1,2,6,4,30,12,8,210,60,24,.. |

In this table the term 'increasing parts' is replaced by the symbolic expression 'p < q' and 'forward list' by the symbolic expression '[1..1] < [n]'. Perhaps this is the most succinct way to express the sometimes confusing interplay of the relations involved; in any case less awing than something like "graded reverse reflected colexicographic order of exponents" yet more informative than something profane like "A. & St." order or Peter's order. Moreover, I have not yet found out what the scholarly names of [VLR, p>q, [1..1]<[n]] or [VRL, p<q, [1..1]<[n]] or [VRL*, p>q, [1..1]<[n]] etc. are.

with(combinat): PrimeEncodedPartitions := proc(n, typ) local e, w, r, c, P; c := e -> conjpart(e); r := proc(L) local B,i; B := NULL; for i from nops(L) by -1 to 1 do B := B,L[i] od; [%] end: w := proc(e) local i, m, p, P; m := infinity; P := permute([seq(ithprime(i), i=1..nops(e))]); for p in P do m := min(m,mul(p[i]^e[i], i=1..nops(e))) od end: P := partition(n); if typ = "Maple" then [seq(w(e),e=P)] elif typ = "Mathematica" then [seq(w(e),e=r(P))] elif typ = "A-ST" then [seq(w(c(e)),e=P)] fi end: # example calls seq(print(PrimeEncodedPartitions(i,"A-ST")),i=0..6); seq(print(PrimeEncodedPartitions(i,"Maple")),i=0..6); seq(print(PrimeEncodedPartitions(i,"Mathematica")),i=0..6);

### Bringing VRL to OEIS

Triangle in which n-th row lists all integer partitions of n, in order of traversing the periphery of the Fenner-Loizou tree in the clockwise sense. 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 4, 1, 5, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 1, 1, 5, 1, 6, 4, 2, 3, 2, 1, 3, 3, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1 OFFSET 1 COMMENTS If the Fenner-Loizou tree is traversed in the counterclockwise sense (preorder traversal) the integer partitions are in lexicographic order. REFERENCES T. I. Fenner and G. Loizou, Comp. J. 23 (1980), 332-337. D. E. Knuth, TAOCP 4 (2005), fasc. 3, 7.2.1.4, exercise 10. EXAMPLE First five rows are: [[1]] [[1, 1], [2]] [[1, 1, 1], [2, 1], [3]] [[1, 1, 1, 1], [2, 1, 1], [3, 1], [4], [2, 2]] [[1, 1, 1, 1, 1],[2, 1, 1, 1],[3, 1, 1],[4, 1],[5],[3,2],[2,2,1]]

### Summary of part I

We have given a framework for linear orderings of integer partitions by interpreting them as special ways of 'flattening' the partial order of the IPs represented by a canonical binary tree. We consider such a representation extremely useful in applications of partitions (see references below).

### The Fenner-Loizou tree

To give a precise definition of the notion *integer partition tree*
I have implemented the algorithm of T. I. Fenner and G. Loizou
with Maple and Sage. Applications of our setup were given to the generalized Stirling triangles of the
first kind and of the
second kind and can be found on my page
Counting With Partitions.

# The partition-product and combinatorial triangles. # Author: Peter Luschny, written 2009-02-02, Maple V R5 restart; readlib(queue): pow := proc(n,k) if n=0 and k=0 then 1 else n^k fi end: GeneratePartitions := proc(n, visit) local a,b,nextLeft,nextRight,count,normalize, partitions,putPart,nextPart,least,length,next; putPart := (x) -> queue[enqueue](partitions, x); nextPart := () -> queue[dequeue](partitions); least := a -> op(2,a); length := a -> op(3,a); normalize := proc(a) local s,t,i; t:=[]; s:=op(1,a); for i from 1 to length(a) do t := [op(t),s[i]] od; t end; next := proc(b) count := count+1; visit(normalize(b)); if least(b) <= length(b) then putPart(b) fi; end; nextLeft := proc() local u,la; la := least(a); if (la = length(a)) or (a[1][la]>1) then RETURN(NULL) fi; u:=normalize(a); u[la]:=u[la]+1; [u,la+1,length(a)-1] end; nextRight := proc() local u,la; la := least(a); if (la = 1) or ((la <> 2) and (a[1][la-1] = a[1][la-2])) then RETURN(NULL) fi; u := normalize(a); u[la-1] := u[la-1]+1; [u,la,length(a)-1]; end; partitions := queue[new](); count := 0; next([[seq(1,i=1..n)],1,n]); while not queue[empty](partitions) do a := nextPart(); b := nextLeft(); if b <> NULL then next(b); fi; b := nextRight(); if b <> NULL then next(b); fi; od; count end: PrintPartitionTree := proc(n) local R,len,visit; visit := proc(L) local i; if nops(L) = len then R := [op(R), L] else len := len - 1; print(R); R := [L] fi; end; R := []; len := n; GeneratePartitions(n,visit); print(R); end: for i from 3 to 7 do print("--",i,"--"); PrintPartitionTree(i); od:

from collections import deque def GeneratePartitions(n, visit): count = 1 p = ([], 0, n) queue = deque() queue.append(p) visit(p) while len(queue) > 0 : (phead, pheadLen, pnum1s) = queue.popleft() if pnum1s <> 1 : head = phead[:pheadLen] + [2] q = (head, pheadLen + 1, pnum1s - 2) if 1 <= q[2] : queue.append(q) count += 1 visit(q) if pheadLen == 1 or (pheadLen > 1 and \ (phead[pheadLen - 1] <> phead[pheadLen - 2])) : head = phead[:pheadLen] head[pheadLen - 1] += 1 q = (head, pheadLen, pnum1s - 1) if 1 <= q[2] : queue.append(q) count += 1 visit(q) return count def visit(q): print q[0] + [1 for i in range(q[2])] GeneratePartitions(6, visit)

## Is there a fractal order on the set of all integer partitions?

In the first part we focused on structures like a tree or a total order associated with partitions of n. Now we will look at integer partitions for all n simultaneously.

### Partition tree and Young's lattice

The classical way to organize the partition for all n in one structure is Alfred Young's lattice. Below is the Hasse diagram of this lattice.

Image by Prof. Richard Stanley. MIT Open Courseware, (CC) BY-NC-SA 3.0

If the partition tree for n is traversed in preorder it becomes the n-th level of the latice. Thus the partial order of the partitions implied by the structure of the tree is consistent with the refinement order induced from the lattice of partitions of an n-element set.

### An alternative way to build a table of all partitions.

The rules for building the table below are: go down the column by increasing the first part by 1; go down diagonal to the next row by appending the part 1. These are the recursive building rules. For starting we supply a sequence of partitions which are the top vertices of the triangles in the table below, 1,22,33,... Thus the triangles can be thought as expanding to infinity on two sides, downwards by appending further rows but also rightwards at the border to the next triangle.

Looking at the triangles we see that the notion of *self-similarity* certainly applies.

2 | 36 | 216 | 900 | 1296 | 5400 | 44100 | 27000 | 7776 | 32400 | 264600 | 5336100 | ||||||||||||||||||||||||||||||

1 | 22 | 33 | 222 | 44 | 332 | 2222 | 333 | 55 | 442 | 3322 | 22222 | ||||||||||||||||||||||||||||||

1 | |||||||||||||||||||||||||||||||||||||||||

2 | 11 | ||||||||||||||||||||||||||||||||||||||||

3 | 21 | 111 | |||||||||||||||||||||||||||||||||||||||

4 | 31 | 211 | 1111 | 22 | |||||||||||||||||||||||||||||||||||||

5 | 41 | 311 | 2111 | 11111 | 32 | 221 | |||||||||||||||||||||||||||||||||||

6 | 51 | 411 | 3111 | 21111 | 111111 | 42 | 321 | 2211 | 33 | 222 | |||||||||||||||||||||||||||||||

7 | 61 | 511 | 4111 | 31111 | 211111 | 1111111 | 52 | 421 | 3211 | 22111 | 43 | 331 | 322 | 2221 | |||||||||||||||||||||||||||

8 | 71 | 611 | 5111 | 41111 | 311111 | 2111111 | 11111111 | 62 | 521 | 4211 | 32111 | 221111 | 53 | 431 | 3311 | 422 | 3221 | 22211 | 44 | 332 | 2222 | ||||||||||||||||||||

9 | 81 | 711 | 6111 | 51111 | 411111 | 3111111 | 21111111 | 11111111 | 72 | 621 | 5211 | 42111 | 321111 | 2211111 | 63 | 531 | 4311 | 33111 | 522 | 4221 | 32211 | 222111 | 54 | 441 | 432 | 3321 | 3222 | 22221 | 333 | ||||||||||||

10 | 91 | 811 | 7111 | 61111 | 511111 | 4111111 | 31111111 | 21111111 | 1111111111 | 82 | 721 | 6211 | 52111 | 421111 | 3211111 | 22111111 | 73 | 631 | 5311 | 43111 | 331111 | 622 | 5221 | 42211 | 322111 | 2221111 | 64 | 541 | 4411 | 532 | 4321 | 33211 | 4222 | 32221 | 222211 | 433 | 3331 | 55 | 442 | 3322 | 22222 |

### Generic partitions

Now let us look closer at the sequence of the 'generic' vertices at the top of the triangles. For a given n there can be more than one such generic vertex or even none (as in the cases n=5 and n=7). The table below lists these vertices depending on n.

n | card(n) | Generic vertices of new triangles introduced at level n. | encoded as |

0 | 0 | { } | 1 |

1 | 1 | [1] | 2 |

2 | 0 | { } | 1 |

3 | 0 | { } | 1 |

4 | 1 | [22] | 36 |

5 | 0 | { } | 1 |

6 | 2 | [33] [222] | 216,900 |

7 | 0 | { } | 1 |

8 | 3 | [44] [332] [2222] | ... |

9 | 1 | [333] | ... |

10 | 4 | [55] [442] [3322] [22222] | ... |

11 | 2 | [443] [3332] | ... |

12 | 7 | [66] [552] [444] [4422] [3333] [33222] [222222] | ... |

13 | 3 | [553] [4432] [33322] | ... |

14 | 10 | [77] [662] [554] [5522] [4442] [4433] [44222] [33332] [332222] [2222222] | ... |

15 | 7 | [663] [555] [5532] [4443] [44322] [33333] [333222] | ... |

The table can be easily generated by the following Maple code:

NewVertices := proc(n) local Q, p; Q := {}; if n = 0 then RETURN([]) fi; if n = 1 then RETURN([[1]]) fi; # we assume the 'p>q' order here # which is not Maple's build-in order for p in IntegerPartitions(n-1) do Q := Q union {[op(p),1]}; p[1] := p[1] + 1; Q := Q union {p}; od; [op(IntegerPartitions(n) minus Q)]; sort(%,(s,t)->IPsort(s,t)) end:

Thus if we apply prime encoding to the sequence of generic integer partitions

[[],[1],[],[],[2,2],[],[3,3],[2,2,2],[],[4,4],[3,3,2], [2,2,2,2],[3,3,3],[5,5],[4,4,2],[3,3,2,2],[2,2,2,2,2], [4,4,3],[3,3,3,2],[6,6],[5,5,2],[4,4,4],[4,4,2,2], [3,3,3,3],[3,3,2,2,2],[2,2,2,2,2,2],[5,5,3],[4,4,3,2], [3,3,3,2,2],[7,7],[6,6,2],[5,5,4],[5,5,2,2],[4,4,4,2], [4,4,3,3],[4,4,2,2,2],[3,3,3,3,2],[3,3,2,2,2,2], [2,2,2,2,2,2,2],[6,6,3],[5,5,5],[5,5,3,2],[4,4,4,3], [4,4,3,2,2],[3,3,3,3,3],[3,3,3,2,2,2]];

we get sequence A182911, seemingly connected with the sequence A046056, which gives the smallest order for which there are n nonisomorphic finite Abelian groups.

1, 2, 1, 1, 36, 1, 216, 900, 1, 1296, 5400, 44100, 27000, 7776, 32400, 264600, 5336100, 162000, 1323000, 46656, 194400, 810000, 1587600, 9261000, 32016600, 901800900, 972000, 7938000, 160083000, 279936, 1166400, 4860000, 9525600, 39690000, 55566000, 192099600, 1120581000, 5410805400, 260620460100, 5832000, 24300000, 47628000, 277830000, 960498000, 12326391000, 27054027000.

Looking for a while at the *grande table de partitions principales*
I remembered that Ken Ono said: "self-similar in a shocking way".
But I did not feel that this table was shocking. Then I looked again at the *petite table des partitions
génératrices*.

22 | |||||

33 | 222 | ||||

44 | 332 | 2222 | |||

55 | 442 | 3322 | 22222 | ||

66 | 552 | 4422 | 33222 | 222222 | |

77 | 662 | 5522 | 44222 | 332222 | 2222222 |

### The number of generic integer partitions of n

The history file of A053445 shows that the original author Alford Arnold defined the sequence starting at 1 with the values

1, 0, 0, 1, 0, 2, 0, 3, .. (offset 1)

I believe this is the right way to define this sequence; if one really wants to add n = 0 then 0 should be added as value.

0, 1, 0, 0, 1, 0, 2, 0, 3, .. (offset 0).

Unfortunately the current A053445 does not reflect this. Taken things in our (and as I believe Arnold's) sense we can state:

A053445(n) are the numbers of generic partitions of n. |

Relative to our definition we can calculate A053445 with a nice algorithm by Alois Heinz (personal communication, see also A182911).

A053445 := proc(n) local b, ll; b := proc(n,i,l) local nl; if n<0 then elif n=0 then nl := nops(l); if nl=0 or nl=1 and l[1]=1 or nl>1 and l[-1]<>1 and l[1]=l[2] then ll := ll,l fi elif i>0 then b(n-i,i,[l[],i]), b(n,i-1,l) fi end; ll := NULL; b(n,n,[]); `if` (n=0,0,nops([ll])) end: