A071654 -id:A071654 - cp's OEIS frontend

A071673 Sequence a(n) obtained by setting a(0) = 0; then reading the table T(x,y)=a(x)+a(y)+1 in antidiagonal fashion.

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

Offset: 0

Antti Karttunen, May 30 2002

The fixed point of RASTxx transformation. The repeated applications of RASTxx starting from A072643 seem to converge toward this sequence. Compare to A072768 from which this differs first time at the position n=37, where A072768(37) = 4, while A071673(37) = 5.
Each term k occurs A000108(k) times, and maximal position where k occurs is A072638(k).
The size of each Catalan structure encoded by the corresponding terms in triangles A071671 & A071672 (i.e., the number of digits / 2), as obtained with the global ranking/unranking scheme presented in A071651-A071654.

			The first 15 rows of this irregular triangular table:
               0,
               1,
              2, 2,
             3, 3, 3,
            3, 4, 4, 3,
           4, 4, 5, 4, 4,
          4, 5, 5, 5, 5, 4,
         4, 5, 6, 5, 6, 5, 4,
        4, 5, 6, 6, 6, 6, 5, 4,
       5, 5, 6, 6, 7, 6, 6, 5, 5,
      5, 6, 6, 6, 7, 7, 6, 6, 6, 5,
     4, 6, 7, 6, 7, 7, 7, 6, 7, 6, 4,
    5, 5, 7, 7, 7, 7, 7, 7, 7, 7, 5, 5,
   5, 6, 6, 7, 8, 7, 7, 7, 8, 7, 6, 6, 5,
  6, 6, 7, 6, 8, 8, 7, 7, 8, 8, 6, 7, 6, 6
etc.
E.g., we have
  a(1) = T(0,0) = a(0) + a(0) + 1 = 1,
  a(2) = T(1,0) = a(1) + a(0) + 1 = 2,
  a(3) = T(0,1) = a(0) + a(1) + 1 = 2,
  a(4) = T(2,0) = a(2) + a(0) + 1 = 3, etc.

Antti Karttunen, Table of n, a(n) for n = 0..10440 (rows 0..144 of the triangle, flattened)
N. J. A. Sloane, Transforms (Maple code for RASTxx transform)

Same triangle computed modulo 2: A071674.
Permutations of this sequence include: A072643, A072644, A072645, A072660, A072768, A072789, A075167.
Cf. also A000108, A002260, A004736, A002262, A025581, A072638.

up_to = 105;
A002260(n) = (n-binomial((sqrtint(8*n)+1)\2, 2)); \\ From A002260
A004736(n) = (1-n+(n=sqrtint(8*n)\/2)*(n+1)\2); \\ From A004736
A071673list(up_to) = { my(v=vector(1+up_to)); v[1] = 0; for(n=1,up_to,v[1+n] = 1 + v[A004736(n)] + v[A002260(n)]); (v); };
v071673 = A071673list(up_to);
A071673(n) = v071673[1+n]; \\ Antti Karttunen, Aug 17 2021

(define (A071673 n) (cond ((zero? n) n) (else (+ 1 (A071673 (A025581 (-1+ n))) (A071673 (A002262 (-1+ n)))))))

a(0) = 0, a(n) = 1 + a(A025581(n-1)) + a(A002262(n-1)) = 1 + a(A004736(n)) + a(A002260(n)).

Self-referential definition added Jun 03 2002

Term a(0) = 0 prepended and the Example-section amended by Antti Karttunen, Aug 17 2021

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

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 6, 10, 11, 29, 16, 22, 56, 8, 12, 9, 15, 36, 14, 21, 28, 66, 67, 436, 137, 254, 1597, 37, 79, 46, 121, 667, 106, 232, 407, 2212, 17, 38, 23, 30, 68, 13, 18, 20, 78, 465, 44, 153, 276, 1653, 19, 25, 27, 45, 91, 35, 55, 136, 703, 77, 120, 253, 435, 2278

Offset: 0

Antti Karttunen, May 30 2002

It seems that a(A014137(n)) = a(A014137(n)-1)+1 = A006894(n+1) for all n. - Antti Karttunen, Jul 30 2012

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071652. Cf. also A014486, A061579, A071653, A071654.

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.

A071652 Inverse permutation to A071651.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 5, 14, 16, 8, 9, 15, 42, 19, 17, 11, 37, 43, 51, 44, 20, 12, 39, 121, 52, 126, 53, 21, 10, 40, 123, 149, 127, 154, 56, 18, 28, 38, 124, 151, 385, 155, 163, 47, 54, 30, 112, 122, 152, 387, 475, 164, 135, 156, 57, 13, 114, 376, 150, 388, 477, 503, 136

Offset: 0

Antti Karttunen, May 30 2002

Antti Karttunen, Rows n=0..66 of triangle, flattened
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071651. A071671 gives the corresponding parenthesizations (from the term 1 onward) encoded as binary numbers, i.e. A071671(n) = A063171(A071652(n)) for n >= 1.

A071652(n) = A057163(A071654(n)). Cf. also A014486, A002262, A025581, A071653, A071654.

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

Original entry on oeis.org

0, 1, 3, 2, 10, 6, 5, 7, 4, 66, 28, 21, 36, 15, 14, 9, 12, 56, 22, 8, 16, 29, 11, 2278, 435, 253, 703, 136, 120, 55, 91, 1653, 276, 45, 153, 465, 78, 77, 35, 27, 44, 20, 25, 18, 68, 2212, 407, 30, 232, 667, 121, 19, 13, 23, 106, 46, 38, 79, 1597, 254, 17, 37, 137, 436

Offset: 0

Antti Karttunen, May 30 2002

nonn

A071653(A014137(n-1)) = A072638(n) for all n > 0. - Paul D. Hanna, Jan 04 2007

Also seems that A071653(A014137(n)-1) = A006894(n) for all n > 0. - Antti Karttunen, Jul 30 2012

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071654. Cf. also A014486, A001477, A071651, A071652.

A071672 The binary encoding of parenthesizations given in a "global arithmetic order", using A001477 as the packing bijection N X N -> N.

Original entry on oeis.org

10, 1100, 1010, 111000, 110010, 101100, 110100, 11100010, 11001100, 101010, 11110000, 11010010, 1110001100, 11001010, 10111000, 11100100, 1111000010, 1101001100, 1110001010, 1100111000, 10110010, 11011000, 1110010010

Offset: 1

Antti Karttunen, May 30 2002

A. Karttunen, Gatomorphisms (Includes the complete Scheme source for computing this sequence)

Cf. A071672(n) = A063171(A071654(n)). Permutation of A063171 and A071671. Particularly, applying the automorphism ReflectBinTree (A057163) to A071672(n) yields A071671(n). The length of each term / 2: A071673.

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

cp's OEIS Frontend

A071673 Sequence a(n) obtained by setting a(0) = 0; then reading the table T(x,y)=a(x)+a(y)+1 in antidiagonal fashion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

A072637 Inverse permutation to A072636.

Views

Author

Keywords

Links

Crossrefs

A071652 Inverse permutation to A071651.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

A071672 The binary encoding of parenthesizations given in a "global arithmetic order", using A001477 as the packing bijection N X N -> N.

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