login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A073270
Permutation of natural numbers induced by Catalan Automorphism *A073270 acting on the binary trees/parenthesizations encoded by A014486/A063171.
16
0, 1, 3, 2, 7, 8, 5, 4, 6, 17, 18, 20, 21, 22, 12, 13, 11, 9, 10, 15, 14, 16, 19, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 30, 33, 28, 23, 24, 29, 25, 26, 27, 40, 41, 39, 37, 38, 43, 42, 44, 47, 52, 51, 53, 56, 60, 129, 130, 132, 133, 134
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).
.A...B...............C...B
..\./.................\./
...x...C...-->.....A...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (a . (c . b)) ____ (() . a) ----> (a . ())
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.
PROG
(Scheme functions implementing this automorphism on list-structures/S-expressions, both constructive (*A073270) and destructive (*A073270!) versions:)
(define (*A073270 s) (cond ((not (pair? s)) s) ((not (pair? (car s))) (cons (cdr s) (car s))) (else (cons (caar s) (cons (cdr s) (cdar s))))))
(define (*A073270! s) (*A072796! (*A069770! s)))
CROSSREFS
Row 19 of A089840. Inverse permutation: A073269. a(n) = A072796(A069770(n)).
Sequence in context: A071655 A130964 A130929 * A072094 A122330 A082322
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 25 2002
EXTENSIONS
A graphical description and Scheme-implementations of automorphism added by Antti Karttunen, Jun 04 2011
STATUS
approved