|
| |
|
|
A072796
|
|
Self-inverse permutation of natural numbers induced by Catalan Automorphism *A072796 acting on the parenthesizations encoded by A014486.
|
|
50
| |
|
|
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, 26, 27, 37, 38, 42, 44, 47, 51, 53, 56, 60, 28, 29, 39, 43, 52, 30, 40, 31, 45, 46, 32, 48, 49, 50, 33, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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.)
...B...C...........A...C
....\./.............\./
.A...x....-->....B...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (b . (a . c)) ______ (a . ()) ---> (a . ())
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).
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).
Look at the example in A069770 to see how this will produce the given sequence of integers.
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| A. Karttunen, Table of n, a(n) for n = 0..196
J. W. Cannon, W. J. Floyd and W. R. Parry, Notes on Richard Thompson's Groups F and T
A. Karttunen, Catalan Automorphisms
|
|
|
PROG
| (Scheme function implementing this automorphism on list-structures, both the constructive (*A072796) and destructive (*A072796!) variant given:)
(define (*A072796 s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (cons (cadr s) (cons (car s) (cddr s))))))
(define (*A072796! s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) s) (else (swap! s) (robr! s) (swap! (cdr s)) s)))
(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))
(define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
|
|
|
CROSSREFS
| Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204.
Fixed point counts and cycle counts are given in A073190 and A073191.
Cf. A073190, A072797, A129608.
Sequence in context: A130340 A130339 A058812 * A130374 A122363 A122364
Adjacent sequences: A072793 A072794 A072795 * A072797 A072798 A072799
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Antti Karttunen (His-Firstname.His-Surname@gmail.com) Jun 12 2002
|
| |
|
|
