|
%I M3483 N1415 #261 Jan 17 2024 04:33:35
%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: a(n) = 4*binomial(2*n+3,n)/(n+4).
%C 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
%C 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
%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) 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) 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
%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
%C Apparently also Young tableaux of (non-partition) shape [n+1, 1, 1, n+1], see example file. - _Joerg Arndt_, Dec 30 2023
%D Pierre 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., Vol. 14 (1922), pp. 55-62, 122-138 and 143-146.
%D Robert Sedgewick and Phillipe 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 Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, <a href="https://arxiv.org/abs/2301.09765">Enumeration of multi-rooted plane trees</a>, arXiv:2301.09765 [math.CO], 2023.
%H Joerg Arndt, <a href="/A002057/a002057.txt">The a(3)=48 Young tableaux for shape [4,1,1,4]</a>.
%H Andrei Asinowski and Cyril Banderier, <a href="https://arxiv.org/abs/2401.05558">From geometry to generating functions: rectangulations and permutations</a>, arXiv:2401.05558 [cs.DM], 2024. See page 2.
%H Jean-Luc Baril and Helmut Prodinger, <a href="https://arxiv.org/abs/2205.01383">Enumeration of partial Lukasiewicz paths</a>, arXiv:2205.01383 [math.CO], 2022.
%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 Julia E. Bergner, Cedric Harper, Ryan Keller, and Mathilde Rosi-Marshall, <a href="https://arxiv.org/abs/1807.03005">Action graphs, planar rooted forests, and self-convolutions of the Catalan numbers</a>, arXiv:1807.03005 [math.CO], 2018.
%H Daniel Birmajer, Juan B. Gil, and 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 Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.
%H Gi-Sang Cheon, Hana Kim, and Louis 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 Samuel Connolly, Zachary Gabor, and Anant 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., Vol. 35, No. 4 (1995) pp. 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., Vol. 35, No. 4 (1995) pp. 743-751. [Annotated scanned copy]
%H Harold M. Edwards, <a href="https://doi.org/10.1090/S0273-0979-07-01153-6">A Normal Form for Elliptic Curves</a>, Bulletin of the A.M.S., Vol. 44, No. 3 (2007), pp. 393-422.
%H Richard K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>
%H Richard K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, Sandsteps and Pascal Pyramids</a>, J. Integer Seq., Vol. 3 (2000), Article 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., Vol. 14, No. 5 (1976), pp. 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., Vol. 14 (1922), pp. 55-62, 122-138 and 143-146. [Annotated scanned copy]
%H Wolfdieter 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., Vol. 38, No. 5 (2000), pp. 408-419. See Eq.(3).
%H Kyu-Hwan Lee and 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 Nik Lygeros and Olivier 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., Vol. 13 (2010), Article 10.7.4.
%H Ran Pan and Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.
%H John Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Nov 10 1970</a>.
%H John 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-1">A Catalan triangle</a>, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90.
%H L. W. Shapiro, <a href="/A003517/a003517.pdf">A Catalan triangle</a>, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90. [Annotated scanned copy]
%H Zoran Sunic, <a href="https://doi.org/10.37236/1745">Self describing sequences and the Catalan family tree</a>, Elect. J. Combin., Vol. 10 (2003), Article N5.
%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 Steven 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, Vol. 11 (2011), Article A3.
%H Wen-Jin Woan, Lou 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, Vol. 104, No. 10 (1997), pp. 926-931.
%F a(n) = A033184(n+4, 4) = 4*binomial(2*n+3, n)/(n+4) = 2*(n+1)*A000108(n+2)/(n+4).
%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-4*x) + 2*x*(-2+sqrt(1-4*x) + x))/(2*x^4). - _Harvey P. Dale_, May 05 2011
%F a(n+1) = A214292(2*n+4,n). - _Reinhard Zumkeller_, Jul 12 2012
%F 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
%F 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
%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 [Note: 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
%F From _Bradley Klee_, Mar 05 2018: (Start)
%F 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:
%F K(x) = (1+sqrt(xi(x)))*K(xi(x)).
%F 2*K(1-x) = (1+sqrt(xi(x)))*K(1-xi(x)).
%F q(x) = sqrt(q(xi(16*x)/16)) = q'(xi(16*x)/16)/sqrt(xi(16*x)/16). (End)
%F From _Amiram Eldar_, Jan 02 2022: (Start)
%F Sum_{n>=0} 1/a(n) = 5/4 + Pi/(18*sqrt(3)).
%F Sum_{n>=0} (-1)^n/a(n) = 183*log(phi)/(25*sqrt(5)) - 77/100, where phi is the golden ratio (A001622). (End)
%F 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
%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
%p A002057List := proc(m) local A, P, n; A := [1]; P := [1,1,1];
%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
%p A := [op(A), P[-1]] od; A end: A002057List(27); # _Peter Luschny_, Mar 26 2022
%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 *)
%o (GAP) List([0..25],n->4*Binomial(2*n+3,n)/(n+4)); # _Muniru A Asiru_, Mar 05 2018
%o (SageMath) [2*(n+1)*catalan_number(n+2)/(n+4) for n in (0..30)] # _G. C. Greubel_, May 27 2022
%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, A001622.
%Y Cf. A145596 (row sums), A279004.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
|
