This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A069770 #25 Jul 09 2025 03:56:53 %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 nonnegative integers. %C A069770 This is the simplest possible Catalan automorphism after the identity bijection (A001477). It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those vectices): %C A069770 A B B A %C A069770 \ / --> \ / %C A069770 x x %C A069770 (a . b) -----> (b . a) %C A069770 Applying this permutation recursively to the right hand side branch of the binary trees produces permutations A069767 and A069768 (that occur at the same index 1 in tables A122203 and A122204), and applying this recursively to the both branches of binary trees (as in pre- or postorder traversal) produces A057163 (which occurs at the same index 1 in tables A122201 and A122202) that reflects the whole binary tree. %C A069770 For this permutation, A127302(a(n)) = A127302(n) for all n, [or equally, A153835(a(n)) = A153835(n)], and likewise for all such recursive derivations as mentioned above. %H A069770 A. Karttunen, <a href="/A069770/b069770.txt">Table of n, a(n) for n = 0..2055</a> %H A069770 A. Karttunen, <a href="/A089840/a089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</a> %H A069770 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a> %F A069770 a(n) = A154125(A154126(n)) = A154126(A154125(n)). %F A069770 a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))). %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 . %e A069770 one tree of one internal %e A069770 empty tree (non-leaf) node %e A069770 x \/ %e A069770 n= 0 1 %e A069770 a(n)= 0 1 (both are always fixed) %e A069770 . %e A069770 the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are: %e A069770 . %e A069770 \/ \/ \/ \/ %e A069770 \/ \/ \/ \/ \/ \/ \/ \/ %e A069770 \/ \/ \/ \/ \_/ \/ \/ %e A069770 n= 2 3 4 5 6 7 8 %e A069770 . %e A069770 and the new shapes after swapping their left and right hand subtrees are: %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. %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) %Y A069770 Row 1 of A089840. %Y A069770 The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331. %Y A069770 Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126. %Y A069770 Cf. also A127302, A153835. %K A069770 nonn %O A069770 0,3 %A A069770 _Antti Karttunen_, Apr 16 2002 %E A069770 Entry revised by _Antti Karttunen_, Oct 11 2006 and Mar 30 2024