|
| |
|
|
A002057
|
|
Fourth convolution of Catalan numbers: a(n) = 4*binomial(2*n+3,n)/(n+4).
(Formerly M3483 N1415)
|
|
67
|
|
|
|
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(n-2) is the number of n-th 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,n-1). - 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 123-avoiding, i.e., do not contain a three-term monotone subsequence, for which the first ascent is at positions (4,5); for example, there are 48 123-avoiding 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 k-th Catalan Convolution is the number of 123-avoiding 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 123-avoiding 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 North-East lattice paths from (0,0) to (n+2,n+2) that have exactly one east step below the subdiagonal y = x-1. 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 North-East 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 North-East 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
Apparently also Young tableaux of (non-partition) shape [n+1, 1, 1, n+1], see example file. - Joerg Arndt, Dec 30 2023
|
|
|
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. 55-62, 122-138 and 143-146.
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
|
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
L. W. Shapiro, A Catalan triangle, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90. [Annotated scanned copy]
|
|
|
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^(n-k) and a(n) = Sum_{k = 0..floor(n/2)} binomial(n+1,2*k+1) * Catalan(k+1) * 2^(n-2*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,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n>=3, a(n-3) = (-1)^(n-3) * coeff(charpoly(A,x), x^3). - Milan Janjic, Jul 08 2010
G.f.: (1-sqrt(1-4*x) + 2*x*(-2+sqrt(1-4*x) + x))/(2*x^4). - Harvey P. Dale, May 05 2011
D-finite with recurrence: (n+4)a(n) = 8*(2*n-1)*a(n-3) - 20*(n+1)*a(n-2) + 4*(2*n+5)*a(n-1). - Fung Lam, Jan 29 2014
D-finite with recurrence: (n+4)*a(n) - 2*(3*n+7)*a(n-1) + 4*(2*n+1)*a(n-2) = 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
With F(x) = 16/(1+sqrt(1-4*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(1-x) = (1+sqrt(xi(x)))*K(1-xi(x)).
q(x) = sqrt(q(xi(16*x)/16)) = q'(xi(16*x)/16)/sqrt(xi(16*x)/16). (End)
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
|
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,k-1) + T(n-1,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)):
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[ (1-Sqrt[1-4 x]+2 x (-2+Sqrt[1-4 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, n-2) / n)}; /* Michael Somos, Jul 31 2005 */
(PARI) x='x+O('x^100); Vec((1-(1-4*x)^(1/2)+2*x*(-2+(1-4*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
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
