% % http://www.research.att.com/~njas/sequences/a079438p.txt % % Few lemmas & conjectures concerning the gatomorphism A057505/A057506, % i.e. Donaghey's map M as presented in % R. Donaghey, Automorphisms on Catalan trees and bracketing, % J. Combin. Theory, Series B, 29 (1980), 75-90. % % by Antti Karttunen, January 2003, http://www.iki.fi/~kartturi/ % % Some of the definitions & conditions are elaborated here % with the Prolog-code. % % This works with GNU prolog http://www.gnu.org/software/prolog % % Load as: % consult('c:\\matikka\\Nekomorphisms\\a079438p.txt'). % % a057163 implements the reflection of plane binary trees (A057163): % (a057163 stands for flip) a057163([],[]). a057163([L1|R1],[L2|R2]) :- a057163(L1,R2), a057163(R1,L2). % a057164 implements the reflection of plane general trees (A057164): % (dr stands for deepreverse) % Note the double usage possible in Prolog: % In predicate extend we use a057164(L,R) to REFLECT the parenthesization % present in the instantiated variable L, and stores the result % into uninstantiated variable R, % but at another time we use a057164(T,T) to CHECK that the instantiated % variable T contains a symmetric parenthesization/general tree. a057164([],[]). a057164([L1|R1],Z) :- a057164(L1,L2), a057164(R1,R2), append(R2,[L2],Z). applygat(a057163,X,Y) :- a057163(X,Y). applygat(a057164,X,Y) :- a057164(X,Y). % % append is provided by Prolog, but could defined like: % % append([],B,B). % B appended to the end of empty list = B. (B can be empty also). % % append([A1|AR],B,[A1|CR]) :- % append(AR,B,CR). % % Works like this: % % | ?- append([a,b,c],[],Z). % % Z = [a,b,c] % % yes % | ?- append([a,b,c],[1,2,3,4],Z). % % Z = [a,b,c,1,2,3,4] % % yes % | ?- append(A,[1,2,3,4],[a,b,c,1,2,3,4]). % % A = [a,b,c] ? ; % % no % | ?- append([a,b],B,[a,b,c,1,2,3,4]). % % B = [c,1,2,3,4] % % yes % % The following gives all lists A & B whose concatenation is [a,b,c]: % | ?- append(A,B,[a,b,c]). % % A = [] % B = [a,b,c] ? ; % % A = [a] % B = [b,c] ? ; % % A = [a,b] % B = [c] ? ; % % A = [a,b,c] % B = [] ? ; % % no % | ?- % symmetric_trees_with_primitive_and_right_slanting_zigzag_tree([[]|R]) :- extend([],R). extend(L,[R]) :- a057164(L,R), a057163([R],T), a057164(T,T). extend(L,[T|[R]]) :- a057164(L,R), a057163([R],L2), extend(L2,FT), a057163(FT,T), a057164(T,T). % % If we had infinite wisdom, i.e. an infinite stack, % and an infinitely fast computer, the following would give % all the solutions: % % | ?- symmetric_trees_with_primitive_and_right_slanting_zigzag_tree(Z). % % Z = [[],[]] ? ; % % Z = [[],[[],[]],[]] ? ; % % Z = [[],[[[],[]],[[],[[]],[]],[[],[]]],[]] ? ; % % But because we live in a real world, we get a stack overflow % after the third solution. % The known three parenthesizations whose zigzag-trees are primitive % and right-slanting are thus: % (() ()), (() (() ()) ()), (() ((() ()) (() (()) ()) (() ())) ()) % with sizes 2, 5 and 14, incidentally. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Lemma 0: % % If we have two involutions A & B (in some abstract group G), % then their composite's AB = A o B action on some finite set X partitions % it (the set X) to distinct cycles of various lengths. % (Well, I'm introducing this as generally as possible. % I don't know whether we need for this to also stipulate % that they have no common fixed points. % Anyways, I wouldn't be surprised if this result had % been explicitly stated in the group theory.) % Of these cycles, we can state that: % % A) The odd cycles containing fixed points of A contain a fixed point % of B too. % The fixed point of B sitting (c+1)/2 further than that of A, % where c is the cycle's length. % % B) In the even cycles, if there are fixed points of A or fixed points of B, % they occur in pairs, sitting on opposite sides (both being of % the same type). % % (Can we have more than two fixed points in one cycle?) % % % Proof: % % For odd cases, consider the following diagram: % % t0 A s0 % ------ % B / \ B % / \ % s2 / \ t1 % \ / % A \ / A % \ B / % ------ % t2 s1 % % Where, if there are no fixed points of either B or A, % we have two separate cycles of three % (we define BA = B o A). % % t1 = BA(t0), t2 = BA(t1), t0 = BA(t2) % and % s1 = BA(s0), s2 = BA(s1), s0 = BA(s2) % % However, if we stipulate that there is at least % one element fixed by A, then, without the loss % of generalization, we can assume that it is t0, % thus s0 = t0. % thus t1 = BA(t0) = BA(s0) = s2 % and t2 = BA(t1) = BA(s2) = s1, % and t0 = BA(t2) = BA(s1) = s0 % (thus we came full circle without a contradiction.) % This means that instead of two distinct 3-cycles % we have now one 3-cycle: (t0=s0,t1=s2,t2=s1) % of which the first element is fixed by A, % and the last element is fixed by B. % % % % For even cases, consider the following diagram: % % t0 A s0 % ------ % B / \ B % / \ % s3 / \ t1 % | | % A | | A % | | % t3| |s1 % \ / % B \ / B % \ A / % ------ % s2 t2 % % Again, we may have two distinct 4-cycles: % t1 = BA(t0), t2 = BA(t1), t3 = BA(t2), t0 = BA(t3). % and % s1 = BA(s0), s2 = BA(s1), s3 = BA(s2), s0 = BA(s3). % % However, if we stipulate that there is at least % element fixed by A, then, without the loss of % generalization, we can assume that it is t0, % thus s0 = t0. % thus t1 = BA(t0) = BA(s0) = s3 % and t2 = BA(t1) = BA(s3) = s2, % and t3 = BA(t2) = BA(s2) = s1 % and t0 = BA(t3) = BA(s1) = s0 % (thus again we came full circle without a contradiction.) % This means that instead of two distinct 4-cycles % we have now one 4-cycle: (t0=s0,t1=s3,t2=s2,t3=s1) % of which the first element is fixed by A, % and the element on the opposite side of the cycle % is also fixed by A. % % Alternatively, we may equate, say s0=t1, which means % that t1 is fixed by B, and then we get a similar result, % that the opposite element t3 must also be fixed by B. % % These both diagrams generalize to any polygons % of 2(2n+1) and 2(2n) elements respectively, with the % same result holding there. QED. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % First we prove that a057163(t) != a057164(t) for all trees except % the trivial cases of empty tree and a tree of size one % (i.e. A057163(n) is never A057164(n), when n > 1) % that is, a general tree larger than one edge can never be % reflected by flipping its underlying binary tree representation, % nor vice versa, a binary tree reflected by reflecting % the corresponding general tree. % % In the following diagrams the letters A,B, etc. indicate % various subtrees in the original tree (viewed as a binary % tree), and A', B', ... indicate the corresponding subtrees % recursively flipped with a057163 (A057163), and A~, B~ the same % subtrees recursively deep-reversed with a057164 (A057164). % Note that in general, we can neither assume nor exclude % the possibility that the subtree marked with A at the left % hand side tree is equal or not equal to the subtree marked % A' or A~ at the right hand side tree. % However, we can be sure that their weights are same, % because the automorphisms do not change the size of a tree. % % % Automorphism a057163 flips (reflects) the underlying binary tree of % the general tree: % % A B B' A' % \/ --> \/ % % Automorphism a057164 reflects the general tree, i.e. deep reverses % the corresponding general parenthesization. % We also show how the same tree looks after the bin-tree % flipping (downward arrows). % % A () a057164 A~() % \/ --> \/ % % | a057163 % v % Here the results are equivalent only in % () A' the trivial case A = (). % \/ % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % B () dr A~() % A \/ --> B~\/ % \/ \/ % % | a057163 % v % % () B' Here the results can never be equivalent % \/ A' because the lefthand side subtree of the % \/ bin-tree flipped tree is one node larger % than the lefthand side subtree of the % gen-tree reflected tree. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % C () A~() % B \/ dr B~\/ % A \/ --> C~\/ % \/ \/ % % | a057163 % v % % () C' Here the results can never be equivalent % \/ B' because the lefthand side subtree (B'+C'+()) % \/ A' of the bin-tree flipped tree is sizeof(B)+1 nodes % \/ larger than the lefthand side subtree (only C~) % of the gen-tree reflected tree. % % et cetera. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Lemma 1: % The automorphism A057505 which is a composition of % automorphisms A057163 & A057164, i.e. A057505(n) = A057164(A057163(n)) % and its inverse, A057506 = A057163 o A057164, % never fixes any tree after the trivial trees of size 0 and 1. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % In general, for degree > 1 general trees, the operation dr changes % the balance of the corresponding binary tree as follows: % % U () L () % \/ \/ % . dr . % . ---> . % L . U . % \/ \/ % % That is, if the balance is first as: % wt(L)|wt(R) % where R indicates the whole right hand side of the subtree % (i.e. excluding the L and the root node) then after dr operation % it is: % wt(U)|(wt(R)-wt(U)+wt(L)) % Here U is the rightmost subtree of the corresponding general % tree. (The rightmost sub-parenthesization). % Thus balance stays same if only if wt(U) = wt(L). % Because in symmetric binary trees (of size > 1) L cannot % be of the same size as U, we get % % Lemma 2: % If the tree T is symmetric as a binary tree, % with size > 1, then a057164(T) is NOT symmetric as a binary tree. % (regardless whether a057164(T) = T or a057164(T) != T). % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % We are interested about 2-cycles of A057505/A057506. % Again we consider only tree larger than one node. % % In the following diagram A & D form one, as % % A = A057505(C) & C = A057506(A) % (or A = A057506(C) & C = A057505(A)) % % and also B & D form one, as similarly: % % B = A057505(D) & D = A057506(B) % (or B = A057506(D) & D = A057505(B)) % % Note that both fl and dr are involutions, and the % former fixes only symmetric binary trees, while % the latter fixes only symmetric general trees, % and they never fix the same tree (for sizes > 1). % From lemma 1 it's also immediately obvious that % A != C, and B != D (for sizes > 1). % % A <-- fl --> B % % ^ ^ % | | % dr dr % | | % V V % % D <-- fl --> C % % Case A = B but C != D leads to contradiction, as % then we would have C = a057164(B) = a057164(A) = D. % The same contradiction occurs respectively in the % case C = D but A != B. % % Similarly, if A = D, but B != C % (or respectively, B = C, but A != D) % leads to a contradiction, as then we would have % B = a057163(A) = a057163(D) = C % % The case where A=B and C=D, i.e. two distinct symmetric % binary trees were changed to each other with dr, % is excluded by lemma 2. % % So we are left with the fact that % A != B and C != D % and % if A is (not) equal to D then B must also be (not) equal to C. % % We want to know what is the condition for that % we get back to the same tree after one round in % above diagram, i.e. that % A = a057164(a057163(a057164(a057163(A)))) = a057163(a057164(a057163(a057164(A)))) % % This condition is equivalent to condition: % a057164(A) = a057163(a057164(a057163(A))) % % The composition fl o dr o fl (A057163 o A057164 o A057163) % is the gatomorphism A069787, called % "car/cdr-flipped conjugate of deep reverse". % % It works exactly like dr, except in mirrored fashion. % In the diagrams below, we call it rd. A^ stands for a057164(A). % % () A rd () A^ % \/ --> \/ % % () B rd () A^ % \/ A --> \/ B^ % \/ \/ % % () C rd () A^ % \/ B --> \/ B^ % \/ A \/ C^ % \/ \/ % % et cetera. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % On what condition rd(T) = a057164(T) ? % % If the tree is of the general form, we have: % % % () U V () L~() % \ / \/ \/ % . . dr . % L R ----> . % . . V~ . % \/ \/ % % | % | rd % | % V % % % () R^ % \/ % . % . % . U^ % \/ % % Where L and R indicate the WHOLE left & right hand side % subtrees of the original tree. % Now the balance changes in these two operations as: % % wt(L)|wt(R) ---DR---> wt(V)|(wt(R)+wt(L)-wt(V)) % ---RD---> wt(L)+wt(R)-wt(U)|wt(U) % % and equating the left (or right) hand sides % we get in both cases the equation: % % wt(U)+wt(V) = wt(L)+wt(R) % % which clearly is impossible, because % wt(U) < wt(L) and wt(V) < wt(R). % (A part is smaller than the whole). % % Thus if rd(T) = a057164(T), then either the right % hand side of the binary tree must be () (i.e. it's % degree=1 general tree) or the left hand side % of the binary tree must be () (i.e. it's a general % tree whose leftmost branch is \). % % Lemma 3: % % a057164(T) = rd(T) if and only if a057164(T)=T and rd(T)=T. % % Proof: % % (To be done. A sketch follows.) % Maybe the binary trees could be drawn into a square lattice % with each node that fits into a square adding its weight by % by the weight of the whole subtree (leaves included), % (Note that we have possibly more than one nodes positioned into % the same square from the different overlapping branches, % the square with weight 2 (or any even weight) in the diagram below): % % \/ _ _ _ _ % \/ |1|_|1|_| % \/\/ |3|2|3|1| % \/ ---> |B|7|5|1| % % (45 degrees clockwise) % (where B = 11) % % And then dr induces only such changes that % the row sums of the diagram stay intact, % in contrast to rd, which leaves column sums % intact. Then we just need to prove that % the corresponding diagrams can be same % only when neither of the operations do not % change them. % Maybe there are better intepretations in the % Catalan family for this? (Young tableaux???) % % % After having proved this, I will turn to the condition % when are such trees (for which a057164(T) = rd(T) = T) % primitive zig-zag trees. (Implemented by the Prolog-word % extend above.) To be continued... (28. January 2003) % % % general trees with n edges tpt-isomorphic subset amongst % (i.e. binary trees with 2n+1 nodes, the 2n+1 edge general trees % or 2n edges). % % cycle lengths How many invocations How many invocations of A057505 (RF) % of A071661 (RF^2) needed to go around? % needed to go around = 3* How many invocations of A071663 % the cycle? (RF^3) needed to go around the cycle? % (i.e. the size of the RF-cycle % where an isomorphic tpt-tree must be) % % cl (= cl/gcd(cl,2)) (3 * (cl/gcd(cl,2))) if cl divisible by 2 or 3 % otherwise (cl/gcd(cl,2)) % % 2 1 3 % 3 3 9 % 4 2 6 % 5 5 5 or 15 also? (5/gcd(5,3) = 5) % 6 3 9 % 7 7 7 % 8 4 12 or 4 as 4/gcd(4,3) = 4 and 12/gcd(12,3) = 4. % 9 9 27 % 10 5 15 % 11 11 11 % 12 6 18 % 13 13 13 % 14 7 21 % 15 15 45 % % 35 35 35 % % etc. % % No, Yes!: the condition should be that if there's a cycle of length % X among n edge trees, then there should be at least one % cycle of some length Y among 2n+1 edge trees, where the % following holds: X/gcd(X,2) = Y/gcd(Y,3) [Note the symmetry!] % % Note that for a given X there can be more than one solution for Y: % e.g. % 2/gcd(2,2) = 1 = 3/gcd(3,3) % 3/gcd(3,2) = 3 = 9/gcd(9,3) % 4/gcd(4,2) = 2 = 2/gcd(2,3) = 6/gcd(6,3) % 5/gcd(5,2) = 5 = 5/gcd(5,3) = 15/gcd(15,3) % 6/gcd(6,2) = 3 = 9/gcd(9,3) % 8/gcd(8,2) = 4 = 4/gcd(4,3) = 12/gcd(12,3) % 9/gcd(9,2) = 9 = 27/gcd(27,3) % 10/gcd(10,2) = 5 = 5/gcd(5,3) = 15/gcd(15,3) % 12/gcd(12,2) = 6 = 18/gcd(18,3) % % (Fortunately, we don't need to consider 1-cycles at the right side, % because they are absent). %