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

0, 1, 3, 2, 6, 5, 13, 8, 4, 14, 10, 36, 20, 9, 25, 19, 24, 11, 12, 18, 38, 16, 7, 44, 27, 209, 77, 21, 105, 66, 104, 28, 35, 65, 230, 54, 15, 34, 33, 75, 43, 26, 85, 50, 40, 37, 22, 31, 191, 67, 23, 51, 41, 69, 107, 68, 49, 92, 30, 29, 32, 56, 211, 46, 17, 299, 120, 5671

Offset

0,3

Comments

This ranking scheme condenses the structures of the same size (cf. A072789) somewhat better than scheme presented in A072656 (which uses the N X N -> N bijection A072793). Compare the sequences A072790 and A072640 giving the max positions where the last structure with size n will occur in these orderings and the respective binary widths A072791 & A072642. However, by using the second or third power of the bijection A072734 one gets even better results in a certain range.

Links

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

A. Karttunen, Gatomorphisms

Index entries for sequences that are permutations of the natural numbers

Prog

(Scheme functions below show the essential idea. For a complete source, follow the "Gatomorphisms" link.)
(define A072787 (lexrank->arithrank-bijection packA072734))
(define (lexrank->arithrank-bijection packfun) (lambda (n) (rank-bintree (binexp->parenthesization (A014486 n)) packfun)))
(define (rank-bintree bt packfun) (cond ((not (pair? bt)) 0) (else (1+ (packfun (rank-bintree (car bt) packfun) (rank-bintree (cdr bt) packfun))))))

Crossrefs

Inverse permutation: A072788. Cf. also A014486, A072734, A072789.

Sequence in context: A090868 A125675 A301501 * A338524 A371906 A293549

Adjacent sequences: A072784 A072785 A072786 * A072788 A072789 A072790

Keyword

nonn

Author

Antti Karttunen, Jun 12 2002

Status

approved