|
%I
%S 0,1,3,2,7,6,4,5,15,14,12,13,8,9,10,11,31,30,28,29,24,25,26,27,16,17,
%T 18,19,20,21,22,23,63,62,60,61,56,57,58,59,48,49,50,51,52,53,54,55,32,
%U 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,127,126,124,125,120,121
%N Permutation of nonnegative integers: A059893-conjugate of A153151.
%C This permutation is induced by a wreath recursion a = s(a,b), b = (b,b) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 103 of Bondarenko, Grigorchuk, et al. paper, starting from the active (swapping) state a and rewriting bits from the second most significant bit to the least significant end, continuing complementing as long as the first 1-bit is reached, which is the last bit to be complemented.
%C The automorphism group of infinite binary tree (isomorphic to an infinitely iterated wreath product of cyclic groups of two elements) embeds naturally into the group of "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps these kind of permutations to the corresponding Catalan automorphisms/bijections (that act on S-expressions). The following identities hold: *A069770 = psi(A063946) (Just swap the left and right subtrees of the root), *A057163 = psi(A054429) (Reflect the whole tree), *A069767 = psi(A153141), *A069768 = psi(A153142), *A122353 = psi(A006068), *A122354 = psi(A003188), *A122301 = psi(A154435), *A122302 = psi(A154436) and from *A154449 = psi(A154439) up to *A154458 = psi(A154448). See also comments at A153246 and A153830.
%H A. Karttunen, <a href="/A153141/b153141.txt">Table of n, a(n) for n = 0..2047</a>
%H Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, Sunic, <a href="http://arxiv.org/abs/0803.3555">Classification of groups generated by 3-state automata over a 2-letter alphabet</a>, pp. 8--9 & 103.
%H S. Wolfram, R. Lamy, <a href="http://forum.wolframscience.com/showthread.php?threadid=107">Discussion on the NKS Forum</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e 18 = 10010 in binary and after complementing the second, third and the fourthmost significant bits at positions 3, 2 and 1, we get 1110., at which point we stop (because bit-1 was originally 1) and fix the rest, so we get 11100 (28 in binary), thus a(18)=28. This is the inverse of "binary adding machine". See pages 8, 9 and 103 in Bondarenko, Grigorchuk, et al. paper.
%e 19 = 10011 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 11101 in binary, which is 29 in decimal, thus a(19)=29.
%o (MIT Scheme:)
%o (define (a153141 n) (if (< n 2) n (let loop ((maskbit (a072376 n)) (z n)) (cond ((zero? maskbit) z) ((not (zero? (modulo (floor->exact (/ n maskbit)) 2))) (- z maskbit)) (else (loop (floor->exact (/ maskbit 2)) (+ z maskbit)))))))
%o (define (psi inftreeperm) (lambda (s) (swap-binary-tree-according-to-infbintree-permutation s inftreeperm)))
%o (define (swap-binary-tree-according-to-infbintree-permutation s inftreeperm) (cond ((not (= 1 (inftreeperm 1))) (error "Function inftreeperm should return 1 for 1 and it should be one-to-one and onto!")) (else (let fork ((s s) (nod 1)) (cond ((pair? s) (fork (car s) (* 2 nod)) (fork (cdr s) (+ (* 2 nod) 1)) (let ((node-dest (inftreeperm nod)) (left-dest (inftreeperm (* 2 nod))) (right-dest (inftreeperm (1+ (* 2 nod))))) (cond ((or (not (= (floor->exact (/ left-dest 2)) node-dest)) (not (= (floor->exact (/ right-dest 2)) node-dest))) (error (format #t "Function inftreeperm is not an automorphism of an infinite binary tree. Either the left or right child flees from its parent: (inftreeperm ~a)=~a. Left: (inftreeperm ~a)=~a, Right: (inftreeperm ~a)=~a.\n" nod node-dest (* 2 nod) left-dest (1+ (* 2 nod)) right-dest))) ((= (1+ left-dest) right-dest)) (else (*A069770! s))))))) s)))
%Y Inverse: A153142. a(n) = A059893(A153151(A059893(n))) = A059894(A153152(A059894(n))) = A154440(A154445(n)) = A154442(A154443(n)). Corresponds to A069767 in the group of Catalan bijections. Cf. also A154435-A154436, A154439-A154448, A072376.
%Y Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.
%K nonn,base
%O 0,3
%A _Antti Karttunen_, Dec 20 2008
|
