login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 92
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; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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 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.

PROG

(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.

Sequence in context: A130959 A130928 A154126 * A129612 A154455 A082345

Adjacent sequences:  A069767 A069768 A069769 * A069771 A069772 A069773

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 16 2002. Entry revised Oct 11 2006.

STATUS

approved

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 22 05:11 EST 2019. Contains 319353 sequences. (Running on oeis4.)