%I
%S 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 26,27,37,38,42,44,47,51,53,56,60,28,29,39,43,52,30,40,31,45,46,32,48,
%U 49,50,33,41,34,54,55,35,57,58,59,36,61,62,63,64,65,66,67,68,69,70,71
%N Selfinverse permutation of natural numbers induced by Catalan Automorphism *A072796 acting on the parenthesizations encoded by A014486.
%C 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 ...B...C...........A...C
%C ....\./.............\./
%C .A...x....>....B...x.................A..().........A...()..
%C ..\./.............\./...................\./....>....\./...
%C ...x...............x.....................x.............x....
%C (a . (b . c)) > (b . (a . c)) ______ (a . ()) > (a . ())
%C In terms of general trees, it swaps the two leftmost branches of the tree if its degree (i.e. of the root) > 1 and keeps the tree intact if it is planted (root's degree = 1).
%C 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 Look at the example in A069770 to see how this will produce the given sequence of integers.
%D J. W. Cannon, W. J. Floyd and W. R. Parry, Introductory notes on Richard Thompson's groups, L'Enseignement Mathematique, Vol. 42 (1996), pp. 215256.
%H A. Karttunen, <a href="/A072796/b072796.txt">Table of n, a(n) for n = 0..196</a>
%H J. W. Cannon, W. J. Floyd and W. R. Parry, <a href="http://www.geom.uiuc.edu/docs/preprints/lib/GCG63/thompson.ps">Notes on Richard Thompson's Groups F and T</a>
%H A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a>
%o (Scheme function implementing this automorphism on liststructures, both the constructive (*A072796) and destructive (*A072796!) variant given:)
%o (define (*A072796 s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (cons (cadr s) (cons (car s) (cddr s))))))
%o (define (*A072796! s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (swap! s) (robr! s) (swap! (cdr s)) s)))
%o (define (robr! s) (let ((excdr (cdr s))) (setcdr! s (caar s)) (setcar! (car s) excdr) (swap! (car s)) (swap! s) s))
%o (define (swap! s) (let ((excar (car s))) (setcar! s (cdr s)) (setcdr! s excar) s))
%Y Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204.
%Y Fixed point counts and cycle counts are given in A073190 and A073191.
%Y Cf. A073190, A072797, A129608.
%K nonn
%O 0,3
%A _Antti Karttunen_, Jun 12 2002
