login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002057 Fourth convolution of Catalan numbers: 4*binomial(2n+3,n)/(n+4).
(Formerly M3483 N1415)
59

%I M3483 N1415

%S 1,4,14,48,165,572,2002,7072,25194,90440,326876,1188640,4345965,

%T 15967980,58929450,218349120,811985790,3029594040,11338026180,

%U 42550029600,160094486370,603784920024,2282138106804,8643460269248,32798844771700,124680849918352

%N Fourth convolution of Catalan numbers: 4*binomial(2n+3,n)/(n+4).

%C 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_, Nov 11 2001

%C a(n-2) = 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

%C Number of standard tableaux of shape (n+2,n-1). - _Emeric Deutsch_, May 30 2004

%C 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

%C 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 + ...)

%C a(n+1) = A214292(2*n+4,n). - _Reinhard Zumkeller_, Jul 12 2012

%C 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

%C 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

%C With offset 4, a(n)=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

%C 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

%C 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

%C 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

%D P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_4(z).

%D C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.

%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 225.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H T. D. Noe and Fung Lam, <a href="/A002057/b002057.txt">Table of n, a(n) for n = 0..1000</a> (first 100 terms were computed by T. D. Noe)

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1707.09918">Bounce statistics for rational lattice paths</a>, arXiv:1707.09918 [math.CO], 2017, p. 9.

%H A. Cayley, <a href="http://dx.doi.org/10.1112/plms/s1-22.1.237">On the partitions of a polygon</a>, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.

%H G.-S. Cheon, H. Kim, L. W. Shapiro, <a href="http://arxiv.org/abs/1410.1249">Mutation effects in ordered trees</a>, arXiv preprint arXiv:1410.1249 [math.CO], 2014 (see page 4).

%H S. Connolly, Z. Gabor and A. Godbole, <a href="http://arxiv.org/abs/1401.2691"> The location of the first ascent in a 123-avoiding permutation</a>, arXiv:1401.2691 [math.CO], 2014.

%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, <a href="http://dx.doi.org/10.1021/ci00026a012">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751.

%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, <a href="/A002057/a002057.pdf">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]

%H R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>

%H R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, Sandsteps and Pascal Pyramids</a>, J. Integer Seqs., Vol. 3 (2000), #00.1.6.

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="http://www.fq.math.ca/Scanned/14-5/hoggatt1.pdf">Catalan and related sequences arising from inverses of Pascal's triangle matrices</a>, Fib. Quart., 14 (1976), 395-405.

%H C. Krishnamachary and M. Bheemasena Rao, <a href="/A000108/a000108_10.pdf">Determinants whose elements are Eulerian, prepared Bernoullian and other numbers</a>, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146. [Annotated scanned copy]

%H W. Lang, <a href="http://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38 (2000) 408-419. See Eq.(3).

%H Kyu-Hwan Lee, Se-jin Oh, <a href="http://arxiv.org/abs/1601.06685">Catalan triangle numbers and binomial coefficients</a>, arXiv:1601.06685 [math.CO], 2016.

%H N. Lygeros, O. Rozier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Lygeros/lygeros5.html">A new solution to the equation tau(rho) == 0 (mod p)</a>, J. Int. Seq. 13 (2010) # 10.7.4.

%H Ran Pan, Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.

%H J. Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Nov 10 1970</a>

%H J. Riordan, <a href="/A000254/a000254.pdf">Letter of 04/11/74</a>

%H L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0012-365X(76)90009-">A Catalan triangle</a>, Discrete Math. 14 (1976), no. 1, 83-90.

%H L. W. Shapiro, <a href="/A003517/a003517.pdf">A Catalan triangle</a>, Discrete Math. 14 (1976), no. 1, 83-90. [Annotated scanned copy]

%H Zoran Sunic, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v10i1n5">Self describing sequences and the Catalan family tree</a>, Elect. J. Combin., 10 (No. 1, 2003).

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

%H S. J. Tedford, <a href="http://www.emis.de/journals/INTEGERS/papers/l3/l3.Abstract.html">Combinatorial interpretations of convolutions of the Catalan numbers</a>, Integers 11 (2011) #A3

%H W.-J. Woan, L. Shapiro and D. G. Rogers, <a href="http://www.jstor.org/stable/2974473">The Catalan numbers, the Lebesgue integral and 4^{n-2}</a>, Amer. Math. Monthly, 104 (1997), 926-931.

%F a(n) = A033184(n+3, 4)= 4*binomial(2*n+1, n-1)/(n+3)= 2*n*A000108(n+1)/(n+3).

%F G.f.: c(x)^4 with c(x) g.f. of A000108 (Catalan).

%F 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

%F 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

%F G.f.: (1-sqrt(1-4x)+2x(-2+sqrt(1-4x)+x))/(2x^4). - _Harvey P. Dale_, May 05 2011

%F 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

%F (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

%F Asymptotics: a(n) ~ 4^(n+3)/sqrt(4*Pi*n^3). - _Fung Lam_, Mar 31 2014

%F a(n) = 32*4^n*Gamma(5/2+n)*(1+n)/(sqrt(Pi)*Gamma(5+n)). - _Peter Luschny_, Dec 14 2015

%F a(n) = C(n+1)-2*C(n) where C is Catalan number A000108. _Yuchun Ji_, Oct 18 2017 [NB: Offset is off by 2]

%F E.g.f.: d/dx 2*exp(2*x)*BesselI(2,2*x)/x. - _Ilya Gutkovskiy_, Nov 01 2017

%e From _Peter Bala_, Apr 14 2017: (Start)

%e 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

%e n\k| 0 1 2 3 4 5 6 7 ...

%e - - - - - - - - - - - - - - - - - -

%e 0 | 0

%e 1 | 0 0

%e 2 | 0 0 0

%e 3 | 1 1 1 1

%e 4 | 1 2 3 4 4

%e 5 | 1 3 6 10 14 14

%e 6 | 1 4 10 20 34 48 48

%e 7 | 1 5 15 35 69 117 165 165

%e ...

%e (see Tedford 2011; this is essentially the array C_4(n,k) in the notation of Lee and Oh). Compare with A279004. (End)

%p a := n -> 32*4^n*GAMMA(5/2+n)*(1+n)/(sqrt(Pi)*GAMMA(5+n)):

%p seq(a(n),n=0..23); # _Peter Luschny_, Dec 14 2015

%t Table[Plus@@Flatten[Nest[ #/.a_Integer:> Range[0, a+1]&, {0}, n]], {n, 0, 10}]

%t 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 *)

%o (PARI) a(n)=if(n<0, 0, n+=2; 2*binomial(2*n,n-2)/n) /* _Michael Somos_, Jul 31 2005 */

%o (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

%o (MAGMA) [4*Binomial(2*n+3,n)/(n+4): n in [0..30]]; // _Vincenzo Librandi_, Feb 04 2016 *)

%Y T(n, n+4) for n=0, 1, 2, ..., array T as in A047072. Also a diagonal of A059365 and of A009766.

%Y Cf. A001003.

%Y A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

%Y Cf. A000108, A000245, A000344, A003517, A000588, A003518, A003519, A001392.

%Y Cf. A145596 (row sums). Cf. A279004.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 04:39 EST 2018. Contains 299358 sequences. (Running on oeis4.)