A070031 Expansion of (1+x*C)*C^3, where C = (1-sqrt(1-4*x))/(2*x) is g.f. for Catalan numbers, A000108.

1, 4, 13, 42, 138, 462, 1573, 5434, 19006, 67184, 239666, 861764, 3120180, 11366370, 41630805, 153216570, 566343030, 2101610280, 7826451270, 29240172780, 109566326220, 411671536380, 1550629453698, 5854180360932, 22148866939948, 83965042615552, 318895250752708

Offset: 0

Author

N. J. A. Sloane, Jun 06 2002

Keywords

• nonn

Comments

Counts the large components twice and the small components once in all Dyck (n+1)-paths, i.e., twice the number of returns less the number of hills = 2*A000245(n+1) - A000108(n+1). - David Scambler, Oct 08 2012

For n>=2, the number of coalescent histories for matching gene tree and species trees with a pseudocaterpillar shape that has n+3 leaves (Rosenberg 2007, Corollary 3.9). - Noah A Rosenberg, Feb 14 2019

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Filippo Disanto and Noah A. Rosenberg, Asymptotic properties of the number of matching coalescent histories for caterpillar-like families of species trees, IEEE/ACM Trans. Comput. Biol. Bioinformat. 13 (2016), 913-925. See Eq. 30.
• Manuel Flores, Yuta Kimura, and Baptiste Rognerud, Combinatorics of quasi-hereditary structures, arXiv:2004.04726 [math.RT], 2020.
• Anna Rodriguez Rasmussen, Exact Borel subalgebras of quasi-hereditary monomial algebras, arXiv:2504.01706 [math.RT], 2025. See p. 38.
• Noah A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.

Crossrefs

Cf. A000245, A000108, A126079, A306423.

Partial sums of A071736.

Programs

Magma

[2*(5*n+3)* Binomial(2*n+1, n)/((n+2)*(n+3)): n in [0..30]]; // G. C. Greubel, Feb 14 2019

Maple

gf := ((3*x - 2)*sqrt(1 - 4*x) + 2*x^2 - 7*x + 2)/(2*x^3): ser := series(gf, x, 32): seq(coeff(ser, x, n), n = 0..9); # Peter Luschny, Jun 17 2022

Mathematica

Table[2^(n + 1)*(5*n + 3)*(2*n + 1)!!/(n + 3)!, {n, 0, 27}] (* Jean-François Alcover, Nov 07 2016 *)

PARI

my(x='x+O('x^30)); Vec((3-sqrt(1-4*x))*(1-sqrt(1-4*x))^3/(16*x^3)) \\ G. C. Greubel, Feb 14 2019

Sage

((3-sqrt(1-4*x))*(1-sqrt(1-4*x))^3/(16*x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 14 2019

Formula

a(n) = 2*(5*n+3)*binomial(2*n+1, n)/((n+2)*(n+3)). - Emeric Deutsch, Dec 13 2002

a(n) = leftmost term of M^n*V, M = an infinite tridiagonal matrix with all 1's in the super and subdiagonals and all 2's in the main diagonal; with the rest zeros. V = Vector [1,2,0,0,0,...]. - Gary W. Adamson, Jun 16 2011

a(n) = 2*A000245(n+1) - A000108(n+1). - David Scambler, Oct 08 2012

D-finite with recurrence: 2*(n+3)*a(n) +(-11*n-15)*a(n-1) +6*(2*n-1)*a(n-2)=0. - R. J. Mathar, Aug 25 2013

G.f.: (3-sqrt(1-4*x))*(1-sqrt(1-4*x))^3/(16*x^3). - G. C. Greubel, Feb 14 2019

From Mélika Tebni, Sep 03 2024: (Start)

a(n) = A000108(n+1) - A126079(n+3).

E.g.f.: 4*exp(2*x)*(BesselI(0, 2*x) - 3/(4*x)*BesselI(1, 2*x) - (1-1/x)*BesselI(2, 2*x)). (End)