A072766 -id:A072766 - cp's OEIS frontend

A072771 X-projection of the tabular N X N -> N bijection A072764 and Y-projection of its transpose A072766.

0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 0, 0, 0, 1, 1, 2, 4, 5, 3, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 4, 9, 10, 5, 11, 12, 13, 3, 3, 6, 14, 15, 7, 16, 17, 18, 8, 19, 20, 21, 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Jun 12 2002

nonn

This corresponds to Lisp/Scheme function 'car' computed with respect to the lexicographical ordering of parenthesizations/planar binary trees (A014486), i.e. with planar binary trees this is equal to extracting the left subtree (from the root), with general parenthesizations equal to taking the first sub-parenthesization of the top-level list and with general plane trees equal to taking the leftmost branch of the tree (at the root).

A. Karttunen, Gatomorphisms (with the complete Scheme source)

A072772 Y-projection of the tabular N X N -> N bijection A072764 and X-projection of its transpose A072766.

Original entry on oeis.org

0, 1, 0, 2, 3, 1, 0, 0, 4, 5, 6, 7, 8, 2, 3, 1, 0, 0, 1, 0, 0, 0, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 4, 5, 6, 7, 8, 2, 3, 1, 0, 0, 1, 0, 0, 0, 2, 3, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44

Offset: 1

Antti Karttunen, Jun 12 2002

nonn

This corresponds to Lisp/Scheme function 'cdr' computed with respect to the lexicographical ordering of parenthesizations/planar binary trees (A014486), i.e. with planar binary trees this is equal to extracting the right subtree (from the root), with general parenthesizations equal to discarding the first sub-parenthesization of the top-level list and with general plane trees equal to discarding the leftmost branch from the root.

A. Karttunen, Gatomorphisms (with the complete Scheme source)

A072767 Inverse permutation to A072766.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 6, 10, 11, 16, 22, 29, 37, 8, 12, 9, 15, 21, 14, 28, 36, 45, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 17, 23, 30, 38, 47, 13, 18, 20, 55, 66, 27, 78, 91, 105, 19, 25, 35, 120, 136, 44, 153, 171, 190, 54, 210, 231, 253, 276

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

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

Cf. A072765, A001477, A072771, A072772.

A072795 A014486-indices of the plane binary trees AND plane general trees whose left subtree is just a stick: \. thus corresponding to the parenthesizations whose first element (of the top-level list) is an empty parenthesization: ().

Original entry on oeis.org

1, 2, 4, 5, 9, 10, 11, 12, 13, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 197, 198, 199

Offset: 0

Antti Karttunen Jun 12 2002

nonn

This sequence is induced by the 'flipped form' of the function 'list': (define (flippedlist x) (cons '() x)) when it acts on symbolless S-expressions encoded by A014486/A063171.

Gives in A063171 positions of the terms which begin with digits 10...

Column 0 of A072764, row 0 of A072766, column 1 of A085201. Complement: A081291. Cf. A085223.

Range[0, Length[#]-1] + CatalanNumber[#] & [Flatten[Array[Table[#, CatalanNumber[#]] &, 7, 0]]] (* Paolo Xausa, Mar 01 2024 *)

a(n) = n + A000108(A072643(n)) = A069770(A057548(n)) = A080300(A083937(n))

A072764 Tabular N X N -> N bijection induced by Lisp/Scheme function 'cons' combining the two planar binary trees/general trees/parenthesizations encoded by A014486(X) and A014486(Y).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 4, 8, 16, 14, 5, 17, 19, 42, 15, 9, 18, 44, 51, 43, 37, 10, 20, 47, 126, 52, 121, 38, 11, 21, 53, 135, 127, 149, 122, 39, 12, 22, 56, 154, 136, 385, 150, 123, 40, 13, 45, 60, 163, 155, 413, 386, 151, 124, 41, 23, 46, 128, 177, 164, 475, 414, 387, 152

Offset: 0

Antti Karttunen Jun 12 2002

Index entries for the sequences induced by list functions of Lisp
Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (with the complete Scheme source)

Inverse permutation: A072765. a(n) = A069770(A072766(n)). Also transpose of A072766, i.e. a(n) = A072766(A038722(n)). The upper triangular region: A072773. Projection functions are A072771 ('car') & A072772 ('cdr'). The sizes of the corresponding Catalan structures: A072768. The first row: A057548, the first column: A072795, diagonal: A083938. Cf. also A080300, A025581, A002262.

a(0)=0 prepended by Sean A. Irvine, Oct 25 2024

A072768 The RASTxx transformation of the sequence A072643.

Original entry on oeis.org

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, 4, 5, 6, 6, 7, 6, 6, 5, 4, 5, 5, 6, 6, 7, 7, 6, 6, 5, 5, 5, 6, 6, 6, 7, 7, 7, 6, 6, 6, 5, 5, 6, 7, 6, 7, 7, 7, 7, 6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 5, 6, 7, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 5

Offset: 1

Antti Karttunen, Jun 12 2002

Also, the sizes of the parenthesizations produced by 'cons' combination A072764 and its transpose A072766.
Differs from A071673 first time at the position n=37, where A072768(37) = 4, while A071673(37) = 5. RASTxx(A072768) differs from A071673 first time at the position n=704, which leads to conjecture that the repeated applications of RASTxx starting from A072643 converge towards A071673, the fixed point of RASTxx transformation.
Each value v occurs A000108(v) times. (The term a(0)=0 is not explicitly listed here as to get a better looking triangle).

A. Karttunen, Gatomorphisms (Includes the complete Scheme source for computing this sequence)
N. J. A. Sloane, Transforms (Maple code for RASTxx transform)

Same triangle computed modulo 2: A072770. Permutations: A072643, A071673, A072644, A072645, A072660, A072789. Cf. also A072769, A025581, A002262.

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

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

A083938 A014486-indices of binary trees whose left and right subtree are identical.

Original entry on oeis.org

0, 1, 6, 42, 52, 385, 414, 477, 506, 555, 4089, 4180, 4388, 4479, 4645, 5095, 5186, 5394, 5485, 5651, 5969, 6060, 6226, 6502, 47363, 47661, 48366, 48664, 49237, 50800, 51098, 51803, 52101, 52674, 53808, 54106, 54679, 55681, 59311, 59609, 60314

Offset: 0

Antti Karttunen, May 13 2003

nonn

Fixed points of permutation A069770. Diagonal of A072764 (and A072766).

a(n) = A080300(A083939(n)). Cf. A083940.

a(0)=0, a(n)=A072764bi(n-1, n-1).

cp's OEIS Frontend

A072771 X-projection of the tabular N X N -> N bijection A072764 and Y-projection of its transpose A072766.

Views

Author

Keywords

Comments

Links

A072772 Y-projection of the tabular N X N -> N bijection A072764 and X-projection of its transpose A072766.

Views

Author

Keywords

Comments

Links

A072767 Inverse permutation to A072766.

Views

Author

Keywords

Links

Crossrefs

A072795 A014486-indices of the plane binary trees AND plane general trees whose left subtree is just a stick: \. thus corresponding to the parenthesizations whose first element (of the top-level list) is an empty parenthesization: ().

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A072764 Tabular N X N -> N bijection induced by Lisp/Scheme function 'cons' combining the two planar binary trees/general trees/parenthesizations encoded by A014486(X) and A014486(Y).

Views

Author

Keywords

Links

Crossrefs

Extensions

A072768 The RASTxx transformation of the sequence A072643.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A083938 A014486-indices of binary trees whose left and right subtree are identical.

Views

Author

Keywords

Comments

Crossrefs

Formula