This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/DoubleEnumeration
From OeisWiki
Contents
- 1 Double enumerationsof permutation trees
- 1.1 George Beck's message to seqcomp
- 1.2 Permutation trees
- 1.3 Pairing height with width
- 1.4 Tree-traversal and displacement
- 1.5 Pairing height with displacement
- 1.6 Pairing width with displacement
- 1.7 Flattening the sequences of squares
- 1.8 Generalizing with set operations
- 1.9 The Stirling Eulerian Jumping Jack
- 1.10 Double enumeration triangles: sum of rows
- 1.11 Double enumeration triangles: sum of columns
- 1.12 List of double enumerations of permutation trees
- 1.13 The Maple program
Double enumerations
of permutation trees
| operation ° | intersection | union | minus | converse minus | symmetric difference | ||||||||||||||||||||
| height ° width |
|
|
|
|
|
||||||||||||||||||||
| height ° displacement |
|
|
|
|
|
||||||||||||||||||||
| width ° displacement |
|
|
|
|
|
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.
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.
 |
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;
