A072635 -id:A072635 - cp's OEIS frontend

A072644 Size of the parenthesizations obtained with the global ranking/unranking scheme A072634-A072637.

0, 1, 2, 2, 3, 3, 3, 4, 4, 3, 4, 3, 4, 5, 5, 5, 5, 4, 4, 5, 5, 4, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 4, 5, 4, 5, 6, 6, 6, 6, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 7, 7, 8, 8, 7, 8, 8, 9, 5, 4, 6, 5, 5, 4, 6, 5, 7, 6, 7, 6, 7, 6, 7, 6, 5, 6, 6, 7, 6, 6, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 7, 8, 7, 8, 7, 8, 7

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

Sohrab Towfighi, Symbolic regression by random search, arXiv:1906.07848 [cs.NE], 2019.

Cf. A072635 & A072637. A072644(n) = A029837(A014486(A072635(n))+1)/2 or = A029837(A014486(A072637(n))+1)/2 [A029837(n+1) gives the binary width of n].

Each value v occurs A000108(v) times. The maximum position for value v to occur is A072639(v). Permutations: A071673, A072643, A072645, A072660.

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

Original entry on oeis.org

0, 1, 3, 2, 11, 9, 4, 6, 5, 139, 131, 33, 41, 35, 12, 10, 8, 70, 66, 7, 17, 21, 18, 32907, 32779, 2051, 2179, 2059, 161, 137, 129, 8233, 8201, 43, 515, 547, 521, 140, 132, 34, 42, 36, 16, 14, 72, 16454, 16390, 68, 1026, 1090, 1030, 15, 13, 19, 81, 69, 23, 65

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

Antti Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A072635.
Cf. A014486, A000695, A054238, A071651, A072636, A072646, A072656, A072658, A072644.
Cf. also A296689.

;; Functions below show the essential idea:
(define A072634 (lexrank->arithrank-bijection packA054238))
(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))))))
(define (packA054238 x y) (+ (A000695 x) (* 2 (A000695 y))))

A072637 Inverse permutation to A072636.

Original entry on oeis.org

0, 1, 2, 3, 6, 4, 5, 14, 15, 7, 16, 8, 19, 42, 43, 51, 52, 11, 9, 39, 37, 10, 28, 38, 112, 123, 121, 151, 149, 122, 376, 150, 466, 20, 53, 17, 44, 154, 155, 126, 127, 18, 47, 54, 156, 135, 136, 480, 481, 477, 475, 387, 385, 476, 1531, 386, 1234, 415, 413, 1542, 1540

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme source for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

A072644 gives the size of the corresponding parenthesizations, i.e. A072644(n) = A029837(A014486(A072637(n))+1)/2 [A029837(n+1) gives the binary width of n].

A072637(n) = A057163(A072635(n)). Cf. also A014486, A059905, A059906, A071654, A072646.

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4

Offset: 0

Peter Luschny, Aug 09 2012

See Antti Karttunen's code in A057117. Karttunen writes: "Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES (Kreher and Stinson) book."

For all n>0, a(A014486(n)) = n = A080300(A014486(n)). The sequence A080300 differs from this one in that it gives 0 for those n which are not found in A014486. - Antti Karttunen, Aug 10 2012

G. C. Greubel, Table of n, a(n) for n = 0..1000
A. Karttunen, Catalan's Triangle and ranking of Mountain Ranges
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.

Cf. A213704, A057117, A057164, A057505, A057506, A057501, A057502, A057511, A057512, A057123, A057117, A057509, A057510, A057161, A057162, A072766, A071654, A071652, A075161, A061856, A072635, A072788, A057518, A075168, A080119, A057120, A072773.

A215406 := proc(n) local m,a,y,t,x,u,v;
m := iquo(A070939(n), 2);
a := A030101(n);
y := 0; t := 1;
for x from 0 to 2*m-2 do
    if irem(a, 2) = 1 then y := y + 1
    else u := 2*m - x;
         v := m-1 - iquo(x+y,2);
         t := t + A037012(u,v);
         y := y - 1 fi;
    a := iquo(a, 2) od;
A014137(m) - t end:
seq(A215406(i),i=0..199); # Peter Luschny, Aug 10 2012

A215406[n_] := Module[{m, d, a, y, t, x, u, v}, m = Quotient[Length[d = IntegerDigits[n, 2]], 2]; a = FromDigits[Reverse[d], 2]; y = 0; t = 1; For[x = 0, x <= 2*m - 2, x++, If[Mod[a, 2] == 1, y++, u = 2*m - x; v = m - Quotient[x + y, 2] - 1; t = t - Binomial[u - 1, v - 1] + Binomial[u - 1, v]; y--]; a = Quotient[a, 2]]; (1 - I*Sqrt[3])/2 - 4^(m + 1)*Gamma[m + 3/2]*Hypergeometric2F1[1, m + 3/2, m + 3, 4]/(Sqrt[Pi]*Gamma[m + 3]) - t]; Table[A215406[n] // Simplify, {n, 0, 86}] (* Jean-François Alcover, Jul 25 2013, translated and adapted from Peter Luschny's Maple program *)

def A215406(n) : # CatalanRankGlobal(n)
    m = A070939(n)//2
    a = A030101(n)
    y = 0; t = 1
    for x in (1..2*m-1) :
        u = 2*m - x; v = m - (x+y+1)/2
        mn = binomial(u, v) - binomial(u, v-1)
        t += mn*(1 - a%2)
        y -= (-1)^a
        a = a//2
    return A014137(m) - t

A296689 Let phi be the one-to-one mapping between binary trees and natural numbers described in the Tychonievich link. Let a(n) = min({phi^{-1}(t)| size(t)=n}); i.e., a(n) is the rank -- starting from 0 -- of the first tree the size of which is n.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 24, 30, 54, 64, 124, 244, 383, 503, 981, 1021, 1981, 3901, 6137, 8057, 13649, 16369, 32689, 65329, 98230, 130870, 229312, 261952, 491516, 524156, 1046388, 1048564, 2093044, 4182004, 8359924, 16715764, 25141220, 33497060, 58703812, 67059652, 125828996, 134184836, 259487492, 268435204, 536866564, 1073729284

Offset: 0

Philippe Esperet, Dec 18 2017

nonn

Let v(n) = max({phi^{-1}(t)| size(t)=n}); v(n) is already known as A072639.
The interleaving process used by Tychonievich is not specific to base 2, each base b>=3 giving birth to a new a(n)-like sequence and a new v(n)-like sequence.
a(n) is the position of the first occurrence of n in A072644. - Andrey Zabolotskiy, Dec 20 2017
The tree-enumeration scheme of Tychonievich is similar, but not the same as "Recursive binary interleaving of binary trees" mentioned at my OEIS Wiki notes about Alternative Catalan Orderings. On the other hand, it seems to be the same (possibly up to the reflection of binary trees) as the ranking/unranking scheme mentioned in the section "Binary tree encoding with bijection" and in sequences A072634 - A072637 that are permutations of nonnegative integers induced by cross-ranking binary trees between such a "dense" binary interleaving ranking system and the standard lexicographic ordering of them (A014486). - Antti Karttunen, Dec 20 2017

Antti Karttunen, Alternative Catalan Orderings (Notes in OEIS Wiki, 2012-, see the section "Binary tree encoding with bijection")
Luther Tychonievich, Enumerating Trees, 2013.

Cf. A014486, A059905, A059906, A072639, A072634, A072635, A072644.

let rec evenOdd=function(*Luther Tychonievich decomposition*)
| n when n<=1 -> n,0
| n -> let ev,od=evenOdd(n/2) in
        2*od+n mod 2,ev
let rec cardImage=function
| n when n<=1 -> n
| n -> let ev,od=evenOdd(n-1) in 1+cardImage(ev)+cardImage(od)
let checkCatalanBis n=(*why 2*n+1 ? empirical...*)
  let (first,last)=(Array.make (2*n+1) 0,Array.make (2*n+1) 0) in
    for i=0 to 1 lsl n do
    let cai=cardImage i in
      last.(cai)<-1+last.(cai);
      if first.(cai)=0 then first.(cai)<-i done;
  (first,last)

def dei(n):
    n1 = n2 = 0
    bit = 1
    while n:
        if n&1:
            n1 += bit
        n >>= 1
        if n&1:
            n2 += bit
        n >>= 1
        bit <<= 1
    return (n1, n2)
r = [0]
for n in range(1, 100):
    r.append(1 + sum(r[x] for x in dei(n-1)))
print([r.index(x) for x in range(max(r)+1)])
# Andrey Zabolotskiy, Dec 20 2017

cp's OEIS Frontend

A072644 Size of the parenthesizations obtained with the global ranking/unranking scheme A072634-A072637.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

A072637 Inverse permutation to A072636.

Views

Author

Keywords

Links

Crossrefs

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A296689 Let phi be the one-to-one mapping between binary trees and natural numbers described in the Tychonievich link. Let a(n) = min({phi^{-1}(t)| size(t)=n}); i.e., a(n) is the rank -- starting from 0 -- of the first tree the size of which is n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

OCaml

Python