User:Peter Luschny/PermutationTrees

Permutation Trees

KEYWORDS: Permutation tree, rooted tree, classifications of permutation trees, Eulerian numbers, permutation, caterpillar notation.

Concerned with sequences: A008275, A008292, A179454, A179455, A179456, A179457.

Definitions

A permutation tree is a rooted tree that has vertex set {0,1,2,..,n} and root 0, and in which each child is larger than its parent and the children are in strict order from the left to the right. The power of a permutation tree is the number of descendants of the root. The height of a permutation tree is the number of descendants of the root on the longest chain starting at the root of the tree and ending at a leaf. The width of a permutation tree is the number of leafs.

The correspondence with the permutation is given by traversing the periphery of the tree starting at the right hand side of the root and recording a node whenever the node's right edge is passed.

For example below tree A has height 4 and width 1, the trees B, C, D all have height 3 and width 2, ..., and tree I has height 1 and width 4.

Example classifications

Permutations classified by height and by width of the associated rooted tree.

Trees are coded as parental lists.

Permutations and trees, n = 3.
By width (Eulerian) Trees Perm's # [ 0, 1, 2] 1 2 3 1 [ 0, 1, 1] [ 0, 1, 0] [ 0, 0, 2] [ 0, 0, 1] 1 3 2 3 1 2 2 3 1 2 1 3 4 [ 0, 0, 0] 3 2 1 1	By height Trees Perm's # [ 0, 0, 0] 3 2 1 1 [ 0, 0, 1] [ 0, 0, 2] [ 0, 1, 0] [ 0, 1, 1] 2 1 3 2 3 1 3 1 2 1 3 2 4 [ 0, 1, 2] 1 2 3 1

Permutations and trees, n = 4.

By width (Eulerian)   Trees Perm's # A [ 0, 1, 2, 3] 1 2 3 4 1 B C D G [ 0, 1, 2, 2] [ 0, 1, 2, 1] [ 0, 1, 2, 0] [ 0, 1, 1, 3] [ 0, 1, 1, 2] [ 0, 1, 0, 3] [ 0, 1, 0, 2] [ 0, 0, 2, 3] [ 0, 0, 2, 1] [ 0, 0, 1, 3] [ 0, 0, 1, 2] 1 2 4 3 1 3 2 4 4 1 2 3 1 3 4 2 1 4 2 3 3 4 1 2 3 1 2 4 2 3 4 1 2 3 1 4 2 1 3 4 2 4 1 3 11 E F H [ 0, 1, 1, 1] [ 0, 1, 1, 0] [ 0, 1, 0, 1] [ 0, 1, 0, 0] [ 0, 0, 2, 2] [ 0, 0, 2, 0] [ 0, 0, 1, 1] [ 0, 0, 1, 0] [ 0, 0, 0, 3] [ 0, 0, 0, 2] [ 0, 0, 0, 1] 1 4 3 2 4 1 3 2 3 1 4 2 4 3 1 2 2 4 3 1 4 2 3 1 2 1 4 3 4 2 1 3 3 4 2 1 3 2 4 1 3 2 1 4 11 I [ 0, 0, 0, 0] 4 3 2 1 1

By height   Trees Perm's # I [ 0, 0, 0, 0] 4 3 2 1 1 H G F E [ 0, 0, 0, 1] [ 0, 0, 0, 2] [ 0, 0, 0, 3] [ 0, 0, 1, 0] [ 0, 0, 1, 1] [ 0, 0, 1, 2] [ 0, 0, 2, 0] [ 0, 0, 2, 1] [ 0, 0, 2, 2] [ 0, 1, 0, 0] [ 0, 1, 0, 1] [ 0, 1, 0, 3] [ 0, 1, 1, 0] [ 0, 1, 1, 1] 3 2 1 4 3 2 4 1 3 4 2 1 4 2 1 3 2 1 4 3 2 4 1 3 4 2 3 1 2 3 1 4 2 4 3 1 4 3 1 2 3 1 4 2 3 4 1 2 4 1 3 2 1 4 3 2 14 D C B [ 0, 0, 1, 3] [ 0, 0, 2, 3] [ 0, 1, 0, 2] [ 0, 1, 1, 2] [ 0, 1, 1, 3] [ 0, 1, 2, 0] [ 0, 1, 2, 1] [ 0, 1, 2, 2] 2 1 3 4 2 3 4 1 3 1 2 4 1 4 2 3 1 3 4 2 4 1 2 3 1 3 2 4 1 2 4 3 8 A [ 0, 1, 2, 3] 1 2 3 4 1

 

Permutation trees with power 4

Counting permutation trees

A123125 Permutation trees of power n and width k (Eulerian numbers).

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	4	1
4	0	1	11	11	1
5	0	1	26	66	26	1
6	0	1	57	302	302	57	1
7	0	1	120	1191	2416	1191	120	1
8	0	1	247	4293	15619	15619	4293	247	1
9	0	1	502	14608	88234	156190	88234	14608	502	1

A special case: A008292(n,2) = A000295(n) for n > 1.

A179454 Permutation trees of power n and height k.

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	4	1
4	0	1	14	8	1
5	0	1	51	54	13	1
6	0	1	202	365	132	19	1
7	0	1	876	2582	1289	265	26	1
8	0	1	4139	19404	12859	3409	473	34	1
9	0	1	21146	155703	134001	43540	7666	779	43	1

Special cases: A179454(n,2) = BellNumber(n) - 1 = A058692(n) for n > 1;
A179454(n,n-1) = A034856(n) for n > 1.

A179455 Permutation trees of power n and height does not exceed k.

Partial row sums of A179454.

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	2
3	0	1	5	6
4	0	1	15	23	24
5	0	1	52	106	119	120
6	0	1	203	568	700	719	720
7	0	1	877	3459	4748	5013	5039	5040
8	0	1	4140	23544	36403	39812	40285	40319	40320
9	0	1	21147	176850	310851	354391	362057	362836	362879	362880

Special cases: A179455(n, 2) = BellNumber(n) = A000110(n) for n > 1;
A179455(n, n-1) = A033312(n) for n > 1.

A179456 Permutation trees of power n and height at most n − k.

Partial row sums of A179454 starting from the diagonal.

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	2	1
3	0	6	5	1
4	0	24	23	9	1
5	0	120	119	68	14	1
6	0	720	719	517	152	20	1
7	0	5040	5039	4163	1581	292	27	1
8	0	40320	40319	36180	16776	3917	508	35	1
9	0	362880	362879	341733	186030	52029	8489	823	44	1

A special case: A179456(n, n-1) = A000096(n).

A179457 Permutation trees of power n and width does not exceed k.

Partial row sums of A008292.

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	2
3	0	1	5	6
4	0	1	12	23	24
5	0	1	27	93	119	120
6	0	1	58	360	662	719	720
7	0	1	121	1312	3728	4919	5039	5040
8	0	1	248	4541	20160	35779	40072	40319	40320
9	0	1	503	15111	103345	259535	347769	362377	362879	362880

A special case: A179457(n, 2) = A000325(n) for n > 1 (Grassmannian permutations).

Three statistics on permutations

The Combinatorial Statistic Finder gives the definitions:
A combinatorial collection is a set ${\mathcal {S}}$ with interesting combinatorial properties.
A combinatorial map is a combinatorially interesting map $\phi :{\mathcal {S}}\longrightarrow {\mathcal {S'}}$ between combinatorial collections.
A combinatorial statistic is a combinatorially interesting map $\operatorname {st} :{\mathcal {S}}\longrightarrow \mathbb {Z}$.

The combinatorial collection we want to consider here are permutations ${\mathcal {P}}$ and we want to find a combinatorial statistic assigning a characteristic integer to every permutation. We assume that we already have a function ${\mathcal {H:}}\ {\mathcal {T}}\longrightarrow \mathbb {Z}$ which assignes to a rooted tree ${\mathcal {T}}$ its height and a function ${\mathcal {W:}}\ {\mathcal {T}}\longrightarrow \mathbb {Z}$ which assignes to a rooted tree ${\mathcal {T}}$ its width. Now we want to lift these characteristics to permutations.

The height-statistic of permutations

In the first case we want to find a statistic $st:{\mathcal {P}}\longrightarrow \mathbb {Z}$ and a map $\tau :{\mathcal {P}}\longrightarrow {\mathcal {T}}$ such that $\!st(p)=H(\tau (p))\!$ for all permutations p. This statistic and the map can be implemented in Sage/Python as:

def statistic(pi):
    if pi == []: return 0

    h, i, branch, next = 0, len(pi), [0], pi[0]

    while true:
        while next < branch[-1]:
            branch.pop()

        current = 0

        while next > current:
            i -= 1
            h = max(h, len(branch))
            if i == 0: return h
            branch.append(next)
            current, next = next, pi[i]

The distribution of the heights over the permutations now amounts to count the number of permutations with the same height.

def A179454_distribution(dim):
    for n in [0..dim]:
        L = [0]*(n+1)
        for p in Permutations(n):
            L[statistic(p)] += 1
        print L

A call A179454_distribution(9) generates the above table A179454. The statistic can be found on FindStat as the statistic St000308.

The width-statistic of permutations

The second case is the Eulerian case. Here we want to find a statistic $st:{\mathcal {P}}\longrightarrow \mathbb {Z}$ and a map $\tau :{\mathcal {P}}\longrightarrow {\mathcal {T}}$ such that $\!st(p)=W(\tau (p))\!$ for all permutations p. This statistic and the map can be implemented in Sage/Python as:

def statistic_eulerian(pi):
    if pi == []: return 0
    w, i, branch, next = 0, len(pi), [0], pi[0] 
    while true:
        while next < branch[-1]:
            branch.pop()
        current = 0
        w += 1 
        while next > current:
            i -= 1 
            if i == 0: return w
            branch.append(next)
            current, next = next, pi[i]

The distribution of widths over the permutations are counted by the Eulerian numbers. The function below computes a row in the Euler triangle.

def A123125_row(n):
    L = [0]*(n+1)
    for p in Permutations(n):
        L[statistic_eulerian(p)] += 1
    return L      
[A123125_row(n) for n in range(7)]     

The shape-statistic of permutations

The width-statistic and the height-statistic of permutations can be combined in a single statistic, the shape-statistic of permutations. It describes the shape of a permutation as the pair [width, height] of the associated permutation tree.

The small formal imprecision that a statistic is required to have the form $st:{\mathcal {P}}\longrightarrow \mathbb {Z}$ can be easily overcome: We define st_shape(p) = 2^width(p)*3^height(p). There is no ambiguity in this encoding by the uniqueness of the prime factorization. Granted, there is an arbitrariness in the choice of 2 and 3 (any other two different prime numbers would do equally well) and in the order of width and height, but for the purpose of our exposition this encoding is a convenient way to represent and count the various shapes of permutation trees.

For example in the case n = 3 we have the statistic

[1, 2, 3] => (2, 2) => 36
[1, 3, 2] => (1, 3) => 54
[2, 1, 3] => (2, 2) => 36
[2, 3, 1] => (2, 2) => 36
[3, 1, 2] => (3, 1) => 24
[3, 2, 1] => (2, 2) => 36

Thus the 6 permutations can have three shapes [24, 36, 54] which have shape counts [1, 4, 1] respectively. Thus the permutations of {1, 2, 3} distribute in shape as [(24, 1), (36, 4), (54, 1)].

The number of different shapes for n ≥ 0 are

A265602 = 1, 1, 2, 3, 5, 7, 11, 14, 20, 25, 32, ...

We consider the fact that this sequence was not yet in the OEIS as a strong indication that this classification of permutations might be new.

The corresponding different shapes are

[(0,0)], [(1,1)], [(2,1), (1,2)], [(3,1), (2,2), (1,3)], 
[(2,2), (4,1), (3,2), (2,3), (1,4)], ...

or in encoded form

A265603 = [1], [6], [12, 18], [24, 36, 54], [36, 48, 72, 108, 162], 
[72, 96, 108, 144, 216, 324, 486], ...

The corresponding number of permutations with these shapes are

A265604 = [1], [1], [1, 1], [1, 4, 1], [3, 1, 11, 8, 1], 
[25, 1, 13, 26, 41, 13, 1], ...

A more formal description of the shape-statistic of permutations are bivariate polynomials defined as the sum of the monomials x^w*y^h where (w, h) is the shape of p, summed over all n-permutations p.

For example in the case n = 4 we find

p(x,y) = x^4*y + 11*x^3*y^2 + 8*x^2*y^3 + x*y^4 + 3*x^2*y^2.

Looking at the coefficients of this polynomial we get the two lists

[0, y^4, 8*y^3 + 3*y^2, 11*y^2, y]
[0, x^4, 11*x^3 + 3*x^2, 8*x^2, x]

Setting in turn y = 1 and x = 1 we arrive at the lists

[0, 1, 11, 11, 1]
[0, 1, 14,  8, 1]

which are row 4 in triangle A123125 and triangle A179454, respectively.

In case n = 5 the reader might verify the polynomial

p(x,y) = x^5*y + 26*x^4*y^2 + 41*x^3*y^3 + 13*x^2*y^4
         + x*y^5 + 25*x^3*y^2 + 13*x^2*y^3

This polynomial describes much the structure seen in the poster displayed at the bottom of this page. Looking at the coefficients we get:

[0, y^5, 13*y^4 + 13*y^3, 41*y^3 + 25*y^2, 26*y^2, y]
[0, x^5, 26*x^4 + 25*x^3, 41*x^3 + 13*x^2, 13*x^2, x]

The Sage code for computing the shape-statistic is unsurprisingly almost identical to the scripts given above:

def statistic_shape(pi):
    if pi == []: return (0, 0)
    h, w, i, branch, next = 0, 0, len(pi), [0], pi[0]

    while true:
        while next < branch[-1]:
            branch.pop()

        current = 0
        w += 1
        while next > current:
            i -= 1
            h = max(h, len(branch))
            if i == 0: return (w, h) 
            branch.append(next)
            current, next = next, pi[i]

This statistic can now be evaluated with regard to the different variables of interest for example with the function:

from sage.combinat.subset import list_to_dict

def shape_row(n):
    y = var('y')
    S, L = 0, []
    for p in Permutations(n):
        w, h = statistic_shape(p)
        S += x^w*y^h
        L.append(2^w*3^h)
    f = sorted(list_to_dict(L).items())
    
    print " "
    print "*** n =", n, "***"
    print "dist of shapes: ", f
    print "shapes: ", [t[0] for t in f]
    print "shape counts: ", [t[1] for t in f]
    print "number of shapes: ", len(f)
    print "number of permutations: ", sum([t[1] for t in f])
    print S
    print S.list(x)
    print S.list(y)

for n in range(6): shape_row(n)    

Flattening the tree: the caterpillar notation

The 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.

The caterpillar notation is the usual one line notation of a permutation augmented by the symbol '^', inserted every time when the caterpillar is forced to climb up a level in the tree. Thus it is an one dimensional description of a permutation tree. The length of the caterpillar is twice the power of the tree.

Trees in caterpillar notation, n = 3 3^2^1^ 13^2^^ 3^12^^ 23^^1^ 2^13^^ 123^^^

Trees in caterpillar notation, n = 4 4^3^2^1^ 14^3^2^^ 4^13^2^^ 3^14^2^^ 4^3^12^^ 2^14^3^^ 4^2^13^^ 3^2^14^^ 24^3^^1^ 4^23^^1^ 34^^2^1^ 3^24^^1^ 34^^12^^ 23^^14^^ 24^^13^^ 124^3^^^ 13^24^^^ 4^123^^^ 14^23^^^ 2^134^^^ 3^124^^^ 134^^2^^ 234^^^1^ 1234^^^^

Segments of the caterpillar which consist entirely of numbers are called down runs and segments consisting entirely of '^'s are called up runs of the caterpillar. A run is either a up run or a down run. The number of runs and their lengths are characteristics of a permutation.

The correspondence: Permutation <-> Tree

Given a permutation, how to construct the associated rooted tree?

Maple code

perm2tree := proc(perm)
local tree, i, next, root, branch, current;
tree := []; root := 0; branch := [root];
i := 1; next := perm[i];

while true do
  while next < branch[nops(branch)] do
    branch := subsop(nops(branch) = NULL, branch);
  od;
  current := root;

  while next > current
  do
    branch := [op(branch),next];
    i := i + 1;
    if i > nops(perm) then
       tree := [op(tree),branch];
       RETURN(tree)
    fi;
    current := next;
    next := perm[i];
  od;
  tree := [op(tree),branch];
od end:

An example use is:

ListPermTrees := proc(n) local p, P;
P := combinat[permute](n);
for p in P do
   lprint(p, "=>", perm2tree(p));
od end:
ListPermTrees(4);

SageMath code

def plot_tree(E):
    G = Graph()
    G.add_edges(E)
    G.show(layout='tree', tree_root=0, tree_orientation='down')
    
def permutation_to_tree(pi):
    if pi == []: return [[0]]
    root, i, next = 0, 0, pi[0] 
    branch, edges = [root], []
    caterpillar = ""

    while true:
        while next < branch[-1]: 
            branch.pop()
            caterpillar += "^"
        
        current = root
        while next > current:
            edges.append([branch[-1], next])  
            caterpillar += str(next)
            branch.append(next)
            i += 1
            if i == len(pi):
                l = 2*len(pi)-len(caterpillar)
                caterpillar += "^" * l
                return caterpillar
                #plot_tree(edges)
                #return edges
                
            current, next = next, pi[i]

for n in (1..4):
    for p in Permutations(n):
        print p, "=>", permutation_to_tree(p)

[1, 2, 3, 4] => 1234^^^^
[1, 2, 4, 3] => 124^3^^^
[1, 3, 2, 4] => 13^24^^^
[1, 3, 4, 2] => 134^^2^^
[1, 4, 2, 3] => 14^23^^^
[1, 4, 3, 2] => 14^3^2^^
[2, 1, 3, 4] => 2^134^^^
[2, 1, 4, 3] => 2^14^3^^
[2, 3, 1, 4] => 23^^14^^
[2, 3, 4, 1] => 234^^^1^
[2, 4, 1, 3] => 24^^13^^
[2, 4, 3, 1] => 24^3^^1^
[3, 1, 2, 4] => 3^124^^^
[3, 1, 4, 2] => 3^14^2^^
[3, 2, 1, 4] => 3^2^14^^
[3, 2, 4, 1] => 3^24^^1^
[3, 4, 1, 2] => 34^^12^^
[3, 4, 2, 1] => 34^^2^1^
[4, 1, 2, 3] => 4^123^^^
[4, 1, 3, 2] => 4^13^2^^
[4, 2, 1, 3] => 4^2^13^^
[4, 2, 3, 1] => 4^23^^1^
[4, 3, 1, 2] => 4^3^12^^
[4, 3, 2, 1] => 4^3^2^1^

Given a rooted tree, how to construct the associated permutation?

Maple code

We assume the tree given by the list of its branches, this means as the list of all the chains starting at the root of the tree and ending at a leaf.

tree2perm := proc(tree)
local j, k, perm, branch, leaf;
perm := [];
for j from 1 to nops(tree) do
  branch := tree[j];
  for k from 2 to nops(branch) do
     leaf := branch[k];
     if not member(leaf, perm) then
        perm := [op(perm), leaf] fi;
  od;
od:
perm end:

An example use is:

ListPerms := proc(n) local p,P,pi,t;
P := combinat[permute](n);
for p in P do
  t := perm2tree(p):
  pi := tree2perm(t);
  lprint(t, "=>", pi);
od end:

ListPerms(4);

SageMath code

def tree_to_permutation(tree):
    perm = tree.translate(None, '^')
    return [int(p) for p in perm]
    
for n in (1..4):
    for p in Permutations(n):
        t = permutation_to_tree(p)
        print t, "=>", tree_to_permutation(t)

1234^^^^ => [1, 2, 3, 4]
124^3^^^ => [1, 2, 4, 3]
13^24^^^ => [1, 3, 2, 4]
134^^2^^ => [1, 3, 4, 2]
14^23^^^ => [1, 4, 2, 3]
14^3^2^^ => [1, 4, 3, 2]
2^134^^^ => [2, 1, 3, 4]
2^14^3^^ => [2, 1, 4, 3]
23^^14^^ => [2, 3, 1, 4]
234^^^1^ => [2, 3, 4, 1]
24^^13^^ => [2, 4, 1, 3]
24^3^^1^ => [2, 4, 3, 1]
3^124^^^ => [3, 1, 2, 4]
3^14^2^^ => [3, 1, 4, 2]
3^2^14^^ => [3, 2, 1, 4]
3^24^^1^ => [3, 2, 4, 1]
34^^12^^ => [3, 4, 1, 2]
34^^2^1^ => [3, 4, 2, 1]
4^123^^^ => [4, 1, 2, 3]
4^13^2^^ => [4, 1, 3, 2]
4^2^13^^ => [4, 2, 1, 3]
4^23^^1^ => [4, 2, 3, 1]
4^3^12^^ => [4, 3, 1, 2]
4^3^2^1^ => [4, 3, 2, 1]

Summary: Three classifications of permutation trees.

Proposition 1. A permutation p has k down runs if and only if the permutation tree T(p) has width k.

Proposition 2. The length of the longest run of a permutation p is k if and only if the permutation tree T(p) has height k.

Proposition 1 is covered by the enumeration of permutations by the Eulerian numbers A008292 and proposition 2 by the enumeration of permutations by A179454.

The power of the caterpillar notation becomes even more obvious when we note that it immediately leads to a third classification. Just look at the tail of the caterpillar. Classifying the caterpillar by the length of the last up run gives the Stirling cycle numbers! (Definition as in CM, table 245, or DLMF, 26.13.3., ABS(A008275).) This third classification is equivalent to:

Proposition 3. Stirling cycle numbers classify permutation trees according to the length of the first (leftmost) branch.

This description is somewhat simpler then the standard definition using cycle arrangements.

Number of maps p:[n]→[n] with p(x) ≤ x and p^[k](x) = p^[k-1](x).

Joerg Arndt gave this interpretation in A187761 and indicated an algorithm for the generation with restricted growth strings (RGS) for maps. A C# implementation of this algorithm below:

// Generating algorithm due to Joerg Arndt.
// Restricted growth strings (RGS) for maps.
// A000110: f: [n] -> [n] with f(x) <= x and f(x) = f(f(x)).
// A187761: f: [n] -> [n] with f(x) <= x and f(f(x)) = f(f(f(x)))
// general: k-th column of A179455
//          f: [n] -> [n] with f(x) <= x and f^[k-1](x) = f^[k](x) 

namespace OEIS { class A179455 {

static int[] a;

static void Main()
{
    for (int n = 1; n < 11; n++)
    {
        var count = row(n);
        Console.Write("[n = " + n + "] ");
        for (int i = 0; i < n; i++)
            Console.Write(count[i] + ",");
        Console.WriteLine();
    }
    Console.ReadLine();
}

static int[] row(int n)
{
    int[] count = new int[n];
    for (int k = 0; k < n; k++)
    {
        a = new int[n];
        do {
            count[k]++;
        } while (generate(n, k) != 0);
    }
    return count;
}

static int generate(int n, int k)
{
    if (n == 0 || k == 0) return 0;
    int j = n, f, f1, fl;
            
    while (j-- != 0)
    {
        f = a[j];
        while (++f <= j)
        {
            a[j] = f; f1 = f; fl = f1;
            for (int i = 0; i < k; i++)
            {
                fl = f1;
                f1 = a[fl];
            }
            if (f1 == fl) return j;
        }
        a[j] = 0;
    }
    return 0;
}}}

---
The image of the black-red caterpillar was made by Jill Chen from Taipei, Taiwan. It was down loaded from commons.wikimedia.org and is licensed under the Creative Commons Attribution 2.0 Generic license.

The permutation trees with power 5

You can download this poster of permutation trees as a pdf-file. And this article as a pdf-file.