|
Search: id:A069770
|
|
|
| A069770 |
|
Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top-branches of a binary tree. An involution of nonnegative integers. |
|
+0
70
|
|
| 0, 1, 3, 2, 7, 8, 6, 4, 5, 17, 18, 20, 21, 22, 16, 19, 14, 9, 10, 15, 11, 12, 13, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 44, 47, 53, 56, 60, 42, 51, 37, 23, 24, 38, 25, 26, 27, 43, 52, 39, 28, 29, 40, 30, 31, 32, 41, 33, 34, 35, 36, 129, 130, 132, 133, 134
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
This is the simplest possible Catalan automorphism after the identity automorphism *A001477. It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those nodes):
.A...B....-->....B...A.
..\./.............\./..
...x...............x...
(a . b) ------> (b . a)
|
|
REFERENCES
|
A. Karttunen, paper in preparation, draft available by e-mail.
|
|
LINKS
|
A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.
Index entries for signature-permutations of Catalan automorphisms
|
|
EXAMPLE
|
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:
...................one tree of one internal.
..empty tree.........(non-leaf) node........
............................................
......x......................\/.............
n=....0......................1..............
a(n)=.0......................1.............. (both are always fixed)
the next 7 trees, with with 2-3 internal nodes, in range [A014137(1), A014138(2)] = [2,8] change as follows:
..........................\/.....\/.................\/.....\/...
.......\/.....\/.........\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\/.......\/.......\_/.......\/.......\/.
n=.....2........3........4........5........6........7........8..
..............................|.................................
..............................|.................................
..............................V.................................
................................................................
........................\/.....\/.....................\/.....\/.
.....\/.........\/.....\/... ...\/.......\/.\/.......\/.......\/
......\/.......\/.......\/.......\/.......\_/.......\/.......\/.
a(n)=..3........2........7........8........6........4........5..
thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.
|
|
PROGRAM
|
(Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
(CONSTRUCTIVE VERSION:) (define (*A069770 s) (if (pair? s) (cons (cdr s) (car s)) s))
(DESTRUCTIVE VERSION:) (define (*A069770! s) (if (pair? s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car))) s)
|
|
CROSSREFS
|
Row 1 of A089840. a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).
The number of cycles (A007595) and the number of fixed points (A000108 interleaved with zeros) in range [A014137(n-1)..A014138(n-1)] of this permutation are given by the same sequences as for the following recursive derivations of this automorphism: *A057163 and *A122351.
Other related sequences: A069767, A069768, A089864, A123492.
Adjacent sequences: A069767 A069768 A069769 this_sequence A069771 A069772 A069773
Sequence in context: A125984 A130959 A130928 this_sequence A129612 A082345 A122327
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Antti Karttunen Apr 16 2002. Entry revised Oct 11 2006.
|
|
|
Search completed in 0.006 seconds
|
