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 A072796 #42 Feb 04 2024 18:47:34 %S A072796 0,1,2,3,4,6,5,7,8,9,10,14,16,19,11,15,12,17,18,13,20,21,22,23,24,25, %T A072796 26,27,37,38,42,44,47,51,53,56,60,28,29,39,43,52,30,40,31,45,46,32,48, %U A072796 49,50,33,41,34,54,55,35,57,58,59,36,61,62,63,64,65,66,67,68,69,70,71 %N A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments. %C A072796 This bijection effects the following transformation on the unlabeled rooted plane general trees (letters A, B, C, etc. refer to arbitrary subtrees located on those vertices): %C A072796 A A A B B A A B C B A C %C A072796 | --> | \ / --> \ / \ | / --> \ | / %C A072796 | | \./ \./ \|/ \|/ etc. %C A072796 I.e., it keeps "planted" (root degree = 1) trees intact, and swaps the two leftmost toplevel subtrees of the general trees that have a root degree > 1. %C A072796 On the level of underlying binary trees that general trees map to (see, e.g., 1967 paper by N. G. De Bruijn and B. J. M. Morselt, or consider lists vs. dotted pairs in Lisp programming language), 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 A072796 B C A C %C A072796 \ / \ / %C A072796 A x --> B x A () A () %C A072796 \ / \ / \ / --> \ / %C A072796 x x x x %C A072796 (a . (b . c)) -> (b . (a . c)) (a . ()) ---> (a . ()) %C A072796 Note that the first clause corresponds to what is called "generator pi_0" in Thompson's group V. (See also A074679, A089851 and A154121 for other related generators.) %C A072796 Look at the example section to see how this will produce the given sequence of integers. %C A072796 Applying this permutation recursively down the right hand side branch of the binary trees (or equivalently, along the topmost level of the general trees) produces permutations A057509 and A057510 (that occur at the same index 2 in tables A122203 and A122204) that effect "shallow rotation" on general trees and parenthesizations. Applying it recursively down the both branches of binary trees (as in pre- or postorder traversal) produces A057511 and A057512 (that occur at the same index 2 in tables A122201 and A122201) that effect "deep rotation" on general trees and parenthesizations. %C A072796 For this permutation, A127301(a(n)) = A127301(n) for all n, which in turn implies A129593(a(n)) = A129593(n) for all n, likewise for all such recursively generated bijections as A057509 - A057512. Compare also to A072797. %H A072796 Antti Karttunen, <a href="/A072796/b072796.txt">Table of n, a(n) for n = 0..196</a> %H A072796 J. W. Cannon, W. J. Floyd, and W. R. Parry, <a href="https://web.archive.org/web/20110605062246/http://www.geom.uiuc.edu/docs/preprints/lib/GCG63/thompson.ps">Notes on Richard Thompson's Groups F and T</a> %H A072796 J. W. Cannon, W. J. Floyd, and W. R. Parry, <a href="https://doi.org/10.5169/seals-87877">Introductory notes on Richard Thompson's groups</a>, L'Enseignement Mathématique, Vol. 42 (1996), pp. 215-256. %H A072796 N. G. De Bruijn and B. J. M. Morselt, <a href="https://doi.org/10.1016/S0021-9800(67)80111-X">A note on plane trees</a>, J. Combinatorial Theory 2 (1967), 27-34. %H A072796 Antti Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a> %e A072796 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 A072796 . %e A072796 one tree of one internal %e A072796 empty tree (non-leaf) node %e A072796 x \/ %e A072796 n= 0 1 %e A072796 a(n)= 0 1 (both are always fixed) %e A072796 . %e A072796 the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are: %e A072796 . %e A072796 \/ \/ \/ \/ %e A072796 \/ \/ \/ \/ \/ \/ \/ \/ %e A072796 \/ \/ \/ \/ \_/ \/ \/ %e A072796 n= 2 3 4 5 6 7 8 %e A072796 . %e A072796 and the new shapes after swapping the two subtrees in positions marked "A" and "B" in the diagram given in the comments are: %e A072796 . %e A072796 \/ \/ \/ \/ %e A072796 \/ \/ \/ \/ \/ \/ \/ \/ %e A072796 \/ \/ \/ \_/ \/ \/ \/ %e A072796 a(n)= 2 3 4 6 5 7 5 %e A072796 thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 6, 5, 7, 8. %o A072796 (Scheme function implementing this automorphism on list-structures, both the constructive (*A072796) and destructive (*A072796!) variant given:) %o A072796 (define (*A072796 s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (cons (cadr s) (cons (car s) (cddr s)))))) %o A072796 (define (*A072796! s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (swap! s) (robr! s) (swap! (cdr s)) s))) %o A072796 (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 A072796 (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s)) %Y A072796 Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204. %Y A072796 Fixed point counts and cycle counts are given in A073190 and A073191. %Y A072796 Cf. A014486, A072797, A057509, A057510, A057511, A057512, A127301, A129593, A129608. %K A072796 nonn %O A072796 0,3 %A A072796 _Antti Karttunen_, Jun 12 2002 %E A072796 Comment section edited and Examples added by _Antti Karttunen_, Jan 26 2024