|
| |
|
|
A072796
|
|
Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.
|
|
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;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
This bijection effects the following transformation on the unlabeled rooted plane general trees (letters A, B, C, etc. refer to arbitrary subtrees located on those vertices):
A A A B B A A B C B A C
| --> | \ / --> \ / \ | / --> \ | /
| | \./ \./ \|/ \|/ etc.
I.e., it keeps "planted" (root degree = 1) trees intact, and swaps the two leftmost toplevel subtrees of the general trees that have a root degree > 1.
On the level of underlying binary trees that general trees map to (see, e.g., 1967 paper by N. G. De Bruijn and B. J. M. Morselt, or consider lists vs. dotted pairs in Lisp programming language), 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).
B C A C
\ / \ /
A x --> B x A () A ()
\ / \ / \ / --> \ /
x x x x
(a . (b . c)) -> (b . (a . c)) (a . ()) ---> (a . ())
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 section to see how this will produce the given sequence of integers.
Applying this permutation recursively down the right hand side branch of the binary trees (or equivalently, along the topmost level of the general trees) produces permutations A057509 and A057510 (that occur at the same index 2 in tables A122203 and A122204) that effect "shallow rotation" on general trees and parenthesizations. Applying it recursively down the both branches of binary trees (as in pre- or postorder traversal) produces A057511 and A057512 (that occur at the same index 2 in tables A122201 and A122201) that effect "deep rotation" on general trees and parenthesizations.
|
|
|
LINKS
|
|
|
|
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 "A" and "B" in the diagram given in the comments are:
.
\/ \/ \/ \/
\/ \/ \/ \/ \/ \/ \/ \/
\/ \/ \/ \_/ \/ \/ \/
a(n)= 2 3 4 6 5 7 5
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 6, 5, 7, 8.
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
