EDITS of 7 SEQUENCES: A069770, A074679, A074680, A089840, A122200, A122201, A122202

%I A069770
%S A069770 0,1,3,2,7,8,6,4,5,17,18,20,21,22,16,19,14,9,10,15,11,12,13,45,46,48,
%T A069770 49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,42,51,37,23,24,38,25,
%U A069770 26,27,43,52,39,28,29,40,30,31,32,41,33,34,35,36,129,130,132,133,134
%N A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top-branches of a binary tree. An involution of non-negative integers.
%C A069770 This is the simplest possible Catalan automorphism after the identity automorphism *A001477. It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those nodes):
%C A069770 .A...B....-->....B...A.
%C A069770 ..\./.............\./..
%C A069770 ...x...............x...
%C A069770 (a . b) ------> (b . a)
%e A069770 To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486, and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
%e A069770 ...................one tree of one internal.
%e A069770 ..empty tree.........(non-leaf) node........
%e A069770 ............................................
%e A069770 ......x......................\/.............
%e A069770 n=....0......................1..............
%e A069770 a(n)=.0......................1.............. (both are always fixed)
%e A069770 the next 7 trees, with with 2-3 internal nodes, in range [A014137(1), A014138(2)] = [2,8] change as follows:
%e A069770 ..........................\/.....\/.................\/.....\/...
%e A069770 .......\/.....\/.........\/.......\/.....\/.\/.....\/.......\/..
%e A069770 ......\/.......\/.......\/.......\/.......\_/.......\/.......\/.
%e A069770 n=.....2........3........4........5........6........7........8..
%e A069770 ..............................|.................................
%e A069770 ..............................|.................................
%e A069770 ..............................V.................................
%e A069770 ................................................................
%e A069770 ........................\/.....\/.....................\/.....\/.
%e A069770 .....\/.........\/.....\/... ...\/.......\/.\/.......\/.......\/
%e A069770 ......\/.......\/.......\/.......\/.......\_/.......\/.......\/.
%e A069770 a(n)=..3........2........7........8........6........4........5..
%e A069770 thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.
%D A069770 A. Karttunen, paper in preparation, draft available by e-mail.
%H A069770 A. Karttunen, <a href="http://www.research.att.com/~njas/sequences/b069770.txt">Table of n, a(n) for n = 0..2055</a>
%H A069770 A. Karttunen, <A HREF="http://www.research.att.com/~njas/sequences/A089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</A>
%H A069770 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%Y A069770 Row 1 of A089840. a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).
%Y A069770 The number of cycles (A007595) and the number of fixed points (A000108 interleaved with zeros) in range [A014137(n-1)..A014138(n-1)] of this permutation are given by the same sequences as for the following recursive derivations of this automorphism: *A057163 and *A122351.
%Y A069770 Other related sequences: A069767, A069768, A089864, A123492.
%Y A069770 Adjacent sequences: A069767 A069768 A069769 this_sequence A069771 A069772 A069773
%Y A069770 Sequence in context: A057161 A089862 A122326 this_sequence A082345 A122327 A122328
%K A069770 nonn
%O A069770 0,3
%A A069770 Antti Karttunen Apr 16 2002. Entry revised Oct 11 2006.
%o A069770 (Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
%o A069770 (CONSTRUCTIVE VERSION:) (define (*A069770 s) (if (pair? s) (cons (cdr s) (car s)) s))
%o A069770 (DESTRUCTIVE VERSION:) (define (*A069770! s) (if (pair? s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car))) s)




%I A074679
%S A074679 0,1,3,2,6,7,8,4,5,14,15,16,17,18,19,20,21,9,10,22,11,12,13,37,38,39,
%T A074679 40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,23,24,59,25,
%U A074679 26,27,60,61,62,28,29,63,30,31,32,64,33,34,35,36,107,108,109,110,111
%N A074679 Signature permutation of the twelfth nonrecursive Catalan automorphism in table A089840. (Rotate binary tree left if possible, otherwise swap its sides.)
%C A074679 This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes, and () stands for an implied terminal node.)
%C A074679 ...B...C.......A...B
%C A074679 ....\./.........\./
%C A074679 .A...x....-->....x...C.................A..().........()..A..
%C A074679 ..\./.............\./...................\./....-->....\./...
%C A074679 ...x...............x.....................x.............x....
%C A074679 (a . (b . c)) -> ((a . b) . c) ______ (a . ()) --> (() . a)
%C A074679 That is, we rotate the binary tree left, in case it is possible, and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e. apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
%C A074679 This is the first multiclause nonrecursive automorphism in table A089840, and the first one whose order is not finite, i.e. the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n-1)] of this permutation is given by A001683(n+1), i.e. the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. This is true because this automorphism traces "step-by-step" the rotation of Eulerian polygon triangulations effected by the latter automorphisms, but in one node larger context.
%D A074679 A. Karttunen, paper in preparation, draft available by e-mail.
%H A074679 A. Karttunen, <a href="http://www.research.att.com/~njas/sequences/b074679.txt">Table of n, a(n) for n = 0..2055</a>
%H A074679 A. Karttunen, <A HREF="http://www.research.att.com/~njas/sequences/A089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</A>
%H A074679 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%Y A074679 This automorphism has several variants, where the first clause is same (rotate binary tree to the left, if possible), but something else is done (than just swapping sides), in case the right hand side is empty: A082335, A082349, A123499, A123695. The following automorphisms can be derived recursively from this one: A057502, A074681, A074683, A074685, A074687, A074690, A089865, A120706, A122321, A122332. See also somewhat similar ones: A069773, A071660, A071656, A071658, A072091, A072095, A072093.
%Y A074679 Inverse: A074680. Row 12 of A089840. Occurs also in A073200 as row 557243 as a(n) = A073283(A073280(A072796(n))). a(n) = A083927(A123498(A057123(n))).
%Y A074679 Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n-1)] of this permutation).
%Y A074679 Sequence in context: A006042 A100280 A092745 this_sequence A072091 A074687 A082349
%Y A074679 Adjacent sequences: A074676 A074677 A074678 this_sequence A074680 A074681 A074682
%K A074679 nonn
%O A074679 0,3
%o A074679 (Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
%o A074679 (CONSTRUCTIVE VERSION:) (define (*A074679 s) (cond ((not (pair? s)) s) ((pair? (cdr s)) (cons (cons (car s) (cadr s)) (cddr s))) (else (cons (cdr s) (car s)))))
%o A074679 (DESTRUCTIVE VERSION:) (define (*A074679! s) (cond ((pair? s) (cond ((pair? (cdr s)) (robl! s)) (else (swap! s))))) s)
%o A074679 (define (robl! s) (let ((ex-car (car s))) (set-car! s (cddr s)) (set-cdr! (cdr s) ex-car) (swap! (cdr s)) (swap! s) s))
%o A074679 (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
%A A074679 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 11 2002, description clarified Oct 10 2006.


%I A074680
%S A074680 0,1,3,2,7,8,4,5,6,17,18,20,21,22,9,10,11,12,13,14,15,16,19,45,46,48,
%T A074680 49,50,54,55,57,58,59,61,62,63,64,23,24,25,26,27,28,29,30,31,32,33,34,
%U A074680 35,36,37,38,39,40,41,42,43,44,47,51,52,53,56,60,129,130,132,133,134
%N A074680 Signature permutation of the seventeenth nonrecursive Catalan automorphism in table A089840. (Rotate binary tree right if possible, otherwise swap its sides.)
%C A074680 This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes, and () stands for an implied terminal node.)
%C A074680 A...B..............B...C
%C A074680 .\./................\./
%C A074680 ..x...C..-->.....A...x................()..B.......B..()
%C A074680 ...\./............\./..................\./...-->...\./.
%C A074680 ....x..............x....................x...........x..
%C A074680 ((a . b) . c) -> (a . (b . c)) ____ (() . b) --> (b . ())
%C A074680 That is, we rotate the binary tree right, in case it is possible, and otherwise (if the left hand side of a tree is a terminal node) swap the right and left subtree (so that the terminal node ends to the right hand side), i.e. apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
%C A074680 See also the comments at A074679.
%D A074680 A. Karttunen, paper in preparation, draft available by e-mail.
%H A074680 A. Karttunen, <a href="http://www.research.att.com/~njas/sequences/b074680.txt">Table of n, a(n) for n = 0..2055</a>
%H A074680 A. Karttunen, <A HREF="http://www.research.att.com/~njas/sequences/A089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</A>
%H A074680 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%Y A074680 This automorphism has several variants, where the first clause is same (rotate binary tree to the right, if possible), but something else is done (than just swapping sides), in case the left hand side is empty: A082336, A082350, A123500, A123696. The following automorphisms can be derived recursively from this one: A057501, A074682, A074684, A074686, A074688, A074689, A089866, A120705, A122322, A122331. See also somewhat similar ones: A069774, A071659, A071655, A071657, A072090, A072094, A072092.
%Y A074680 Inverse: A074679. Row 17 of A089840. Occurs also in A073200 as row 2156396687 as a(n) = A072796(A073280(A073282(n))). a(n) = A083927(A123497(A057123(n))).
%Y A074680 Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n-1)] of this permutation).
%Y A074680 Sequence in context: A016603 A095353 A054183 this_sequence A072090 A074688 A069774
%Y A074680 Adjacent sequences: A074677 A074678 A074679 this_sequence A074681 A074682 A074683
%K A074680 nonn
%O A074680 0,3
%o A074680 (Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
%o A074680 (CONSTRUCTIVE VERSION:) (define (*A074680 s) (cond ((not (pair? s)) s) ((pair? (car s)) (cons (caar s) (cons (cdar s) (cdr s)))) (else (cons (cdr s) (car s)))))
%o A074680 (DESTRUCTIVE VERSION:) (define (*A074680! s) (cond ((pair? s) (cond ((pair? (car s)) (robr! s)) (else (swap! s))))) s)
%o A074680 (define (robr! s) (let ((ex-cdr (cdr s))) (set-cdr! s (caar s)) (set-car! (car s) ex-cdr) (swap! (car s)) (swap! s) s))
%o A074680 (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
%A A074680 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 11 2002, description clarified Oct 10 2006.


%I A089840
%S A089840 0,1,0,2,1,0,3,3,1,0,4,2,2,1,0,5,7,3,2,1,0,6,8,4,3,2,1,0,7,6,6,5,3,2,1,
%T A089840 0,8,4,5,4,5,3,2,1,0,9,5,7,6,6,6,3,2,1,0,10,17,8,7,4,5,6,3,2,1,0,11,18,
%U A089840 9,8,7,4,4,4,3,2,1,0,12,20,10,12,8,7,5,5,4,3,2,1,0,13,21,14,13,12,8,7,6
%N A089840 Signature permutations of non-recursive Catalan automorphisms, sorted according to the minimum number of opening nodes needed in their defining clauses.
%C A089840 Each row is a permutation of natural numbers and occurs only once. The table is closed with regards to the composition of its rows (see A089839) and it contains the inverse of each (their positions are shown in A089843). The permutations in table form an enumerable subgroup of the group of all "Catalan automorphisms" (automorphisms of finite unlabeled rooted plane binary trees). The order of each element is shown at A089842.
%D A089840 A. Karttunen, paper in preparation, draft available by e-mail.
%H A089840 A. Karttunen, <A HREF="http://www.research.att.com/~njas/sequences/a089839.c.txt">C-program for computing the terms of this table. Defines also the order of rows.</A>
%H A089840 A. Karttunen, <A HREF="http://www.research.att.com/~njas/sequences/A089840p.txt">Prolog-program which illustrates the construction of each row</A>
%Y A089840 The first 22 rows of this table: Row 0 (identity permutation): A001477, 1: A069770, 2: A072796, 3: A089850, 4: A089851, 5: A089852, 6: A089853, 7: A089854, 8: A072797, 9: A089855, 10: A089856, 11: A089857, 12: A074679, 13: A089858, 14: A073269, 15: A089859, 16: A089860, 17: A074680, 18: A089861, 19: A073270, 20: A089862, 21: A089863.
%Y A089840 Other rows: row 253: A123503, row 258: A123499, row 264: A123500, row 3702: A082354, row 3886: A082353, row 4069: A082351, row 4207: A089865, row 4253: A082352, row 4299: A089866, row 65518: A123495, row 65796: A123496, row 79361: A123492, row 1653002: A123695, row 1653063: A123696, row 1654023: A073281, row 1654249: A123498, row 1654694: A089864, row 1655089: A123497, row 1783367: A123713, row 1786785: A123714.
%Y A089840 Tables A122200, A122201, A122202, A122203, A122204, A122283, A122284, A122285, A122286, A122287, A122288, A122289, A122290 give various "recursive derivations" of these non-recursive automorphisms. See also A089831, A073200.
%Y A089840 Adjacent sequences: A089837 A089838 A089839 this_sequence A089841 A089842 A089843
%Y A089840 Sequence in context: A103432 A103448 A078803 this_sequence A122289 A122290 A122284
%K A089840 nonn,tabl
%O A089840 0,4
%A A089840 Antti Karttunen (His_Firstname.His_Surname(AT)gmail.com), Dec 05 2003


%I A122200
%S A122200 0,1,0,2,1,0,3,2,1,0,4,3,2,1,0,5,4,3,2,1,0,6,5,4,3,2,1,0,7,6,5,4,3,2,
%T A122200 1,0,8,8,6,5,4,3,2,1,0,9,7,7,6,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,11,
%U A122200 10,9,8,7,6,5,4,3,2,1,0,12,11,10,9,8,7,6,5,4,3,2,1,0,13,13,11,10,9,8
%N A122200 Signature permutations of RIBS-transformations of non-recursive Catalan automorphisms in table A089840.
%C A122200 Row n is the signature permutation of the Catalan automorphism which is obtained from the nth nonrecursive automorphism in the table A089840 with the recursion scheme "RIBS". In this recursion scheme the given automorphism is applied to all (toplevel) subtrees of the Catalan structure, when it is interpreted as a general tree. Permutations in this table form a countable group, which is isomorphic with the group in A089840. (The RIBS transformation gives the group isomorphism.) Furthermore, row n of this table is also found as the row A123694(n) in tables A122203 and A122204. If the count of fixed points of the automorphism A089840[n] is given by sequence f, then the count of fixed points of the automorphism A089840[A123694(n)] is given by CONV(f,A000108) (where CONV stands for convolution), and the count of fixed points of the automorphism A122200[n] by INVERT(RIGHT(f)). The associated Scheme-procedures RIBS and !RIBS can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism.
%D A122200 A. Karttunen, paper in preparation, draft available by e-mail.
%H A122200 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%o A122200 (Scheme) (define (RIBS foo) (lambda (s) (map foo s)))
%o A122200 (define (!RIBS foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! (car s)) (bar! (cdr s)))) s))) bar!))
%Y A122200 Row 0 (identity permutation): A001477, row 1: A122282. See also tables A089840, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.
%Y A122200 Adjacent sequences: A122197 A122198 A122199 this_sequence A122201 A122202 A122203
%Y A122200 Sequence in context: A025677 A025651 A025670 this_sequence A025646 A025661 A025671
%K A122200 nonn,tabl
%O A122200 0,4
%A A122200 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 01 2006


%I A122201
%S A122201 0,1,0,2,1,0,3,3,1,0,4,2,2,1,0,5,8,3,2,1,0,6,7,4,3,2,1,0,7,6,6,5,3,2,
%T A122201 1,0,8,5,5,4,5,3,2,1,0,9,4,7,6,6,6,3,2,1,0,10,22,8,7,4,5,6,3,2,1,0,11,
%U A122201 21,9,8,7,4,4,4,3,2,1,0,12,20,11,12,8,7,5,5,4,3,2,1,0,13,18,14,13,12
%N A122201 Signature permutations of FORK-transformations of non-recursive Catalan automorphisms in table A089840.
%C A122201 Row n is the signature permutation of the Catalan automorphism which is obtained from the nth nonrecursive automorphism in the table A089840 with the recursion scheme "FORK". In this recursion scheme the given automorphism is first applied at the root of binary tree, before the algorithm recurses down to the both branches (new ones, possibly changed by the given automorphism). I.e. this corresponds to the pre-order (prefix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures FORK and !FORK can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122202.
%D A122201 A. Karttunen, paper in preparation, draft available by e-mail.
%H A122201 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%o A122201 (Scheme:) (define (FORK foo) (letrec ((bar (lambda (s) (let ((t (foo s))) (if (pair? t) (cons (bar (car t)) (bar (cdr t))) t))))) bar))
%o A122201 (define (!FORK foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! s) (bar! (car s)) (bar! (cdr s)))) s))) bar!))
%Y A122201 The first 22 rows of this table: Row 0 (identity permutation): A001477, 1: A057163, 2: A057511, 3: A122341, 4: A122343, 5: A122345, 6: A122347, 7: A122349, 8: A082325, 9: A082360, 10: A122291, 11: A122293, 12: A074681, 13: A122295, 14: A122297, 15: A122353, 16: A122355, 17: A074684, 18: A122357, 19: A122359, 20: A122361, 21: A122301. Other rows: row 4253: A082356, row 65796: A082358, row 79361: A123493.
%Y A122201 See also tables A089840, A122200, A122202-A122204, A122283-A122284, A122285-A122288, A122289-A122290.
%Y A122201 Adjacent sequences: A122198 A122199 A122200 this_sequence A122202 A122203 A122204
%Y A122201 Sequence in context: A122283 A122204 A122288 this_sequence A122286 A122202 A122285
%K A122201 nonn,tabl
%O A122201 0,4
%A A122201 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 01 2006

%I A122202
%S A122202 0,1,0,2,1,0,3,3,1,0,4,2,2,1,0,5,8,3,2,1,0,6,7,4,3,2,1,0,7,6,6,5,3,2,
%T A122202 1,0,8,5,5,4,5,3,2,1,0,9,4,7,6,6,6,3,2,1,0,10,22,8,7,4,5,6,3,2,1,0,11,
%U A122202 21,9,8,7,4,4,4,3,2,1,0,12,20,14,13,8,7,5,5,4,3,2,1,0,13,18,10,12,13
%N A122202 Signature permutations of KROF-transformations of non-recursive Catalan automorphisms in table A089840.
%C A122202 Row n is the signature permutation of the Catalan automorphism which is obtained from the nth nonrecursive automorphism in the table A089840 with the recursion scheme "KROF". In this recursion scheme the algorithm first recurses down to the both branches, before the given automorphism is applied at the root of binary tree. I.e. this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures KROF and !KROF can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122201.
%D A122202 A. Karttunen, paper in preparation, draft available by e-mail.
%H A122202 <A HREF="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</A>
%o A122202 (MIT Scheme:) (define (KROF foo) (letrec ((bar (lambda (s) (fold-right (lambda (x y) (foo (cons (bar x) y))) '() s)))) bar))
%o A122202 (define (!KROF foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (bar! (car s)) (bar! (cdr s)) (foo! s))) s))) bar!))
%Y A122202 The first 22 rows of this table: Row 0 (identity permutation): A001477, 1: A057163, 2: A057512, 3: A122342, 4: A122348, 5: A122346, 6: A122344, 7: A122350, 8: A082326, 9: A122294, 10: A122292, 11: A082359, 12: A074683, 13: A122358, 14: A122360, 15: A122302, 16: A122362, 17: A074682, 18: A122296, 19: A122298, 20: A122356, 21: A122354. Other rows: row 4069: A082355, row 65518: A082357, row 79361: A123494.
%Y A122202 See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.
%Y A122202 Adjacent sequences: A122199 A122200 A122201 this_sequence A122203 A122204 A122205
%Y A122202 Sequence in context: A122288 A122201 A122286 this_sequence A122285 A100224 A089000
%K A122202 nonn,tabl
%O A122202 0,4
%A A122202 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 01 2006