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,2

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

F. Disanto and N. 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.

N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.

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

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 *)

Prog

(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
(Magma) [2*(5*n+3)* Binomial(2*n+1, n)/((n+2)*(n+3)): n in [0..30]]; // 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

Crossrefs

Cf. A000245, A000108, A306423.

Partial sums of A071736.

Sequence in context: A274952 A010900 A175005 * A082989 A267240 A192802

Adjacent sequences: A070028 A070029 A070030 * A070032 A070033 A070034

Keyword

nonn

Author

N. J. A. Sloane, Jun 06 2002

Status

approved