This site is supported by donations to The OEIS Foundation.

# User:Antti Karttunen/Speculations/On the fixed points of A071661

*This is another page in my series of speculations/proofs in making. This intends to be a clean-up of http://www.iki.fi/kartturi/matikka/Nekomorphisms/About_A126312.htm, which was written 2003 and revised 2006.*

## Contents

## Pre-notes

The lemma 0 below was pointed to me by Wouter Meeussen (in slightly more specific terms), and also, that it is a special case of Garsia-Milne involution principle.

This is concerned with the sequences A126312, A080070 (see especially the associated illustrations) and A123050.

Donald Knuth, in his Pre-Fascicle 4a: Generating All Trees^{[1]} (which I don't recall reading until much later than 2003, in any case, I didn't know about it when I submitted A079438 and A080070), asks in section 7.2.1.6., in Exercise 11 (on page 31):

If

Fis a forest, itsconjugateFis obtained by left-to-right mirror reflection.^{R}

(that is, ** dr**,
i.e. *A057164 in our notation), and in exercise 12 (on the same page):

If

Fis a forest, itstransposeFis the forest whose binary tree is obtained by interchanging left and right links in the binary tree representing^{T}F.

(that is, ** fl**,
i.e. *A057163 in our notation), and in exercise 12 (on the same page):

and in Exercise 14 (on page 32):

Find all labeled forests

Fsuch thatF.^{RT}= F^{TR}

and in exercise 17 (on the same page):

Characterize all

unlabeledforestsFsuch thatF. (See exercise 14.)^{RT}= F^{TR}

and in answer to Exercise 17 on page 48, that:

It appears to be true that we cannot have

Funless^{RT}= F^{TR}F = F. Under that assumption,^{R}Fif and only if^{RT}= F^{TR}FandFare both self-conjugate.^{R}David Callan has discovered two infinite families of such forests, with parameters

i, j, k >= 0.

(trees not depicted here, but the two smaller trees can be found also on the top of page 11 of my drawing from January 24 2003: http://oies.org/a079438.pdf, and the first specimens of another family can be found at the top of page 18. -- AK)

...

Knuth then asks:Are there any other cases?

I.e. in my notation, as **rd** **=** **fl** **o** **dr** **o** **fl** (A069787 = A057163 o A057164 o A057163)
the condition *dr(T)* = *rd(T)* means the
same thing as Knuth's *F ^{RT} = F^{TR}*.

Knuths "...if and only if *F* and *F ^{R}* are both
self-conjugate."
means that

*F*is symmetric (with respect to A057164), i.e.

*F = F*, in our notation

^{R}*dr(T)*=

*dr(T)*.

## Determining the fixed points of A071661

% % Few lemmas & conjectures concerning the Catalan bijection 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/ % revised Jun 12 2006. % % 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'). % % fl implements the reflection of plane binary trees (A057163): % (fl stands for flip) fl([],[]). fl([L1|R1],[L2|R2]) :- fl(L1,R2), fl(R1,L2). % dr implements the reflection of plane general trees (A057164): % (dr stands for deepreverse) % Note the double usage possible in Prolog: % In predicate extend we use dr(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 dr(T,T) to CHECK that the instantiated % variable T contains a symmetric parenthesization/general tree. dr([],[]). dr([L1|R1],Z) :- dr(L1,L2), dr(R1,R2), append(R2,[L2],Z). % % 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]) :- dr(L,R), fl([R],T), dr(T,T). extend(L,[T|[R]]) :- dr(L,R), fl([R],L2), extend(L2,FT), fl(FT,T), dr(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 fl(t) != dr(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 fl (A057163), and A~, B~ the same % subtrees recursively deep-reversed with dr (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 fl flips (reflects) the underlying binary tree of % the general tree: % % A B B' A' % \/ --> \/ % % Automorphism dr 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 () dr A~() % \/ --> \/ % % | fl % v % Here the results are equivalent only in % () A' the trivial case A = (). % \/ % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % B () dr A~() % A \/ --> B~\/ % \/ \/ % % | fl % 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~\/ % \/ \/ % % | fl % 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 dr(T) is NOT symmetric as a binary tree. % (which implies that ??? or regardless whether dr(T) = T or dr(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 & C form a 2-cycle, as % % A = A057505(C) & C = A057506(A) % (or A = A057506(C) & C = A057505(A)) % % and also B & D form a 2-cycle, 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 = dr(B) = dr(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 = fl(A) = fl(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 = dr(fl(dr(fl(A)))) = fl(dr(fl(dr(A)))) % % This condition is equivalent to condition: % dr(A) = fl(dr(fl(A))) % % The composition fl o dr o fl (A057163 o A057164 o A057163) % is the Catalan bijection 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 rd(A). % % () A rd () A^ % \/ --> \/ % % () B rd () A^ % \/ A --> \/ B^ % \/ \/ % % () C rd () A^ % \/ B --> \/ B^ % \/ A \/ C^ % \/ \/ % % et cetera. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % On what condition rd(T) = dr(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) = dr(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 \). The latter implies % that the rightmost branch is also empty (/), because % by symmetry, everything that is stated about the node A % in the above diagram can be also stated about the node D, % and also stated about the node D in the mirror image fashion. % (which in turn can be stated about the node A as well). % [MUOTOILE PAREMMIN!] % % % % () () () () % W \/ \/ % \. dr W~ . % D ----> \D~ % () . () . % \/ \/ % % | % | rd % | % V % % % D^ % () . % \/ % % Now, examining the balance of the right hand subtree of D in the same way % (again divided to the L & R halves, W is the penultimate branch of D, % if there's more than three branches total). % % () U () () () () % \ / W \/ L~\/ % . \. dr \. % L R ----> . % . . W~ . % \/ \/ % % | % | rd % | % V % % % () R^ % \/ % . % . % . U^ % \/ % % wt(L)|wt(R) ---DR---> wt(W)|(wt(R)+wt(L)-wt(W)) % ---RD---> wt(L)+wt(R)-wt(U)|wt(U) % % Again, the left hand side subtree of R should be (), % or there are only one top-level (gen tree) branch in R, the (). % In the latter case the equation turns out as: % wt(L)|wt(1) ---DR---> wt(L)|(1) % ---RD---> wt(L)+(1)-wt(U)|wt(U) % % Thus wt(U) = 1 and U = (() . ()) % % () U % \ / % . dr % L () () ----> () () % . \/ L~\/ % \/ \/ % % | % | rd % | % V % % % () () % \/ % . % . % . U^ % \/ % Lemma XXX: % % I DON'T THINK THIS APPROACH WILL WORK, AS THERE ARE FOR EXAMPLE % TREES WITH LUKASIEWICZ-WORD 3130100010 WHICH, WHEN SUBJECTED % TO A069787 (rd) WILL HAVE A L-WORD 3130010100, WHICH HAS % THE SAME LEVEL SUMS AS [3,2,3,1,0]. % % % dr(T) = rd(T) if and only if dr(T)=T and rd(T)=T. %

.. and on and on and on. The latter part of the attempted proof doesn't seem to be going nowhere. Instead, it is solved by the simple fact that **dr** (that is *A057164) belongs to those bijections that preserve A127301, i.e. that A127301(A057164(n)) = A127301(n) for all n, because the deep-reverse preserves the general tree's non-oriented form.
In contrast, it should be quite easy to see that for **rd**, i.e. *A069787, only time when A127301(A069787(n)) = A127301(n), is when A069787(n)=n, that is, when it fixes n.
And this I discovered just today, Aug 23 2012, when I started to rethink this old problem.
(It's a pity that I didn't invent/discover A127301 until 2007...)

## Correspondence between the cycle lengths of A057505 and A071661

I recall that the following correspondence is based on the equivalences

and

but I don't really recall, whether they are really proved in Donaghey's paper^{[2]} or not.
So, so far, take everything with a pinch of salt.

% % 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) % % 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). %

## References

- ↑ Donald Knuth,
*Pre-Fascicle 4a: Generating All Trees*, http://www-cs-staff.stanford.edu/~knuth/fasc4a.ps.gz - ↑ R. Donaghey,
*Automorphisms on Catalan trees and bracketing*, J. Combin. Theory, Series B,**29**(1980), 75-90.