A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 20, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 45, 46, 48, 49, 50, 44, 47, 42, 37, 38, 43, 39, 40, 41, 54, 55, 53, 51, 52, 57, 56, 58, 59, 61, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset

0,3

Comments

This bijection 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 A C

\ / \ /

x C --> x B () A () A

\ / \ / \ / --> \ /

x x x x

((a . b) . c) --> ((a . c) . b) (() . a) ---> (() . a)

See the example for an explanation of how to obtain a given integer sequence from this definition.

Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - Antti Karttunen, Jan 14 2024

Links

Table of n, a(n) for n=0..71.

A. Karttunen, Catalan Automorphisms

Index entries for signature-permutations induced by Catalan automorphisms

Formula

a(n) = A057163(A072796(A057163(n))).

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), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "B" and "C" in the diagram given in the comments are:
.
                          \/     \/       \/               \/
       \/     \/         \/       \/     \/       \/ \/     \/
      \/       \/       \/       \/       \/       \_/       \/
a(n)=  2        3        4        5        7        6        8
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8.

Prog

(Scheme function implementing this automorphism on list-structures/S-expressions, both constructive (*A072797) and destructive (*A072797!) version:)
(define (*A072797 s) (if (and (pair? s) (pair? (car s))) (cons (cons (caar s) (cdr s)) (cdar s)) s))
(define (*A072797! s) (cond ((not (pair? s)) s) ((not (pair? (car s))) s) (else (swap! s) (robl! s) (swap! (car s)) s)))
(define (robl! s) (let ((ex-car (car s))) (set-car! s (cddr s)) (set-cdr! (cdr s) ex-car) (swap! (cdr 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 8 of A089840.

Cf. A014486, A057163, A072796, A127301, A129593.

Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191.

Sequence in context: A336285 A222249 A230565 * A131169 A131170 A082338

Adjacent sequences: A072794 A072795 A072796 * A072798 A072799 A072800

Keyword

nonn

Author

Antti Karttunen, Jun 12 2002

Extensions

Further comments added by Antti Karttunen, Jun 04 2011 and Mar 30 2024

Status

approved