A080300 -id:A080300 - cp's OEIS frontend

A154472 a(n) = A126309(A154471(n)).

42, 218, 359, 875, 1763, 2359496, 926357642, 1431707647759, 239418125921492, 9138627621456887, 5265474933763866437, 36640566669911088560059, 1544449741807406472977531, 12634727265105076809694418

Offset: 0

Antti Karttunen, Jan 11 2009

nonn

This sequence essentially gives the iterated S-expressions of the sequence A154471, with ()'s removed. See A154473.

A. Karttunen, Table of n, a(n) for n = 0..100

a(n) = A080300(A154473(n)).

A209640 Global ranking function for restricted totally balanced binary strings given in A209641.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 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, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 6, 0, 0, 0, 7, 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, 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, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, Mar 24 2012

nonn

The given Scheme-program implements a ranking function for the terms of A209641, using Khayyam's triangle A007318.

			a(12)=3, as 12 occurs as the 3rd term (zero-based) in A209641.
a(14)=0, as 14 doesn't occur in A209641.

This is an inverse function for A209641 in the sense that a(A209641(n)) = n for all n. The beginning of sequence coincides with A080300, because A209641 is a subsequence of A014486. Used to compute the permutation A209861.

(define (A209640 n) (if (or (zero? n) (not (member_of_A209641? n))) 0 (let* ((w (/ (binwidth n) 2))) (let loop ((rank 0) (row 1) (u (- w 1)) (n (- n (A053644 n))) (i (/ (A053644 n) 2)) (first_0_found? #f)) (cond ((or (zero? row) (zero? u) (zero? n)) (+ (expt 2 (-1+ w)) rank)) ((> i n) (loop rank (- row 1) u n (/ i 2) #t)) (else (loop (+ rank (if first_0_found? (A007318tr (- (+ row u) 1) (- row 1)) (A007318tr (- w 1) (- row 1)))) (+ row 1) (- u 1) (- n i) (/ i 2) first_0_found?)))))))
(define (binwidth n) (let loop ((n n) (i 0)) (if (zero? n) i (loop (floor->exact (/ n 2)) (1+ i)))))

A218783 A014486-indices for the compact representation of Beanstalk-tree, with the lesser numbers coming to the right hand side.

Original entry on oeis.org

1, 3, 7, 18, 49, 142, 438, 1405, 4630, 15595, 53493, 186112, 655421, 2331057, 8362451, 30222369, 109930284, 402134685, 1478480102, 5460253675, 20247271086, 75353895375, 281374686795, 1053846512655, 3957966801068, 14902939174394, 56245902561309, 212741751056939

Offset: 1

Antti Karttunen, Nov 17 2012

nonn

See the comments and examples at A218782.

Antti Karttunen, Table of n, a(n) for n = 1..128

a(n) = A057163(A218781(n)). Cf. A218788, A218782, A218777, A218779.

a(n) = A080300(A218782(n)).

A080970 A014486-indices of the trees whose interior zigzag-tree (Stanley's c) is not branch-reduced (in the sense defined by Donaghey).

Original entry on oeis.org

4, 8, 9, 10, 13, 14, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 31, 33, 35, 36, 37, 38, 41, 42, 44, 45, 46, 50, 51, 52, 54, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 83, 84, 86, 87, 88, 92, 93, 94, 96, 98, 100, 101, 102, 103

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

Cf. A014486, A080300, A080971.

See comment at A080971. Complement of A080980.

a(n) = A080300(A080971(n)).

A080980 A014486-indices of the trees whose interior zigzag-tree (Stanley's c) is branch-reduced (in the sense defined by Donaghey).

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 11, 12, 15, 16, 18, 20, 29, 30, 32, 34, 39, 40, 43, 47, 48, 49, 53, 55, 57, 81, 82, 85, 89, 90, 91, 95, 97, 99, 113, 114, 116, 118, 123, 124, 136, 137, 139, 140, 141, 143, 146, 155, 159, 160, 161, 165, 167, 173, 183, 245, 246, 248, 250, 255, 256, 268

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
R. P. Stanley, Exercises on Catalan and Related Numbers

Cf. A080979. a(n) = A080300(A080981(n)). See comment at A080981. Complement of A080970.

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.

A082860 Array A(x,y): the least common supertree (union) of the binary trees x and y, (x,y) running as (0,0),(1,0),(0,1),(2,0),(1,1),(0,2) and each index referring to a binary tree encoded by A014486(j).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 2, 2, 3, 4, 3, 2, 3, 4, 5, 4, 6, 6, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 14, 14, 5, 6, 7, 8, 7, 6, 15, 4, 15, 6, 7, 8, 9, 8, 16, 6, 11, 11, 6, 16, 8, 9, 10, 9, 19, 7, 14, 5, 14, 7, 19, 9, 10, 11, 10, 9, 8, 42, 15, 15, 42, 8, 9, 10, 11, 12, 11, 10, 37, 51, 43, 6, 43, 51, 37, 10, 11, 12, 13, 12, 11, 38, 9, 52, 16, 16, 52, 9, 38, 11, 12, 13, 14, 13, 12

Offset: 0

Antti Karttunen, May 06 2003

Note that together with A082858 this forms a distributive lattice, thus it is possible to compute this function also with the binary OR-operation (A003986) with the help of appropriate mapping functions. I.e. we have A(x,y) = A082857(A003986(A082856(x), A082856(y))).

Antti Karttunen, Alternative Catalan Orderings (with the complete Scheme source)
Index entries for sequences related to lattices

The lower/upper triangular region: A082861. Cf. A072764, A080300, A025581, A002262.

A126309 A014486-index for the Dyck path "compressed" from the n-th Dyck path encoded by A014486(n).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

According to Vaillé, the concept of "compression d'un pont" was introduced by Poupard, in "Sur les quasi-ponts" paper. In effect, the operation removes all the peaks /\ from the Dyck path.

			A014486(4) encodes the Dyck path /\/\/\, of which, when all the peaks are removed, nothing remains, thus a(4)=0. A014486(18) encodes the Dyck path:
....../\
.../\/..\
../......\,
which, after the peaks are removed, results
.../\,
../..\ encoded by A014486(3), thus a(18)=3.

Y. Poupard, Sur les quasi-ponts, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 32, Paris, 1979, pp. 3-20.
J. Vaillé, Une Bijection Explicative de Plusieurs Propriétés Remarquables des Ponts, European J. Combin. 18 (1997), no. 1, 117-124.

Cf. A014486, A080300, A125985, A125986, A126308, A126310.

a(n) = A080300(A126308(A014486(n))).

a(n) = A125985(A126310(A125986(n))).

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Original entry on oeis.org

1, 0, 2, 0, 3, 4, 0, 0, 5, 6, 0, 0, 6, 7, 9, 0, 0, 0, 8, 10, 11, 0, 0, 0, 0, 11, 12, 14, 0, 0, 0, 0, 14, 13, 15, 16, 0, 0, 0, 0, 0, 15, 16, 17, 19, 0, 0, 0, 0, 0, 0, 19, 18, 20, 23, 0, 0, 0, 0, 0, 0, 0, 20, 21, 24, 25, 0, 0, 0, 0, 0, 0, 0, 0, 22, 25, 26, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 27, 29, 30

Offset: 0

Antti Karttunen, Dec 22 2008

Note: the leaf positions are indexed so that the rightmost one in the tree is leaf 0, etc., up to the leftmost one, which is the leaf with index A072643(x). In this manner, terms on each row stay in monotone order. Row n (starting from row 0) contains A072643(n)+1 nonzero terms and then an infinite number of zeros after that. A153249 gives only the nonzero terms. Can be used to compute "fleeing tree" sequences for Catalan bijections. See comments at A153246.

			Top left corner of array:
1,  0,  0,  0,  0, ...
2,  3,  0,  0,  0, ...
4,  5,  6,  0,  0, ...
6,  7,  8,  0,  0, ...
9,  10, 11, 14, 0, ...
11, 12, 13, 15, 0, ...
14, 15, 16, 19, 0, ...
By inserting a bud (\/) at leaf position 1 of binary tree A014486(2) (leaf positions numbered for clarification):
....1....0
.....\../
..2...\/
...\../
....\/
we obtain a binary tree:
.......
.\../..
..\/...
...\../
....\/
.\../
..\/
which is the 5th binary tree encoded by A014486. Thus A(2,1)=5.

A. Karttunen, Table of n, a(n) for n = 0..1274

Cf. A002262, A025581.

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

A154472 a(n) = A126309(A154471(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

A209640 Global ranking function for restricted totally balanced binary strings given in A209641.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Scheme

A218783 A014486-indices for the compact representation of Beanstalk-tree, with the lesser numbers coming to the right hand side.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A080970 A014486-indices of the trees whose interior zigzag-tree (Stanley's c) is not branch-reduced (in the sense defined by Donaghey).

Views

Author

Keywords

Links

Crossrefs

Formula

A080980 A014486-indices of the trees whose interior zigzag-tree (Stanley's c) is branch-reduced (in the sense defined by Donaghey).

Views

Author

Keywords

Links

Crossrefs

A082857 Inverse function of N -> N injection A082856.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A082860 Array A(x,y): the least common supertree (union) of the binary trees x and y, (x,y) running as (0,0),(1,0),(0,1),(2,0),(1,1),(0,2) and each index referring to a binary tree encoded by A014486(j).

Views

Author

Keywords

Comments

Links

Crossrefs

A126309 A014486-index for the Dyck path "compressed" from the n-th Dyck path encoded by A014486(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A153250 Array A(x,y): A(0,0), A(1,0), A(0,1), A(2,0), A(1,1), A(0,2), ... formed by growing a bud (a single V-node) on the y-th leaf of the binary tree A014486(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica