A072636 - OEIS

%I #5 May 01 2014 02:43:28

%S 0,1,2,3,5,6,4,9,11,18,21,17,66,70,7,8,10,35,41,12,33,131,139,261,274,

%T 258,4101,4117,22,65,69,1030,1090,81,1026,16390,16454,20,23,19,68,72,

%U 13,14,36,521,547,42,515,8201,8233,15,16,34,43,129,132,137,2059,2179

%N Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using packA054238tr as the packing bijection N X N -> N.

%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gatomorf.htm">Gatomorphisms</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%o (Scheme functions below show the essential idea. For a complete source, follow the "Gatomorphisms" link.)

%o (define A072636 (lexrank->arithrank-bijection packA054238tr))

%o (define (lexrank->arithrank-bijection packfun) (lambda (n) (rank-bintree (binexp->parenthesization (A014486 n)) packfun)))

%o (define (rank-bintree bt packfun) (cond ((not (pair? bt)) 0) (else (1+ (packfun (rank-bintree (car bt) packfun) (rank-bintree (cdr bt) packfun))))))

%o (define (packA054238tr x y) (+ (A000695 y) (* 2 (A000695 x))))

%Y Inverse permutation: A072637. Cf. also A014486, A000695, A054238, A071651, A072634, A072646, A072656, A072658, A072644.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jun 02 2002