This site is supported by donations to The OEIS Foundation.
User:Antti Karttunen/Speculations/On the fixed points of A071661
From OeisWiki
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 F is a forest, its conjugate FR is obtained by left-to-right mirror reflection.
(that is, dr, i.e. *A057164 in our notation), and in exercise 12 (on the same page):
If F is a forest, its transpose FT is the forest whose binary tree is obtained by interchanging left and right links in the binary tree representing 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 F such that FRT = FTR.
and in exercise 17 (on the same page):
Characterize all unlabeled forests F such that FRT = FTR. (See exercise 14.)
and in answer to Exercise 17 on page 48, that:
It appears to be true that we cannot have FRT = FTR unless F = FR. Under that assumption, FRT = FTR if and only if F and FR are both self-conjugate.
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 FRT = FTR.
Knuths "...if and only if F and FR are both self-conjugate." means that F is symmetric (with respect to A057164), i.e. F = FR, in our notation 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.
