This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/IntegerPartitionTrees

From OeisWiki

Jump to: navigation, search

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.

Contents

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
Image:IntegerPartitionTree6.png
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 listA080576"Maple"
VLR,  decreasing parts, reverse listA080577 "Mathematica"
VLR*, increasing parts, reverse listA036036"A. & St."
VRL,  decreasing parts, forward listA182937"Peter's"

Prime encoded partitions

There is a simple way to make integer partitions more compact. Given an integer partition [e1, e2,...,ek] we can associate the product p1^e1*p2^e2*...*ek^pk where pi 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:YoungLattice.jpg

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:
Personal tools