This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/DoubleEnumeration

From OeisWiki

Jump to: navigation, search

Double enumerations
of permutation trees

  operation ° intersection union minus converse minus symmetric difference
height °
width
rowA179454
colA008292
row 
col 
row 
col 
row*
col 
row*
col 
height °
displacement
rowA179454
colA130534
row 
col 
row 
col 
row 
col 
rowA111650
colA111650
width °
displacement
rowA008292
colA130534
row 
col 
row*
col 
row 
col*
row 
col 

This is a continuation of the blogs from July: Permutation Types and Permutation Trees.
Edit: The missing sequence numbers refer to sequences explained below, however these sequences were never submitted to OEIS. 

Contents

George Beck's message to seqcomp

George Beck recently wrote on groups.google.com/group/seqcomp :

"The idea of double enumeration seems like a natural extension of the principle of counting a thing in two different ways."

More specific Beck writes: "...say we have a function f[n,k] that counts from n objects those objects x for which ff[x] = k, and similarly for g. Then the matrix fg[i, j] would count those objects x for which ff[x] = i and gg[x] = j. The sum of the row sums will be equal to the sum of the column sums."

As far as I understand Beck's idea this can basically be formalized as

DoubleEnum := proc(objs,f,g,n)
local M,i,j,S,r,k;

M := matrix(n,n,[seq(0,i=1..n^2)]);
for i from 1 to n do for j from 1 to n do
   M[i,j] := nops(f(objs,i) intersect g(objs,j)); 
od od;

print(M); # row sums and col sums
S := seq(add(row(M,r)[k],k=1..n),r=1..n);
print(´Row´,[S],add(r,r=S));
S := seq(add(col(M,r)[k],k=1..n),r=1..n);
print(´Col´,[S],add(r,r=S));
NULL end:

Thus a double enumeration is a quadruple consisting of a set of objects objs, two filter functions f and g of type (objs, criterion) → subobjs returning the objects of objs which satisfy the criterion and a parameter n describing the range [1, n] of f and g.

Beck applied his idea to the enumeration of permutations counting the objects in two ways, by the number of ascents and the number of cycles respectively, thus giving a double enumeration by the Eulerian numbers and the Stirling numbers of the first kind. (See Beck's demonstration.)

Permutation trees

Clearly this idea can be applied to a similar double enumeration which is even simpler to describe: The enumeration of a tree, first with respect to the width of the tree and next with respect to the height of the tree.

Well, this is exactly what we have done in our earlier article on permutation trees. So let us explore these trees further, now in relation to Beck's formalization of the double enumeration.

For convenience we repeat our basic tool, a converter function permutation → tree.

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:

With this utility we can define our set of objects.

Objects := n -> convert(map(perm2tree,combinat[permute](n)),set);

Next we define the two filter functions.  (For those not familiar with the Maple parlance read 'card' instead of 'nops'.)

height := T -> max(op(map(b -> max(nops(b)),T))) - 1;
TreesByHeight := (T, h) -> select(t -> height(t) = h, T):
TreesByWidth  := (T, h) -> select(t -> nops(t) = h, T):

Pairing height with width

A macro will bind things together.

DoubleEnumPermutationTreesByHeightAndWidth := n ->
DoubleEnum(Objects(n), TreesByHeight, TreesByWidth, n):

And here we go:

for n from 1 to 6 do DoubleEnumPermutationTreesByHeightAndWidth(n) od;

                                 [ 1 ]
                                 1,  1

                               [0    1]
                               [1    0]
                                 2, 2

                            [0    0    1]
                            [0    4    0]
                            [1    0    0]
                                 6, 6

                         [0    0     0    1]
                         [0    3    11    0]
                         [0    8     0    0]
                         [1    0     0    0]
                                24, 24

                      [0     0     0     0    1]
                      [0     0    25    26    0]
                      [0    13    41     0    0]
                      [0    13     0     0    0]
                      [1     0     0     0    0]
                               120, 120

                  [0     0      0      0     0    1]
                  [0     0     15    130    57    0]
                  [0    10    183    172     0    0]
                  [0    28    104      0     0    0]
                  [0    19      0      0     0    0]
                  [1     0      0      0     0    0]
                               720, 720

Tree-traversal and displacement

Imagine a worm that crawls around the periphery of the tree above. It starts on the left hand side and revolves the tree in the clockwise sense. After having visited all nodes it stops. We will call the distance from the initial position (the root of the tree) and final position of the worm the displacement of the tree. It is also the level of the node at which the worm stops (the root has level 0). It is also the number of nodes on the branch from the root to final position minus 1. Finally by our convention on the traversal it is also the length of the leftmost branch of the tree.

Pairing height with displacement

As I remarked in proposition 3 in the blog on permutation trees: "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." So let us implement this enumeration also.

TreesByDisplacement := (T, h) -> select(t -> nops(t[nops(t)]) - 1 = h, T):

DoubleEnumPermutationTreesByHeightAndDisplacement := n ->
DoubleEnum(Objects(n),TreesByHeight,TreesByDisplacement,n):
 
for n from 1 to 6 do DoubleEnumPermutationTreesByHeightAndDisplacement(n) od;

                                 [ 1]
                                 1, 1

                               [1    0]
                               [0    1]
                                 2, 2

                            [1    0    0]
                            [1    3    0]
                            [0    0    1]
                                 6, 6

                         [1     0    0    0]
                         [4    10    0    0]
                         [1     1    6    0]
                         [0     0    0    1]
                                24, 24

                     [ 1     0     0     0    0]
                     [14    37     0     0    0]
                     [ 8    12    34     0    0]
                     [ 1     1     1    10    0]
                     [ 0     0     0     0    1]
                               120, 120

                 [ 1      0      0     0     0    0]
                 [51    151      0     0     0    0]
                 [54    104    207     0     0    0]
                 [13     18     17    84     0    0]
                 [ 1      1      1     1    15    0]
                 [ 0      0      0     0     0    1]
                               720, 720

Pairing width with displacement

DoubleEnumPermutationTreesByWidthAndDisplacement := n ->
DoubleEnum(Objects(n),TreesByWidth,TreesByDisplacement,n):

for n from 1 to 6 do DoubleEnumPermutationTreesByWidthAndDisplacement(n) od;

                                 [ 1]
                                 1, 1

                               [0    1]
                               [1    0]
                                 2, 2

                            [0    0    1]
                            [1    3    0]
                            [1    0    0]
                                 6, 6

                          [0    0    0    1]
                          [1    4    6    0]
                          [4    7    0    0]
                          [1    0    0    0]
                                24, 24

                     [ 0     0     0     0    1]
                     [ 1     5    10    10    0]
                     [11    30    25     0    0]
                     [11    15     0     0    0]
                     [ 1     0     0     0    0]
                               120, 120

                 [ 0      0      0     0     0    1]
                 [ 1      6     15    20    15    0]
                 [26     91    120    65     0    0]
                 [66    146     90     0     0    0]
                 [26     31      0     0     0    0]
                 [ 1      0      0     0     0    0]
                               720, 720

Flattening the sequences of squares

Flattening the three sequences of matrices to an integer sequence by concatenation of the rows now leads to three new sequences for OEIS.

[AX5] DoubleEnumPermutationTreesByHeightAndWidth
1,0,1,1,0,0,0,1,0,4,0,1,0,0,0,0,0,1,0,3,11,0,0,8,0,0,1,0,0,
0,0,0,0,0,1,0,0,25,26,0,0,13,41,0,0,0,13,0,0,0,1,0,0,0,0,

[AX6] DoubleEnumPermutationTreesByHeightAndDisplacement
1,1,0,0,1,1,0,0,1,3,0,0,0,1,1,0,0,0,4,10,0,0,1,1,6,0,0,0,0,
1,1,0,0,0,0,14,37,0,0,0,8,12,34,0,0,1,1,1,10,0,0,0,0,0,1,

[AX7] DoubleEnumPermutationTreesByWidthAndDisplacement
1,0,1,1,0,0,0,1,1,3,0,1,0,0,0,0,0,1,1,4,6,0,4,7,0,0,1,0,0,0,
0,0,0,0,1,1,5,10,10,0,11,30,25,0,0,11,15,0,0,0,1,0,0,0,0,

Generalizing with set operations

Does our story ends here? Quite the contrary! Our abstract approach makes it easy to generalize further. We introduce now five types of double enumerations by adding a fifth parameter, an operation, to the DoubleEnum procedure, now GenDoubleEnum(objs,f,g,n,op). We will consider the operations And, Or, Minus, ConverseMinus and SymmetricDifference.

  • DoubleEnumAnd := GenDoubleEnum(objs,f,g,n,intersect)
  • DoubleEnumOr := GenDoubleEnum(objs,f,g,n,union)
  • DoubleEnumMinus := GenDoubleEnum(objs,f,g,n,minus)
  • DoubleEnumConvMinus := GenDoubleEnum(objs,g,f,n,minus)
  • DoubleEnumSymmDiff := GenDoubleEnum(objs,g,f,n,symmdiff)

On the side of the Maple implementation all we have to do is:

Replace: DoubleEnum := proc(objs,f,g,n,op)
by: GenDoubleEnum := proc(objs,f,g,n,op);
Replace: M[i,j] := nops(f(objs,i) intersect g(objs,j)); 
by: M[i,j] := nops(op(f(objs,i),g(objs,j)));

For example we can define now the following function:

PermutationTreesByHeightAndWidth := n ->
GenDoubleEnum(Objects(n), TreesByHeight, TreesByWidth, n, `intersect`):

Similarly we can define another 14 functions (see the Maple code below). The following list gives a short summary.

  • PermutationTreesByHeightAndWidth;
  • PermutationTreesByHeightOrWidth;
  • PermutationTreesByHeightMinusWidth;
  • PermutationTreesByWidthMinusHeight;
  • PermutationTreesByWidthSymmdiffHeight;
  • PermutationTreesByHeightAndDisplacement;
  • PermutationTreesByHeightOrDisplacement;
  • PermutationTreesByHeightMinusDisplacement;
  • PermutationTreesByDisplacementMinusHeight;
  • PermutationTreesByHeightSymmdiffDisplacement;
  • PermutationTreesByWidthAndDisplacement;
  • PermutationTreesByWidthOrDisplacement;
  • PermutationTreesByWidthMinusDisplacement;
  • PermutationTreesByDisplacementMinusWidth;
  • PermutationTreesByWidthSymmdiffDisplacement;

We will use also shortcuts in a three letter format |class | set-operation | class|. The next table indicates their use.

  operation ° intersection union minus converse minus symmetric difference
height °
width
H ∩ W H ∪ W H \ W W \ H H Δ W
height °
displacement
H ∩ D H ∪ D H \ D D \ H H Δ D
width °
displacement
W ∩ D W ∪ D W \ D  D \ W W Δ D

Do these new enumerations make any sense? I do believe so. Because the underlying set, the permutations, is fundamental to many combinatorial problems and the operations used are the basic set theoretic ones.

We know that the rows and columns in the Eulerian and the Stirling case sum to n!. To what sum these entities in the new cases?

 HIW : height       intersect width        : A000142, n!
 HID : height       intersect displacement : A000142, n!
 WID : width        intersect displacement : A000142, n!
 HMW : height       minus     width        : A062119, n!*(n-1)
 HMD : height       minus     displacement : A062119, n!*(n-1)
 WMH : width        minus     height       : A062119, n!*(n-1)
 WMD : width        minus     displacement : A062119, n!*(n-1)
 DMH : displacement minus     height       : A062119, n!*(n-1)
 DMW : displacement minus     width        : A062119, n!*(n-1)
 HUW : height       union     width        : A175925, n!*(n+1)(2n+1)
 HUD : height       union     displacement : A175925, n!*(n+1)(2n+1)
 WUD : width        union     displacement : A175925, n!*(n+1)(2n+1)
 WSH : width        symmdiff  height       : A052609, n!*(n-1)2
 WSD : width        symmdiff  displacement : A052609, n!*(n-1)2
 HSD : height       symmdiff  displacement : A001105, 2n^2

The Stirling Eulerian Jumping Jack

Although the intuitive meaning is at first sight somewhat hidden behind this formal calculus it can be easily reconstructed. For instance the case George Beck considered in his demonstration "Eulerian numbers versus Stirling numbers of the first kind" corresponds to the set-operation of intersection and describes in the framework of our tree interpretation the interplay between the length of the first branch of a permutation tree and the number of leaves of this tree.

Image:StirlingEulerJumpingJack.png

If I had to implement an animated demonstration of this relation I would draw a permutation tree (number of nodes fixed) and let the length of the leftmost branch be adjustable by the user. If the user pulls this 'leg' the displacement increases and the width decreases. If the user let loose again the tree will widen. At each stage the tree can reorganize the remaining branches in several ways.

This is basically what "Eulerian numbers versus Stirling numbers of the first kind" is about. I would call the animation `Der Stirling-Eulersche Hampelmann´ (The Stirling Eulerian Jumping Jack) as it reminds me of a toy almost every child once played with.
Image by John Leech, from: The Comic History of Rome by Gilbert Abbott A Beckett, Bradbury, Evans & Co, London, 1850s. File is in the public domain and taken from Wikipedia.

Double enumeration triangles: sum of rows

[A179454] row(hiw) 
                            ´Row´, [1], 1
                           ´Row´, [1, 1], 2
                         ´Row´, [1, 4, 1], 6
                       ´Row´, [1, 14, 8, 1], 24
                    ´Row´, [1, 51, 54, 13, 1], 120
                ´Row´, [1, 202, 365, 132, 19, 1], 720
            ´Row´, [1, 876, 2582, 1289, 265, 26, 1], 5040
[AX8] row(huw)
                            ´Row´, [1], 1
                           ´Row´, [3, 3], 6
                        ´Row´, [8, 14, 8], 30
                     ´Row´, [27, 66, 48, 27], 168
                ´Row´, [124, 324, 336, 172, 124], 1080
            ´Row´, [725, 1730, 2545, 1380, 815, 725], 7920
     ´Row´, [5046, 10296, 20532, 12774, 6630, 5196, 5046], 65520
[AX9] row(hmw)
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [2, 8, 2], 12
                      ´Row´, [3, 42, 24, 3], 72
                   ´Row´, [4, 204, 216, 52, 4], 480
               ´Row´, [5, 1010, 1825, 660, 95, 5], 3600
          ´Row´, [6, 5256, 15492, 7734, 1590, 156, 6], 30240 
[AX1] row(wmh); see also: [A062119]
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [2, 8, 2], 12
                      ´Row´, [3, 33, 33, 3], 72
                  ´Row´, [4, 104, 264, 104, 4], 480
              ´Row´, [5, 285, 1510, 1510, 285, 5], 3600
          ´Row´, [6, 720, 7146, 14496, 7146, 720, 6], 30240
[AX2] row(wsh); see also: [A052609], [A030495(n)-1]
                            ´Row´, [0], 0
                           ´Row´, [2, 2], 4
                        ´Row´, [7, 10, 7], 24
                     ´Row´, [26, 46, 46, 26], 144
                ´Row´, [123, 198, 318, 198, 123], 960
            ´Row´, [724, 948, 1928, 1928, 948, 724], 7200
     ´Row´, [5045, 5640, 10995, 17120, 10995, 5640, 5045], 60480 
[A179454] row(hid)
                            ´Row´, [1], 1
                           ´Row´, [1, 1], 2
                         ´Row´, [1, 4, 1], 6
                       ´Row´, [1, 14, 8, 1], 24
                    ´Row´, [1, 51, 54, 13, 1], 120
                ´Row´, [1, 202, 365, 132, 19, 1], 720
            ´Row´, [1, 876, 2582, 1289, 265, 26, 1], 5040
[AX10] row(hud)
                            ´Row´, [1], 1
                           ´Row´, [3, 3], 6
                        ´Row´, [8, 14, 8], 30
                     ´Row´, [27, 66, 48, 27], 168
                ´Row´, [124, 324, 336, 172, 124], 1080
            ´Row´, [725, 1730, 2545, 1380, 815, 725], 7920
     ´Row´, [5046, 10296, 20532, 12774, 6630, 5196, 5046], 65520
[AX11] row(hmd)
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [2, 8, 2], 12
                      ´Row´, [3, 42, 24, 3], 72
                   ´Row´, [4, 204, 216, 52, 4], 480
               ´Row´, [5, 1010, 1825, 660, 95, 5], 3600
          ´Row´, [6, 5256, 15492, 7734, 1590, 156, 6], 30240
[AX12] row(dmh)
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [4, 6, 2], 12
                      ´Row´, [18, 33, 18, 3], 72
                  ´Row´, [96, 200, 140, 40, 4], 480
              ´Row´, [600, 1370, 1125, 425, 75, 5], 3600
        ´Row´, [4320, 10584, 9744, 4410, 1050, 126, 6], 30240
[A111650] row(hsd)
                            ´Row´, [2], 2
                           ´Row´, [4, 4], 8
                         ´Row´, [6, 6, 6], 18
                       ´Row´, [8, 8, 8, 8], 32
                   ´Row´, [10, 10, 10, 10, 10], 50
                 ´Row´, [12, 12, 12, 12, 12, 12], 72
               ´Row´, [14, 14, 14, 14, 14, 14, 14], 98
[A008292] row(wid)
                            ´Row´, [1], 1
                           ´Row´, [1, 1], 2
                         ´Row´, [1, 4, 1], 6
                      ´Row´, [1, 11, 11, 1], 24
                    ´Row´, [1, 26, 66, 26, 1], 120
                 ´Row´, [1, 57, 302, 302, 57, 1], 720
           ´Row´, [1, 120, 1191, 2416, 1191, 120, 1], 5040 
[AX3] row(wud); see also: [A030495], [A175925]
                            ´Row´, [1], 1
                           ´Row´, [3, 3], 6
                        ´Row´, [8, 14, 8], 30
                     ´Row´, [27, 57, 57, 27], 168
                ´Row´, [124, 224, 384, 224, 124], 1080
           ´Row´, [725, 1005, 2230, 2230, 1005, 725], 7920
     ´Row´, [5046, 5760, 12186, 19536, 12186, 5760, 5046], 65520
[AX1] row(wmd)
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [2, 8, 2], 12
                      ´Row´, [3, 33, 33, 3], 72
                  ´Row´, [4, 104, 264, 104, 4], 480
              ´Row´, [5, 285, 1510, 1510, 285, 5], 3600
          ´Row´, [6, 720, 7146, 14496, 7146, 720, 6], 30240
[AX12] row(dmw)
                            ´Row´, [0], 0
                           ´Row´, [1, 1], 2
                         ´Row´, [4, 6, 2], 12
                      ´Row´, [18, 33, 18, 3], 72
                  ´Row´, [96, 200, 140, 40, 4], 480
              ´Row´, [600, 1370, 1125, 425, 75, 5], 3600
        ´Row´, [4320, 10584, 9744, 4410, 1050, 126, 6], 30240
[AX2] row(wsd); see also: [A052609], [A030495(n)-1]
                            ´Row´, [0], 0
                           ´Row´, [2, 2], 4
                        ´Row´, [7, 10, 7], 24
                     ´Row´, [26, 46, 46, 26], 144
                ´Row´, [123, 198, 318, 198, 123], 960
            ´Row´, [724, 948, 1928, 1928, 948, 724], 7200
     ´Row´, [5045, 5640, 10995, 17120, 10995, 5640, 5045], 60480

Double enumeration triangles: sum of columns

[A008292] col(hiw)
                            ´Col´, [1], 1
                           ´Col´, [1, 1], 2
                         ´Col´, [1, 4, 1], 6
                      ´Col´, [1, 11, 11, 1], 24
                    ´Col´, [1, 26, 66, 26, 1], 120
                 ´Col´, [1, 57, 302, 302, 57, 1], 720
           ´Col´, [1, 120, 1191, 2416, 1191, 120, 1], 5040
[AX3] col(huw); see also: [A030495], [A175925]
                            ´Col´, [1], 1
                           ´Col´, [3, 3], 6
                        ´Col´, [8, 14, 8], 30
                     ´Col´, [27, 57, 57, 27], 168
                ´Col´, [124, 224, 384, 224, 124], 1080
           ´Col´, [725, 1005, 2230, 2230, 1005, 725], 7920
     ´Col´, [5046, 5760, 12186, 19536, 12186, 5760, 5046], 65520
[AX4] col(hmw); see also: [A033312], [A062119]
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [5, 2, 5], 12
                     ´Col´, [23, 13, 13, 23], 72
                  ´Col´, [119, 94, 54, 94, 119], 480
             ´Col´, [719, 663, 418, 418, 663, 719], 3600
       ´Col´, [5039, 4920, 3849, 2624, 3849, 4920, 5039], 30240 
[AX16] col(wmh)
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [5, 2, 5], 12
                     ´Col´, [23, 10, 16, 23], 72
                 ´Col´, [119, 69, 66, 107, 119], 480
             ´Col´, [719, 518, 355, 588, 701, 719], 3600
       ´Col´, [5039, 4164, 2458, 3751, 4775, 5014, 5039], 30240
[AX17] col(wsh)
                            ´Col´, [0], 0
                           ´Col´, [2, 2], 4
                        ´Col´, [7, 10, 7], 24
                     ´Col´, [26, 52, 40, 26], 144
                ´Col´, [123, 273, 282, 159, 123], 960
            ´Col´, [724, 1528, 2180, 1248, 796, 724], 7200
      ´Col´, [5045, 9420, 17950, 11485, 6365, 5170, 5045], 60480
[A130534] col(hid)
                            ´Col´, [1], 1
                           ´Col´, [1, 1], 2
                         ´Col´, [2, 3, 1], 6
                       ´Col´, [6, 11, 6, 1], 24
                   ´Col´, [24, 50, 35, 10, 1], 120
                ´Col´, [120, 274, 225, 85, 15, 1], 720
           ´Col´, [720, 1764, 1624, 735, 175, 21, 1], 5040
[AX13] col(hud)
                            ´Col´, [1], 1
                           ´Col´, [3, 3], 6
                        ´Col´, [10, 12, 8], 30
                     ´Col´, [42, 57, 42, 27], 168
                ´Col´, [216, 320, 260, 160, 124], 1080
           ´Col´, [1320, 2090, 1845, 1145, 795, 725], 7920
      ´Col´, [9360, 15624, 14784, 9450, 6090, 5166, 5046], 65520
[A182923] col(hmd)
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [4, 3, 5], 12
                     ´Col´, [18, 13, 18, 23], 72
                  ´Col´, [96, 70, 85, 110, 119], 480
             ´Col´, [600, 446, 495, 635, 705, 719], 3600
       ´Col´, [4320, 3276, 3416, 4305, 4865, 5019, 5039], 30240
[AX16] col(dmh)
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [5, 2, 5], 12
                     ´Col´, [23, 10, 16, 23], 72
                 ´Col´, [119, 69, 66, 107, 119], 480
             ´Col´, [719, 518, 355, 588, 701, 719], 3600
       ´Col´, [5039, 4164, 2458, 3751, 4775, 5014, 5039], 30240
[A111650] col(hsd)
                            ´Col´, [2], 2
                           ´Col´, [4, 4], 8
                         ´Col´, [6, 6, 6], 18
                       ´Col´, [8, 8, 8, 8], 32
                   ´Col´, [10, 10, 10, 10, 10], 50
                 ´Col´, [12, 12, 12, 12, 12, 12], 72
               ´Col´, [14, 14, 14, 14, 14, 14, 14], 98
[A130534] col(wid)
                            ´Col´, [1], 1
                           ´Col´, [1, 1], 2
                         ´Col´, [2, 3, 1], 6
                       ´Col´, [6, 11, 6, 1], 24
                   ´Col´, [24, 50, 35, 10, 1], 120
                ´Col´, [120, 274, 225, 85, 15, 1], 720
           ´Col´, [720, 1764, 1624, 735, 175, 21, 1], 5040
[AX13] col(wud)
                            ´Col´, [1], 1
                           ´Col´, [3, 3], 6
                        ´Col´, [10, 12, 8], 30
                     ´Col´, [42, 57, 42, 27], 168
                ´Col´, [216, 320, 260, 160, 124], 1080
           ´Col´, [1320, 2090, 1845, 1145, 795, 725], 7920
      ´Col´, [9360, 15624, 14784, 9450, 6090, 5166, 5046], 65520
[AX14] col(wmd)
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [4, 3, 5], 12
                     ´Col´, [18, 13, 18, 23], 72
                  ´Col´, [96, 70, 85, 110, 119], 480
             ´Col´, [600, 446, 495, 635, 705, 719], 3600
       ´Col´, [4320, 3276, 3416, 4305, 4865, 5019, 5039], 30240
[AX4] col(dmw)
                            ´Col´, [0], 0
                           ´Col´, [1, 1], 2
                         ´Col´, [5, 2, 5], 12
                     ´Col´, [23, 13, 13, 23], 72
                  ´Col´, [119, 94, 54, 94, 119], 480
             ´Col´, [719, 663, 418, 418, 663, 719], 3600
       ´Col´, [5039, 4920, 3849, 2624, 3849, 4920, 5039], 30240
[AX15] col(wsd)
                            ´Col´, [0], 0
                           ´Col´, [2, 2], 4
                         ´Col´, [8, 9, 7], 24
                     ´Col´, [36, 46, 36, 26], 144
                ´Col´, [192, 270, 225, 150, 123], 960
           ´Col´, [1200, 1816, 1620, 1060, 780, 724], 7200
      ´Col´, [8640, 13860, 13160, 8715, 5915, 5145, 5045], 60480 

List of double enumerations of permutation trees

     (height intersect width)

                [1]
             [0    1]
             [1    0]
          [0    0    1]
          [0    4    0]
          [1    0    0]
       [0    0     0    1]
       [0    3    11    0]
       [0    8     0    0]
       [1    0     0    0]
    [0     0     0     0    1]
    [0     0    25    26    0]
    [0    13    41     0    0]
    [0    13     0     0    0]
    [1     0     0     0    0]

      (height union width)

                [1]
             [2    1]
             [1    2]
          [2    5    1]
          [5    4    5]
          [1    5    2]
      [ 2    12    12     1]
      [15    22    14    15]
      [ 9    11    19     9]
      [ 1    12    12     2]
   [ 2    27    67    27     1]
   [52    77    92    51    52]
   [55    67    79    80    55]
   [14    26    79    39    14]
   [ 1    27    67    27     2]

      (height minus width)

               [0]
             [1    0]
             [0    1]
          [1    1    0]
          [4    0    4]
          [0    1    1]
      [ 1     1    1     0]
      [14    11    3    14]
      [ 8     0    8     8]
      [ 0     1    1     1]
   [ 1     1     1     1     0]
   [51    51    26    25    51]
   [54    41    13    54    54]
   [13     0    13    13    13]
   [ 0     1     1     1     1]

       (width minus height)

               [0]
             [1    0]
             [0    1]
          [1    1    0]
          [4    0    4]
          [0    1    1]
      [ 1    1     1     0]
      [11    8     3    11]
      [11    0    11    11]
      [ 0    1     1     1]
   [ 1     1     1     1     0]
   [26    26    13    13    26]
   [66    41    25    66    66]
   [26     0    26    26    26]
   [ 0     1     1     1     1]

     (height symmdiff width)

               [0]
             [2    0]
             [0    2]
          [2    5    0]
          [5    0    5]
          [0    5    2]
      [ 2    12    12     0]
      [15    19     3    15]
      [ 9     3    19     9]
      [ 0    12    12     2]
   [ 2    27    67    27     0]
   [52    77    67    25    52]
   [55    54    38    80    55]
   [14    13    79    39    14]
   [ 0    27    67    27     2]

  (height intersect displacement)

               [1]
             [1    0]
             [0    1]
          [1    0    0]
          [1    3    0]
          [0    0    1]
       [1     0    0    0]
       [4    10    0    0]
       [1     1    6    0]
       [0     0    0    1]
   [ 1     0     0     0    0]
   [14    37     0     0    0]
   [ 8    12    34     0    0]
   [ 1     1     1    10    0]
   [ 0     0     0     0    1]

   (height union displacement)

               [1]
             [1    2]
             [2    1]
          [2    4    2]
          [5    4    5]
          [3    4    1]
      [ 6    12     7     2]
      [16    15    20    15]
      [13    18     8     9]
      [ 7    12     7     1]
   [24    51    36    11     2]
   [61    64    86    61    52]
   [70    92    55    64    55]
   [36    62    47    13    14]
   [25    51    36    11     1]

    (height minus displacement)

               [0]
             [0    1]
             [1    0]
          [0    1    1]
          [3    1    4]
          [1    1    0]
      [ 0    1     1     1]
      [10    4    14    14]
      [ 7    7     2     8]
      [ 1    1     1     0]
   [ 0     1     1     1     1]
   [37    14    51    51    51]
   [46    42    20    54    54]
   [12    12    12     3    13]
   [ 1     1     1     1     0]

    (displacement minus height)

               [0]
             [0    1]
             [1    0]
          [1    1    2]
          [3    0    3]
          [1    1    0]
      [ 5    2     5     6]
      [11    1    10    11]
      [ 6    6     0     6]
      [ 1    1     1     0]
   [23    10    16    23    24]
   [50    13    38    49    50]
   [35    35     1    34    35]
   [10    10    10     0    10]
   [ 1     1     1     1     0]

   (height symdiff displacement)

               [2]
             [2    2]
             [2    2]
          [2    2    2]
          [2    2    2]
          [2    2    2]
        [2    2    2    2]
        [2    2    2    2]
        [2    2    2    2]
        [2    2    2    2]
     [2    2    2    2    2]
     [2    2    2    2    2]
     [2    2    2    2    2]
     [2    2    2    2    2]
     [2    2    2    2    2]

  (width intersect displacement)

               [1]
             [0    1]
             [1    0]
          [0    0    1]
          [1    3    0]
          [1    0    0]
        [0    0    0    1]
        [1    4    6    0]
        [4    7    0    0]
        [1    0    0    0]
   [ 0     0     0     0    1]
   [ 1     5    10    10    0]
   [11    30    25     0    0]
   [11    15     0     0    0]
   [ 1     0     0     0    0]

    (width union displacement)

               [1]
             [2    1]
             [1    2]
          [3    4    1]
          [5    4    5]
          [2    4    2]
      [ 7    12     7     1]
      [16    18    11    12]
      [13    15    17    12]
      [ 6    12     7     2]
   [25    51    36    11     1]
   [49    71    51    26    27]
   [79    86    76    76    67]
   [39    61    61    36    27]
   [24    51    36    11     2]

    (width minus displacement)

               [0]
             [1    0]
             [0    1]
          [1    1    0]
          [3    1    4]
          [0    1    1]
      [ 1    1     1     0]
      [10    7     5    11]
      [ 7    4    11    11]
      [ 0    1     1     1]
   [ 1     1     1     1     0]
   [25    21    16    16    26]
   [55    36    41    66    66]
   [15    11    26    26    26]
   [ 0     1     1     1     1]

    (displacement minus width)

               [0]
             [1    0]
             [0    1]
          [2    1    1]
          [3    0    3]
          [0    1    1]
       [ 6    5    2     5]
       [11    7    4    11]
       [ 6    0    6     6]
       [ 0    1    1     1]
   [24    23    13    13    23]
   [50    45    20    35    50]
   [35    25    10    35    35]
   [10     0    10    10    10]
   [ 0     1     1     1     1]

   (width symmdiff displacement)

               [0]
             [2    0]
             [0    2]
          [3    4    0]
          [4    1    5]
          [1    4    2]
      [ 7    12     7     0]
      [15    14     5    12]
      [ 9     8    17    12]
      [ 5    12     7     2]
   [25    51    36    11     0]
   [48    66    41    16    27]
   [68    56    51    76    67]
   [28    46    61    36    27]
   [23    51    36    11     2]   

The Maple program

with(linalg):
readlib(symmdiff):

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:

Objects := n -> convert(map(perm2tree,combinat[permute](n)),set):
 
height := T -> max(op(map(b -> max(nops(b)),T))) - 1:
width := t -> nops(t):
displacement := t -> nops(t[nops(t)]) - 1:

TreesByHeight := (T,h) -> select(t -> height(t) = h, T):
TreesByWidth := (T,h) -> select(t -> width(t) = h, T):
TreesByDisplacement := (T,h) -> select(t -> displacement(t) = h, T):

DoubleEnum := proc(objs,f,g,n,op,opt)
local M,i,j,R,C,r,k;
M := matrix(n,n,[seq(0,i=1..n^2)]);
for i from 1 to n do for j from 1 to n do
  M[i,j] := nops(op(f(objs,i), g(objs,j))); 
od od;
# Output: row sums and col sums
R := seq(add(row(M,r)[k],k=1..n),r=1..n);
C := seq(add(col(M,r)[k],k=1..n),r=1..n);
if member(opt,{'mat','all'}) then print(M) fi; 
if member(opt,{'row','all'}) then print(´Row´,[R],add(r,r=R)) fi;
if member(opt,{'col','all'}) then print(´Col´,[C],add(r,r=C)) fi;
NULL end:

PermutationTreesByHeightAndWidth := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByWidth,n,`intersect`,opt):
PermutationTreesByHeightOrWidth := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByWidth,n,`union`,opt):
PermutationTreesByHeightMinusWidth := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByWidth,n,`minus`,opt):
PermutationTreesByWidthMinusHeight := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByHeight,n,`minus`,opt):
PermutationTreesByWidthSymmdiffHeight := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByHeight,n,`symmdiff`,opt):
PermutationTreesByHeightAndDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByDisplacement,n,`intersect`,opt):
PermutationTreesByHeightOrDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByDisplacement,n,`union`,opt):
PermutationTreesByHeightMinusDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByDisplacement,n,`minus`,opt):
PermutationTreesByDisplacementMinusHeight := (n,opt) ->
DoubleEnum(Objects(n),TreesByDisplacement,TreesByHeight,n,`minus`,opt):
PermutationTreesByHeightSymmdiffDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByHeight,TreesByDisplacement,n,`symdiff`,opt):
PermutationTreesByWidthAndDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByDisplacement,n,`intersect`,opt):
PermutationTreesByWidthOrDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByDisplacement,n,`union`,opt):
PermutationTreesByWidthMinusDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByDisplacement,n,`minus`,opt):
PermutationTreesByDisplacementMinusWidth := (n,opt) ->
DoubleEnum(Objects(n),TreesByDisplacement,TreesByWidth,n,`minus`,opt):
PermutationTreesByWidthSymmdiffDisplacement := (n,opt) ->
DoubleEnum(Objects(n),TreesByWidth,TreesByDisplacement,n,`symmdiff`,opt):

alias(HIW=PermutationTreesByHeightAndWidth):
alias(HUW=PermutationTreesByHeightOrWidth):
alias(HMW=PermutationTreesByHeightMinusWidth):
alias(WMH=PermutationTreesByWidthMinusHeight):
alias(WSH=PermutationTreesByWidthSymmdiffHeight):
alias(HID=PermutationTreesByHeightAndDisplacement):
alias(HUD=PermutationTreesByHeightOrDisplacement):
alias(HMD=PermutationTreesByHeightMinusDisplacement):
alias(DMH=PermutationTreesByDisplacementMinusHeight):
alias(HSD=PermutationTreesByHeightSymmdiffDisplacement):
alias(WID=PermutationTreesByWidthAndDisplacement):
alias(WUD=PermutationTreesByWidthOrDisplacement):
alias(WMD=PermutationTreesByWidthMinusDisplacement):
alias(DMW=PermutationTreesByDisplacementMinusWidth):
alias(WSD=PermutationTreesByWidthSymmdiffDisplacement):

# The print options are 'row', 'col', 'mat' and 'all'.
Print := proc(b) local n; print(`b`): 
for n in [$1..6] do b(n,opt) od: end:

for opt in ['row','col','all'] do
for enum in [HIW,HUW,HMW,WMH,WSH,HID,HUD,DMH,HMD,HSD,WID,WUD,WMD,DMW,WSD] do
Print(enum) od od;
Personal tools