Louis Shapiro - cp's OEIS frontend

A228343 The number of ordered trees with bicolored single edges on the boundary.

1, 2, 5, 15, 50, 175, 625, 2251, 8142, 29544, 107538, 392726, 1439204, 5292833, 19533241, 72333107, 268728214, 1001448308, 3742866166, 14026901282, 52701685564, 198481560878, 749170991770, 2833635556670, 10738689128460, 40770816357920, 155056284790340, 590644481896972

Offset: 0

Louis Shapiro, Aug 20 2013

nonn

			When n=3 the five trees contribute as follows: UUUDDD 8; UUDDUD, UDUUDD,UUDUDD 2 each; and UDUDUD just 1.

Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8; preprint, 2014.

Cf. A000108, A228197.

Table[FullSimplify[I*2^n - 5/2*Gamma[3+2*n] * HypergeometricPFQRegularized[{1,3/2+n,2+n},{n,5+n},2]],{n,0,20}] (* Vaclav Kotesovec, Jan 31 2014 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = (1+x^2*C^5)/(1-2*x);
Vec(gf) \\ Joerg Arndt, Aug 21 2013

G.f.: (1+x^2*C^5)/(1-2*x) where C is the Catalan number generating function (cf. A000108).
D-finite with recurrence: -(n+3)*(n-2)*a(n) +6*(n^2-2)*a(n-1) -4*n*(2*n-1)*a(n-2)=0. - R. J. Mathar, Aug 25 2013
a(n) -2*a(n-1) = A000344(n). - R. J. Mathar, Aug 25 2013
a(n) ~ 5 * 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 31 2014

A228180 The number of single edges on the boundary of ordered trees with n edges.

Original entry on oeis.org

0, 1, 2, 6, 19, 61, 199, 661, 2234, 7668, 26674, 93858, 333524, 1195288, 4315468, 15681838, 57312643, 210529213, 776872243, 2878482523, 10704933793, 39945106573, 149511432793, 561182969173, 2111812422871, 7965992783803, 30114859723751, 114079902339303, 432975153092011, 1646215731143667

Offset: 0

Louis Shapiro, Aug 20 2013

nonn

Apparently the partial sums of A070031. - R. J. Mathar, Aug 25 2013

			For n=3 the UUUDDD has 3 single edges while UUDDUD, UDUUDD and UUDUDD each have one single edge, i.e., an edge with no siblings.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8; preprint, 2014.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.

Cf. A000108, A228178.

CoefficientList[Series[(x*(1-Sqrt[1-4*x])/(2*x) + 2*x^3*((1-Sqrt[1-4*x])/(2*x))^4)/(1-x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2014 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = (x*C+2*x^3*C^4)/(1-x);
concat([0], Vec(gf) ) \\ Joerg Arndt, Aug 21 2013

G.f.: (x*C+2*x^3*C^4)/(1-x) where C is the g.f. for the Catalan numbers A000108.
Conjecture: 2*(n+1)*a(n) +(-13*n+5)*a(n-1) +(23*n-37)*a(n-2) +6*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Aug 25 2013
a(n) ~ 5*4^n / (3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 01 2014

A228178 The number of boundary edges for all ordered trees with n edges.

Original entry on oeis.org

1, 4, 14, 47, 157, 529, 1805, 6238, 21812, 77062, 274738, 987276, 3572568, 13007398, 47617798, 175171543, 647227453, 2400843823, 8937670603, 33380986153, 125045165773, 469700405533, 1768752809221, 6676088636479, 25252913322299, 95712549267151, 363441602176007, 1382467779393307, 5267219868722803

Offset: 0

Louis Shapiro, Aug 20 2013

nonn

Apparently partial sums of A071722. - R. J. Mathar, Aug 25 2013

			The  5 ordered trees with 3 edges have 3,3,2,3,3 boundary edges with UDUDUD having but 2.

Cf. A000108.

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = (x*C+2*x^2*C^4)/(1-x);
Vec(gf) \\ Joerg Arndt, Aug 21 2013

G.f.: (x*C+2*x^2*C^4)/(1-x) where C is the g.f. for the Catalan numbers A000108.

Conjecture: 2*(n+3)*a(n) +2*(-7*n-11)*a(n-1) +(29*n+7)*a(n-2) +(-21*n+19)*a(n-3) +2*(2*n-5)*a(n-4)=0. - R. J. Mathar, Aug 25 2013

A228404 The number of complete binary trees with bicolored twigs. A twig is a vertex with one child on the boundary and the other child having no descendants.

Original entry on oeis.org

1, 2, 8, 24, 76, 249, 836, 2860, 9932, 34918, 124032, 444448, 1604664, 5831765, 21316860, 78319140, 289064460, 1071275370, 3984871440, 14872552560, 55678270440, 209027020410, 786750047304, 2968257334104, 11223268563896, 42522737574604, 161415556062656, 613813414982656

Offset: 0

Louis Shapiro, Aug 21 2013

nonn

			For n = 2 there are two complete binary trees. Both consist of two twigs so can be colored 4 ways each.

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).

Without the bicoloring A228403 is the result.

Cf. A000108.

[1,2] cat [Catalan(n+2) -2*Catalan(n+1) +2*Catalan(n): n in [2..30]]; // G. C. Greubel, May 03 2021

Table[If[n<2, n+1, CatalanNumber[n+2] -2*CatalanNumber[n+1] +2*CatalanNumber[n]], {n,0,30}] (* G. C. Greubel, May 03 2021 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = 1 - x + 2*x*C^2 + x*C^4;
Vec(gf) \\ Joerg Arndt, Aug 22 2013

[1,2]+[catalan_number(n+2) -2*catalan_number(n+1) +2*catalan_number(n) for n in (2..30)] # G. C. Greubel, May 03 2021

G.f.: 1 - x + 2*x*C^2 + x*C^4 where C is the g.f. for the Catalan numbers A000108.
Conjecture: -5*(n+3)*(n-2)*a(n) +5*(-n^2-n+18)*a(n-1) +5*(-n^2-n+48)*a(n-2) +(-5*n^2+20029*n+720)*a(n-3) +(-5*n^2-104153*n+186654)*
a(n-4) +(-5*n^2 +130153*n -508806)*a(n-5) +13650*(2*n-11)*(n-7)*a(n-6) = 0. - R. J. Mathar, Aug 08 2015
From G. C. Greubel, May 03 2021: (Start)
a(n) = C(n+2) - 2*C(n+1) + 2*C(n) with a(0) = 1, a(1) = 2, and C(n) = A000108(n).
E.g.f.: (-x^2*(1+x) + 2*exp(2*x)*(x*(1+x)*BesselI(0, 2*x) - (1+x^2)*BesselI(1, 2*x)))/x^2. (End)

A228403 The number of boundary twigs for complete binary twigs. A twig is a vertex with one edge on the boundary and only one other descendant.

Original entry on oeis.org

1, 4, 10, 28, 84, 264, 858, 2860, 9724, 33592, 117572, 416024, 1485800, 5348880, 19389690, 70715340, 259289580, 955277400, 3534526380, 13128240840, 48932534040, 182965127280, 686119227300, 2579808294648, 9723892802904, 36734706144304, 139067101832008, 527495903500720, 2004484433302736

Offset: 1

Louis Shapiro, Aug 21 2013

nonn

Essentially twice the Catalan numbers (A000108).

A068875 without the 2. - R. J. Mathar, Aug 24 2013

			For n  = 3 there are 5 complete binary trees. Of these UUUDUDDUDDUD consists of three twigs as does its mirror image UDUUDUUDUDDD. UUDUUDUDDDUD and UDUUUDUDDUDD each have one twig and UUDUDDUUDUDD has two.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Rest[CoefficientList[Series[(1-Sqrt[1-4*x]-2*x-x^2)/x,{x,0,20}],x]] (* Vaclav Kotesovec, Aug 23 2013 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = 2*x*C^2 - x;
Vec(gf) \\ Joerg Arndt, Aug 22 2013

from itertools import accumulate
def A228403_list(size):
    if size < 1: return []
    L, accu = [1], [2]
    for _ in range(size-1):
        accu = list(accumulate(accu + [accu[-1]]))
        L.append(accu[-1])
    return L
print(A228403_list(29)) # Peter Luschny, Apr 25 2016

G.f.: 2*x*C^2 - x where C is the g.f. for the Catalan numbers

a(n) ~ 2^(2*n+1)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 23 2013

A228197 Number of n-edge ordered trees with bicolored boundary edges.

Original entry on oeis.org

1, 2, 8, 36, 160, 692, 2928, 12200, 50304, 205940, 838928, 3405496, 13788736, 55723592, 224863712, 906365136, 3649978880, 14687731572, 59067989072, 237424661016, 953914608320, 3831159414552, 15381896102432, 61739966366256, 247750559632640, 993955865320392, 3986890331450528

Offset: 0

Louis Shapiro, Aug 20 2013

nonn

			When n=3 edges there are A000108(3)= 5 ordered trees. Four of these consist of three boundary edges each contributing 2^3 trees to the count. The last, UDUDUD, has two boundary edges giving the last 2^2 trees for a total of 36.

G. C. Greubel, Table of n, a(n) for n = 0..1000
D. E. Davenport, L. K. Pudwell, L. W. Shapiro, L. C. Woodson, The Boundary of Ordered Trees, 2014.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
E. Deutsch, L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Disc. Math. 256 (2002) 655-670.

Cf. A000108, A000984, A228178, A228180.

CoefficientList[Series[(1-2*x-2*x*Sqrt[1-4*x])/((4*x-1)*(2*x-1)), {x, 0, 20}], x] (* Vaclav Kotesovec, Aug 23 2013 *)
Table[2^(2n)-2^n*JacobiP[n-1,1/2,-n,3],{n,0,20}] (* Benedict W. J. Irwin, Sep 16 2016 *)

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
B = (1-4*x)^(-1/2); \\ central binomial coefficients
gf = (1+4*x^2*B^2*C)/(1-2*x);
Vec(gf) \\ Joerg Arndt, Aug 21 2013

G.f.: (1+4*x^2*B^2*C)/(1-2*x), C is the Catalan g.f. (see A000108) and B =(1-4*x)^(-1/2) is the g.f. for the central binomial coefficients (A000984).
a(n) ~ 4^n * (1-1/(sqrt(Pi*n))). - Vaclav Kotesovec, Aug 23 2013
Conjecture: (-n+1)*a(n) +2*(5*n-8)*a(n-1) +4*(-8*n+17)*a(n-2) +16*(2*n-5)*a(n-3)=0. - R. J. Mathar, Aug 25 2013
a(n) = 2^(2*n)-2^n*JacobiP(n-1,1/2,-n,3) = 2^(2*n)-2*A082590(n-1), which satisfies the above conjecture. - Benedict W. J. Irwin, Sep 16 2016

A125267 Number of Motzkin paths with no peaks and with level steps at height 0 having three colors except that consecutive level steps at height 0 must have different colors.

Original entry on oeis.org

1, 3, 6, 13, 30, 71, 171, 417, 1026, 2542, 6333, 15849, 39813, 100329, 253518, 642117, 1629726, 4143857, 10553511, 26916426, 68739015, 175752268, 449846001, 1152528593, 2955487605, 7585165701, 19481930556, 50073211027, 128784497466, 331426205715, 853409723277

Offset: 0

Louis Shapiro and Gi-Sang Cheon, Jan 15 2007

nonn

This generating function, together with the multiplier function -xg(x), produce an involution in the Riordan group.

			a(3) = 13 since there are 12 = 3*2*2 paths that stay at level 0 and one path ULD that goes above level 0.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

Cf. A004148.

CoefficientList[Series[(((1 - x + x^2) - Sqrt[(1 - x + x^2)^2 - 4 x^2])/(2*x^2)*(1 + x))/(1 - x*((1 - x + x^2) - Sqrt[(1 - x + x^2)^2 - 4 x^2])/(2*x^2)), {x, 0, 30}], x] (* Wesley Ivan Hurt, Jan 10 2017 *)

G.f.: (g(x)*(1+x))/(1-x*g(x)) where g(x)=((1-x+x^2)-sqrt((1-x+x^2)^2-4x^2))/(2*x^2).
Conjecture: -(n+1)*(n-2)*a(n) +2*(n^2-n-3)*a(n-1) +(n^2-3*n+8)*a(n-2) +2*(n^2-5*n+3)*a(n-3) -(n-1)*(n-4)*a(n-4)=0. - R. J. Mathar, Jun 17 2016
a(n) ~ 5^(1/4) * phi^(2*n+1) / sqrt(Pi*n), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 29 2022

A124501 Number of 1-2-3-4-5-6 trees with n edges and with thinning limbs. A 1-2-3-4-5-6 tree is an ordered tree with vertices of outdegree at most 6. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 68, 186, 522, 1479, 4246, 12289, 35872, 105411, 311662, 926270, 2765778, 8292296, 24953437, 75338686, 228140842, 692733127, 2108652750, 6433255041, 19668210742, 60247367313, 184879648441, 568281131800

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (A124499), k=5 (A124500), k=6 (this A124501), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124499, A124500, A124344.

{a(n)=local(k=6,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

A124500 Number of 1-2-3-4-5 trees with n edges and with thinning limbs. A 1-2-3-4-5 tree is an ordered tree with vertices of outdegree at most 5. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 67, 180, 495, 1375, 3871, 10993, 31493, 90843, 263686, 769466, 2256135, 6643082, 19634705, 58232350, 173242381, 516860717, 1546035258, 4635543843, 13929569399, 41943013047, 126532961332, 382396277940

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (A124499), k=5 (this A124500), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124499, A124501, A124344.

{a(n)=local(k=5,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

A124499 Number of 1-2-3-4 trees with n edges and with thinning limbs. A 1-2-3-4 tree is an ordered tree with vertices of outdegree at most 4. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Original entry on oeis.org

1, 1, 2, 4, 10, 24, 62, 160, 425, 1140, 3105, 8528, 23643, 66008, 185526, 524384, 1489810, 4251852, 12184745, 35048405, 101156752, 292865417, 850314803, 2475327088, 7223400899, 21126670372, 61920289652, 181838859665

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (this A124499), k=5 (A124500), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124500, A124501, A124344.

{a(n)=local(k=4,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

cp's OEIS Frontend

User: Louis Shapiro

A228343 The number of ordered trees with bicolored single edges on the boundary.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A228180 The number of single edges on the boundary of ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A228178 The number of boundary edges for all ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A228404 The number of complete binary trees with bicolored twigs. A twig is a vertex with one child on the boundary and the other child having no descendants.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A228403 The number of boundary twigs for complete binary twigs. A twig is a vertex with one edge on the boundary and only one other descendant.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Python

Formula

A228197 Number of n-edge ordered trees with bicolored boundary edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A125267 Number of Motzkin paths with no peaks and with level steps at height 0 having three colors except that consecutive level steps at height 0 must have different colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs