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 A072797 #34 Mar 30 2024 17:21:54 %S A072797 0,1,2,3,4,5,7,6,8,9,10,11,12,13,17,18,16,14,15,20,19,21,22,23,24,25, %T A072797 26,27,28,29,30,31,32,33,34,35,36,45,46,48,49,50,44,47,42,37,38,43,39, %U A072797 40,41,54,55,53,51,52,57,56,58,59,61,60,62,63,64,65,66,67,68,69,70,71 %N A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details. %C A072797 This bijection 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 A072797 A B A C %C A072797 \ / \ / %C A072797 x C --> x B () A () A %C A072797 \ / \ / \ / --> \ / %C A072797 x x x x %C A072797 ((a . b) . c) --> ((a . c) . b) (() . a) ---> (() . a) %C A072797 See the example for an explanation of how to obtain a given integer sequence from this definition. %C A072797 Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - _Antti Karttunen_, Jan 14 2024 %H A072797 A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a> %H A072797 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a> %F A072797 a(n) = A057163(A072796(A057163(n))). %e A072797 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 A072797 . %e A072797 one tree of one internal %e A072797 empty tree (non-leaf) node %e A072797 x \/ %e A072797 n= 0 1 %e A072797 a(n)= 0 1 (both are always fixed) %e A072797 . %e A072797 the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are: %e A072797 . %e A072797 \/ \/ \/ \/ %e A072797 \/ \/ \/ \/ \/ \/ \/ \/ %e A072797 \/ \/ \/ \/ \_/ \/ \/ %e A072797 n= 2 3 4 5 6 7 8 %e A072797 . %e A072797 and the new shapes after swapping the two subtrees in positions marked "B" and "C" in the diagram given in the comments are: %e A072797 . %e A072797 \/ \/ \/ \/ %e A072797 \/ \/ \/ \/ \/ \/ \/ \/ %e A072797 \/ \/ \/ \/ \/ \_/ \/ %e A072797 a(n)= 2 3 4 5 7 6 8 %e A072797 thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8. %o A072797 (Scheme function implementing this automorphism on list-structures/S-expressions, both constructive (*A072797) and destructive (*A072797!) version:) %o A072797 (define (*A072797 s) (if (and (pair? s) (pair? (car s))) (cons (cons (caar s) (cdr s)) (cdar s)) s)) %o A072797 (define (*A072797! s) (cond ((not (pair? s)) s) ((not (pair? (car s))) s) (else (swap! s) (robl! s) (swap! (car s)) s))) %o A072797 (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 A072797 (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s)) %Y A072797 Row 8 of A089840. %Y A072797 Cf. A014486, A057163, A072796, A127301, A129593. %Y A072797 Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191. %K A072797 nonn %O A072797 0,3 %A A072797 _Antti Karttunen_, Jun 12 2002 %E A072797 Further comments added by _Antti Karttunen_, Jun 04 2011 and Mar 30 2024