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
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
KEYWORD
nonn,easy
AUTHOR
STATUS
approved