|
| |
|
|
A002057
|
|
Fourth convolution of Catalan numbers: 4*C(2n+3,n)/(n+4).
(Formerly M3483 N1415)
|
|
28
| |
|
|
1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440, 326876, 1188640, 4345965, 15967980, 58929450, 218349120, 811985790, 3029594040, 11338026180, 42550029600, 160094486370, 603784920024, 2282138106804, 8643460269248
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| a(n) is sum of the (flattened) list obtained by the iteration of: replace each integer k by the list 0,..k+1 on the starting value 0. Length of this list is catalan(n)or A000108. - Wouter Meeussen (wouter.meeussen(AT)pandora.be), Nov 11 2001
a(n-2) = number of n-th generation vertices in the tree of sequences with unit increase labeled by 3 (cf. Zoran Sunik reference) - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 07 2003
Number of standard tableaux of shape (n+2,n-1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (callan(AT)stat.wisc.edu), 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 + ...)
|
|
|
REFERENCES
| Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
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.
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., 35 (1995) 743-751.
P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_4(z).
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.
W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. See Eq.(3).
L. W. Shapiro, A Catalan triangle. Discrete Math. 14 (1976), no. 1, 83-90.
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).
Zoran Sunik, Self describing sequences and the Catalan family tree, Elect. J. Combin., 10 (No. 1, 2003).
W.-J. Woan, L. Shapiro and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n-2}, Amer. Math. Monthly, 104 (1997), 926-931.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..100
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
|
|
|
FORMULA
| a(n)= A033184(n+3, 4)= 4*binomial(2*n+1, n-1)/(n+3)= 2*n*A000108(n+1)/(n+3).
G.f.: c(x)^4 with c(x) g.f. of A000108 (Catalan).
Contribution from Peter Bala (pbala(AT)toucansurf.com), Oct 14 2008: (Start)
Row sums of A145596. Column 4 of A033184. By specialising 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.
(End)
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). [From Milan R. Janjic (agnus(AT)blic.net), Jul 08 2010]
G.f.: (1-sqrt(1-4x)+2x(-2+sqrt(1-4x)+x))/(2x^4) [From Harvey P. Dale, May 05 2011]
Conjecture: (n+4)*a(n) +(n+7)*a(n-1) -2*(17n+26)*a(n-2) +28(2n-1)*a(n-3)=0. - R. J. Mathar, Dec 17 2011
|
|
|
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] (* From 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 */
|
|
|
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 A002057 A000344 A003517 A000588 A003518 A003519 A001392.
A145596 (row sums). [From Peter Bala (pbala(AT)toucansurf.com), Oct 14 2008]
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 (njas(AT)research.att.com).
|
| |
|
|
