A006632 a(n) = 3*binomial(4*n-1,n-1)/(4*n-1). (Formerly M2997)

1, 3, 15, 91, 612, 4389, 32890, 254475, 2017356, 16301164, 133767543, 1111731933, 9338434700, 79155435870, 676196049060, 5815796869995, 50318860986108, 437662920058980, 3824609516638444, 33563127932394060, 295655735395397520, 2613391671568320765

Offset

1,2

Comments

a(n) is the number of ordered trees (A000108) with 3n-1 edges in which every non-leaf vertex has exactly two leaf children (no restriction on non-leaf children). For example, a(2) counts the 3 trees

\/......\/......\/

.\|/...\|/....\|/ . - David Callan, Aug 22 2014

a(n) is the number of lattice paths from (0,0) to (3n,n) using only the steps (1,0) and (0,1) and which are strictly below the line y = x/3 except at the path's endpoints. - Lucas A. Brown, Aug 21 2020

This is instance k = 3 of the family {c(k, n)}_{n>=1} given in a comment in A130564. - Wolfdieter Lang, Feb 04 2024

References

H. M. Finucan, Some decompositions of generalized Catalan numbers, pp. 275-293 of Combinatorial Mathematics IX. Proc. Ninth Australian Conference (Brisbane, August 1981). Ed. E. J. Billington, S. Oates-Williams and A. P. Street. Lecture Notes Math., 952. Springer-Verlag, 1982.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..22.

O. Aichholzer, A. Asinowski and T. Miltzow, Disjoint compatibility graph of non-crossing matchings of points in convex position, arXiv preprint arXiv:1403.5546 [math.CO], 2014.

Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.

Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 438

Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.

J. Sawada, J. Sears, A. Trautrim, and A. Williams, Demystifying our Grandparent's De Bruijn Sequences with Concatenation Trees, arXiv:2308.12405 [math.CO], 2023.

Formula

a(n) = binomial(4*n-1, n)/(4*n-1) = 3*binomial(4*n-2, n-1) - binomial(4*n-2, n). - David Callan, Sep 15 2004

G.f.: g^3 where g = 1+x*g^4 is the g.f. of A002293. - Mark van Hoeij, Nov 11 2011

a(n) = (3/4)*binomial(4*n,n)/(4*n-1). - Bruno Berselli, Jan 17 2014

From Wolfdieter Lang, Feb 06 2020: (Start)

G.f.: (3/4)*(1 - hypergeom([-1, 1, 2]/4, [1, 2]/3, (4^4/3^3)*x)).

E.g.f.: (3/4)*(1 - hypergeom([-1, 1, 2]/4, [1, 2, 3]/3, (4^4/3^3)*x)). (End)

D-finite with recurrence 3*n*(3*n-1)*(3*n-2)*a(n) -8*(4*n-5)*(4*n-3)*(2*n-1)*a(n-1)=0. - R. J. Mathar, May 07 2021

a(n) = (2n-1)*A000260(n). - F. Chapoton, Jul 15 2021

G.f. A(x) satisfies: A(x) = x / (1 - A(x))^3. - Ilya Gutkovskiy, Nov 03 2021

Maple

A006632:=n->3*binomial(4*n-1, n-1)/(4*n-1): seq(A006632(n), n=1..30); # Wesley Ivan Hurt, Oct 23 2017

Mathematica

InverseSeries[Series[y*(1-y)^3, {y, 0, 24}], x] (* then A(x)=y(x) *) (* Len Smiley, Apr 07 2000 *)
a[ n_] := If[ n < 1, 0, Binomial[4 n - 2, n - 1] / n]; (* Michael Somos, Aug 22 2014 *)

Prog

(PARI) a(n) = 3*binomial(4*n-1, n-1)/(4*n-1) \\ Felix Fröhlich, Oct 23 2017

Crossrefs

A112385 divided by 2.

Cf. A000108, A000260, A002293, A006013, A069271, A120588.

Cf. A130564.

Sequence in context: A371435 A366090 A171790 * A366056 A369161 A159928

Adjacent sequences: A006629 A006630 A006631 * A006633 A006634 A006635

Keyword

nonn,easy

Author

Simon Plouffe

Status

approved