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]

---

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.

Partition tree of 6

Partition tree of 7

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₁, e₂,...,e_k] we can associate the product p₁^e₁*p₂^e₂*...*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. For n > 2 these numbers can be computed as the second  backwards difference of A000041, in other words, for n > 2 A053445(n) = A000041(n) - 2 A000041(n-1) + A000041(n-2).

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: