A072634 -id:A072634 - 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.

A072635 Inverse permutation to A072634.

Original entry on oeis.org

0, 1, 3, 2, 6, 8, 7, 19, 16, 5, 15, 4, 14, 52, 43, 51, 42, 20, 22, 53, 60, 21, 61, 56, 179, 155, 178, 154, 177, 164, 557, 163, 556, 11, 39, 13, 41, 151, 123, 153, 125, 12, 40, 33, 117, 152, 124, 471, 381, 477, 553, 479, 555, 505, 1797, 507, 1799, 478, 554, 1536

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms
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(A072635(n))+1)/2 [A029837(n+1) gives the binary width of n].

A072635(n) = A057163(A072637(n)). Cf. also A014486, A059905, A059906, A071652, A072647, A072637.

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

Original entry on oeis.org

0, 1, 3, 2, 11, 6, 5, 7, 4, 100, 27, 24, 45, 14, 18, 10, 13, 62, 17, 8, 15, 28, 9, 1988, 477, 179, 1100, 116, 150, 61, 113, 2090, 147, 35, 189, 302, 58, 162, 44, 39, 73, 23, 34, 20, 102, 1229, 295, 29, 111, 680, 72, 21, 12, 26, 93, 38, 47, 70, 1292, 91, 16, 22, 117, 187

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A072657. Cf. also A014486, A000695, A054238, A048680, A071651, A072634, A072636, A072646, A072658, A072660.

A072636 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.

Original entry on oeis.org

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, 258, 4101, 4117, 22, 65, 69, 1030, 1090, 81, 1026, 16390, 16454, 20, 23, 19, 68, 72, 13, 14, 36, 521, 547, 42, 515, 8201, 8233, 15, 16, 34, 43, 129, 132, 137, 2059, 2179

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms
Index entries for sequences that are permutations of the natural numbers

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

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

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 6, 11, 9, 28, 15, 17, 62, 8, 13, 10, 14, 45, 18, 24, 27, 100, 36, 187, 117, 91, 1292, 22, 70, 38, 72, 680, 93, 111, 295, 1229, 16, 47, 26, 29, 102, 12, 20, 23, 58, 302, 73, 189, 147, 2090, 21, 34, 39, 35, 113, 44, 61, 116, 1100, 162, 150, 179, 477

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A072659. Cf. also A014486, A000695, A054238, A048680, A071651, A072634, A072636, A072646, A072656, A072660.

A082856 Recursive binary interleaving code for rooted plane binary trees, as ordered by A014486.

Original entry on oeis.org

0, 1, 3, 5, 11, 35, 7, 21, 69, 139, 2059, 43, 547, 8227, 15, 39, 23, 277, 4117, 71, 85, 1093, 16453, 32907, 8388747, 2187, 526347, 134219787, 171, 2091, 555, 131619, 33554979, 8235, 8739, 2105379, 536879139, 143, 2063, 47, 551, 8231, 31, 55, 279, 65813, 16777493, 4119, 4373, 1052693, 268439573, 79, 103, 87, 341, 4181, 1095, 1109

Offset: 0

Antti Karttunen, May 06 2003

nonn

This encoding has a property that the greatest common subtree i.e. the intersect (or the least common supertree, the union) of any two trees can be obtained by simply computing the binary-AND (A004198) (or respectively: binary-OR, A003986) of the corresponding codes. See A082858-A082860.

			The empty tree . has code 0, the tree of two edges (and leaves) \/ has code 1 and in general tree's code is obtained by interleaving into odd and even bits (above bit-0, which is always 1 for nonempty trees) the codes for the left and right hand side subtrees of the tree.

Antti Karttunen, Alternative Catalan Orderings (with the complete Scheme source)

Inverse: A082857. Cf. A072634-A072637, A075173-A075174, A000695.

A082857 Inverse function of N -> N injection A082856.

Original entry on oeis.org

0, 1, 0, 2, 0, 3, 0, 6, 0, 0, 0, 4, 0, 0, 0, 14, 0, 0, 0, 0, 0, 7, 0, 16, 0, 0, 0, 0, 0, 0, 0, 42, 0, 0, 0, 5, 0, 0, 0, 15, 0, 0, 0, 11, 0, 0, 0, 39, 0, 0, 0, 0, 0, 0, 0, 43, 0, 0, 0, 0, 0, 0, 0, 123, 0, 0, 0, 0, 0, 8, 0, 19, 0, 0, 0, 0, 0, 0, 0, 51, 0, 0, 0, 0, 0, 20, 0, 53, 0, 0, 0, 0, 0, 0, 0, 154, 0, 0, 0, 0, 0, 0, 0, 52, 0, 0, 0, 0, 0, 0, 0, 151, 0, 0, 0, 0, 0, 0, 0, 155

Offset: 0

Antti Karttunen, May 06 2003

nonn

a(n) = 0 for those n which do not occur as the values of A082856. All positive natural numbers occur here once.

Antti Karttunen, Alternative Catalan Orderings (with the complete Scheme source)

Cf. A082856, A072634-A072637, A075173-A075174.

a(A082856(n)) = n for all n.

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

A072635 Inverse permutation to A072634.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

A072636 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.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

A082856 Recursive binary interleaving code for rooted plane binary trees, as ordered by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A082857 Inverse function of N -> N injection A082856.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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