

A002057


Fourth convolution of Catalan numbers: 4*binomial(2n+3,n)/(n+4).
(Formerly M3483 N1415)


66



1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, 326876, 1188640, 4345965, 15967980, 58929450, 218349120, 811985790, 3029594040, 11338026180, 42550029600, 160094486370, 603784920024, 2282138106804, 8643460269248, 32798844771700, 124680849918352
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) is sum of the (flattened) list obtained by the iteration of: replace each integer k with the list 0,...,k+1 on the starting value 0. Length of this list is Catalan(n) or A000108.  Wouter Meeussen, Nov 11 2001
a(n2) is the number of nth generation vertices in the tree of sequences with unit increase labeled by 3 (cf. Zoran Sunic reference).  Benoit Cloitre, Oct 07 2003
Number of standard tableaux of shape (n+2,n1).  Emeric Deutsch, May 30 2004
a(n) = CatalanNumber(n+3)  2*CatalanNumber(n+2). Proof. From its definition as a convolution of Catalan numbers, a(n) counts lists of 4 Dyck paths of total size (semilength) = n. Connect the 4 paths by 3 upsteps (U) and append 3 downsteps (D). This is a reversible procedure. So a(n) is also the number of Dyck (n+3)paths that end DDD (D for downstep). Let C(n) denote CatalanNumber(n) (A000108). Since C(n+3) is the total number of Dyck (n+3)paths and C(n+2) is the number that end UD, we have (*) C(n+3)  C(n+2) is the number of Dyck (n+3)paths that end DD. Also, (**) C(n+2) is the number of Dyck (n+3)paths that end UDD (change the last D in a Dyck (n+2)path to UDD). Subtracting (**) from (*) yields a(n) = C(n+3)  2C(n+2) as claimed.  David Callan, Nov 21 2006
Convolution square of the Catalan sequence without one of the initial "1"'s: (1 + 4x + 14x^2 + 48x^3 + ...) = (1/x^2) * square(x + 2x^2 + 5x^3 + 14x^4 + ...)
a(n) is the number of binary trees with n+3 internal nodes in which both subtrees of the root are nonempty. Cf. A068875 [Sedgewick and Flajolet].  Geoffrey Critzer, Jan 05 2013
With offset 4, a(n) is the number of permutations on {1,2,...,n} that are 123avoiding, i.e., do not contain a threeterm monotone subsequence, for which the first ascent is at positions (4,5); for example, there are 48 123avoiding permutations on n=7 for which the first ascent is at spots (4,5). See Connolly link. There it is shown in general that the kth Catalan Convolution is the number of 123avoiding permutations for which the first ascent is at (k, k+1). (For n=k, the first ascent is defined to be at positions (k,k+1) if the permutation is the decreasing permutation with no ascents.)  Anant Godbole, Jan 17 2014
With offset 4, a(n) is the number of permutations on {1,2,...,n} that are 123avoiding and for which the integer n is in the 4th spot; see Connolly link.  Anant Godbole, Jan 17 2014
a(n) is the number of NorthEast lattice paths from (0,0) to (n+2,n+2) that have exactly one east step below the subdiagonal y = x1. Details can be found in Section 3.1 in Pan and Remmel's link.  Ran Pan, Feb 04 2016
a(n) is the number of NorthEast lattice paths from (0,0) to (n+2,n+2) that bounce off the diagonal y = x to the right exactly once but do not bounce off y = x to the left. Details can be found in Section 4.2 in Pan and Remmel's link.  Ran Pan, Feb 04 2016
a(n) is the number of NorthEast lattice paths from (0,0) to (n+2,n+2) that horizontally cross the diagonal y = x exactly once but do not cross the diagonal vertically. Details can be found in Section 4.3 in Pan and Remmel's link.  Ran Pan, Feb 04 2016


REFERENCES

Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_4(z).
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., Vol. 14 (1922), pp. 5562, 122138 and 143146.
Robert Sedgewick and Phillipe Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 225.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

T. D. Noe and Fung Lam, Table of n, a(n) for n = 0..1000 (first 100 terms were computed by T. D. Noe)
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multirooted plane trees, arXiv:2301.09765 [math.CO], 2023.
JeanLuc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Julia E. Bergner, Cedric Harper, Ryan Keller and Mathilde RosiMarshall, Action graphs, planar rooted forests, and selfconvolutions of the Catalan numbers, arXiv:1807.03005 [math.CO], 2018.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Bounce statistics for rational lattice paths, arXiv:1707.09918 [math.CO], 2017, p. 9.
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237262 = Collected Mathematical Papers. Vols. 113, Cambridge Univ. Press, London, 18891897, Vol. 13, pp. 93ff.
Giulio Cerbai, Anders Claesson and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
GiSang Cheon, Hana Kim and Louis W. Shapiro, Mutation effects in ordered trees, arXiv preprint arXiv:1410.1249 [math.CO], 2014 (see page 4).
Samuel Connolly, Zachary Gabor and Anant Godbole, The location of the first ascent in a 123avoiding permutation, arXiv:1401.2691 [math.CO], 2014.
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., Vol. 35, No. 4 (1995) pp. 743751.
S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., Vol. 35, No. 4 (1995) pp. 743751. [Annotated scanned copy]
Harold M. Edwards, A Normal Form for Elliptic Curves, Bulletin of the A.M.S., Vol. 44, No. 3 (2007), pp. 393422.
Richard K. Guy, Letter to N. J. A. Sloane, May 1990
Richard K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seq., Vol. 3 (2000), Article 00.1.6.
V. E. Hoggatt, Jr., 7page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., Vol. 14, No. 5 (1976), pp. 395405.
C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., Vol. 14 (1922), pp. 5562, 122138 and 143146. [Annotated scanned copy]
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart., Vol. 38, No. 5 (2000), pp. 408419. See Eq.(3).
KyuHwan Lee, Sejin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
Nik Lygeros and Olivier Rozier, A new solution to the equation tau(rho) == 0 (mod p), J. Int. Seq., Vol. 13 (2010), Article 10.7.4.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
John Riordan, Letter to N. J. A. Sloane, Nov 10 1970.
John Riordan, Letter of 04/11/74.
L. W. Shapiro, A Catalan triangle, Discrete Math., Vol. 14, No. 1 (1976), pp. 8390.
L. W. Shapiro, A Catalan triangle, Discrete Math., Vol. 14, No. 1 (1976), pp. 8390. [Annotated scanned copy]
Zoran Sunic, Self describing sequences and the Catalan family tree, Elect. J. Combin., Vol. 10 (2003), Article N5.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
Steven J. Tedford, Combinatorial interpretations of convolutions of the Catalan numbers, Integers, Vol. 11 (2011), Article A3.
WenJin Woan, Lou Shapiro and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n2}, Amer. Math. Monthly, Vol. 104, No. 10 (1997), pp. 926931.


FORMULA

a(n) = A033184(n+4, 4) = 4*binomial(2*n+3, n)/(n+4) = 2*(n+1)*A000108(n+2)/(n+4).
G.f.: c(x)^4 with c(x) g.f. of A000108 (Catalan).
Row sums of A145596. Column 4 of A033184. By specializing the identities for the row polynomials given in A145596 we obtain the results a(n) = Sum_{k = 0..n} (1)^k*binomial(n+1,k+1)*a(k)*4^(nk) and a(n) = Sum_{k = 0..floor(n/2)} binomial(n+1,2*k+1) * Catalan(k+1) * 2^(n2*k). From the latter identity we can derive the congruences a(2n+1) == 0 (mod 4) and a(2n) == Catalan(n+1) (mod 4). It follows that a(n) is odd if and only if n = (2^m  4) for some m >= 2.  Peter Bala, Oct 14 2008
Let A be the Toeplitz matrix of order n defined by: A[i,i1]=1, A[i,j]=Catalan(ji), (i<=j), and A[i,j]=0, otherwise. Then, for n>=3, a(n3) = (1)^(n3) * coeff(charpoly(A,x), x^3).  Milan Janjic, Jul 08 2010
G.f.: (1sqrt(14*x) + 2*x*(2+sqrt(14*x) + x))/(2*x^4).  Harvey P. Dale, May 05 2011
a(n+1) = A214292(2*n+4,n).  Reinhard Zumkeller, Jul 12 2012
Dfinite with recurrence: (n+4)a(n) = 8*(2*n1)*a(n3)  20*(n+1)*a(n2) + 4*(2*n+5)*a(n1).  Fung Lam, Jan 29 2014
Dfinite with recurrence: (n+4)*a(n)  2*(3*n+7)*a(n1) + 4*(2*n+1)*a(n2) = 0.  R. J. Mathar, Jun 03 2014
Asymptotics: a(n) ~ 4^(n+3)/sqrt(4*Pi*n^3).  Fung Lam, Mar 31 2014
a(n) = 32*4^n*Gamma(5/2+n)*(1+n)/(sqrt(Pi)*Gamma(5+n)).  Peter Luschny, Dec 14 2015
a(n) = C(n+1)  2*C(n) where C is Catalan number A000108. Yuchun Ji, Oct 18 2017 [Note: Offset is off by 2]
E.g.f.: d/dx ( 2*exp(2*x)*BesselI(2,2*x)/x ).  Ilya Gutkovskiy, Nov 01 2017
From Bradley Klee, Mar 05 2018: (Start)
With F(x) = 16/(1+sqrt(14*x))^4 g.f. of A002057, xi(x) = F(x/4)*(x/4)^2, K(16*x) = 2F1(1/2,1/2;1;16*x) g.f. of A002894, q(x) g.f. of A005797, and q'(x) g.f. of A274344:
K(x) = (1+sqrt(xi(x)))*K(xi(x)).
2*K(1x) = (1+sqrt(xi(x)))*K(1xi(x)).
q(x) = sqrt(q(xi(16*x)/16)) = q'(xi(16*x)/16)/sqrt(xi(16*x)/16). (End)
From Amiram Eldar, Jan 02 2022: (Start)
Sum_{n>=0} 1/a(n) = 5/4 + Pi/(18*sqrt(3)).
Sum_{n>=0} (1)^n/a(n) = 183*log(phi)/(25*sqrt(5))  77/100, where phi is the golden ratio (A001622). (End)
a(n) = Integral_{x=0..4} x^n*W(x) dx where W(x) = x^(3/2)*(1  x/2)*sqrt(4  x)/Pi, defined on the open interval (0,4).  Karol A. Penson, Nov 13 2022


EXAMPLE

From Peter Bala, Apr 14 2017: (Start)
This sequence appears on the main diagonal of a generalized Catalan triangle. Construct a lower triangular array (T(n,k)), n,k >= 0 by placing the sequence [0,0,0,1,1,1,1,...] in the first column and then filling in the remaining entries in the array using the rule T(n,k) = T(n,k1) + T(n1,k). The resulting array begins
n\k 0 1 2 3 4 5 6 7 ...
+
0  0
1  0 0
2  0 0 0
3  1 1 1 1
4  1 2 3 4 4
5  1 3 6 10 14 14
6  1 4 10 20 34 48 48
7  1 5 15 35 69 117 165 165
...
(see Tedford 2011; this is essentially the array C_4(n,k) in the notation of Lee and Oh). Compare with A279004. (End)


MAPLE

a := n > 32*4^n*GAMMA(5/2+n)*(1+n)/(sqrt(Pi)*GAMMA(5+n)):
seq(a(n), n=0..23); # Peter Luschny, Dec 14 2015
A002057List := proc(m) local A, P, n; A := [1]; P := [1, 1, 1];
for n from 1 to m  2 do P := ListTools:PartialSums([op(P), P[1]]);
A := [op(A), P[1]] od; A end: A002057List(27); # Peter Luschny, Mar 26 2022


MATHEMATICA

Table[Plus@@Flatten[Nest[ #/.a_Integer:> Range[0, a+1]&, {0}, n]], {n, 0, 10}]
Table[4 Binomial[2n+3, n]/(n+4), {n, 0, 30}] (* or *) CoefficientList[ Series[ (1Sqrt[14 x]+2 x (2+Sqrt[14 x]+x))/(2 x^4), {x, 0, 30}], x] (* Harvey P. Dale, May 05 2011 *)


PROG

(PARI) {a(n) = if( n<0, 0, n+=2; 2*binomial(2*n, n2) / n)}; /* Michael Somos, Jul 31 2005 */
(PARI) x='x+O('x^100); Vec((1(14*x)^(1/2)+2*x*(2+(14*x)^(1/2)+x))/(2*x^4)) \\ Altug Alkan, Dec 14 2015
(Magma) [4*Binomial(2*n+3, n)/(n+4): n in [0..30]]; // Vincenzo Librandi, Feb 04 2016 *)
(GAP) List([0..25], n>4*Binomial(2*n+3, n)/(n+4)); # Muniru A Asiru, Mar 05 2018
(SageMath) [2*(n+1)*catalan_number(n+2)/(n+4) for n in (0..30)] # G. C. Greubel, May 27 2022


CROSSREFS

T(n, n+4) for n=0, 1, 2, ..., array T as in A047072. Also a diagonal of A059365 and of A009766.
Cf. A001003.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A000108, A000245, A000344, A003517, A000588, A003518, A003519, A001392, A001622.
Cf. A145596 (row sums), A279004.
Sequence in context: A094827 A094667 A099376 * A047048 A071745 A071749
Adjacent sequences: A002054 A002055 A002056 * A002058 A002059 A002060


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



