login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A072796 Self-inverse permutation of natural numbers induced by Catalan Automorphism *A072796 acting on the parenthesizations encoded by A014486. 50

%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 Self-inverse 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. 215--256.

%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 list-structures, 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 ((ex-cdr (cdr s))) (set-cdr! s (caar s)) (set-car! (car s) ex-cdr) (swap! (car s)) (swap! s) s))

%o (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 14:01 EST 2020. Contains 331010 sequences. (Running on oeis4.)