login
Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x. Sequence gives S(n-2,n).
2

%I #31 Jul 31 2024 11:36:58

%S 1,3,12,52,237,1119,5424,26832,134913,687443,3541932,18421524,

%T 96585597,509960223,2709067968,14469453632,77655751329,418567792899,

%U 2264867271852,12298297439892,66993811842477,366009125766463

%N Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x. Sequence gives S(n-2,n).

%C Threefold convolution of A001003 with itself. Number of dissections of a convex polygon with n+4 sides that have a quadrilateral over a fixed side (the base) of the polygon. Example: a(1)=3 because the only dissections of the convex pentagon ABCDE (AB being the base), that have a quadrilateral over AB are the dissections made by the diagonals EC, AD and BD, respectively. - _Emeric Deutsch_, Dec 27 2003

%C a(n-1) = number of royal paths (A006318) from (0,0) to (n,n) with exactly 2 diagonal steps on the line y=x. - _David Callan_, Jul 15 2004

%H Vincenzo Librandi, <a href="/A010736/b010736.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f.: (1+z-sqrt(1-6*z+z^2))^3/(64*z^3). - _Emeric Deutsch_, Dec 27 2003

%F a(n) = (3/n)*Sum_{k = 1..n} binomial(n, k)*binomial(n+k+2, k-1) = 3*hypergeom([1-n, n+4], [2], -1), n>=1, a(0)=1.

%F Recurrence: (n+3)*(2*n-1)*a(n) = (12*n^2+11*n-11)*a(n-1) - (n-3)*(2*n-1)*a(n-2) + (3-n)*a(n-3). - _Vaclav Kotesovec_, Oct 07 2012

%F a(n) ~ 3 * (1 + sqrt(2))^(2*n+3) / (2^(11/4) * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Oct 07 2012, simplified Dec 24 2017

%F From _Peter Bala_, Jul 31 2024: (Start)

%F a(n) = (3/4) * Sum_{k = 0..n+1} binomial(n+1, k)*binomial(n+k+1, k)/(k+2) for n >= 1.

%F Second-order recurrence: (n + 3)*n^2*a(n) = (2*n + 1)*(3*n^2 + 3*n - 2)*a(n-1) - (n - 2)*(n + 1)^2*a(n-2), with a(0) = 1 and a(1) = 3.

%F a(n) = (3/8) * hypergeom([2, n + 2, - n - 1], [1, 3], -1) for n >= 1.

%F a(n) = (3/4) * Integral_{x = 0..1} x*Legendre_P(n+1, 2*x+1) for n >= 1. Note that A006318(n) = Integral_{x = 0..1} Legendre_P(n, 2*x+1). (End)

%t f[ x_, y_ ] := f[ x, y ] = Module[ {return}, If[ x == 0, return = 1, If[ y == x-1, return = 0, return = f[ x, y-1 ] + Sum[ f[ k, y ], {k, 0, x-1} ] ] ]; return ]; Do[ Print[ Table[ f[ k, j ], {k, 0, j} ] ], {j, 10, 0, -1} ]

%t CoefficientList[Series[(1+x-Sqrt[1-6x+x^2])^3/(64x^3),{x,0,30}],x] (* _Harvey P. Dale_, Apr 18 2012 *)

%o (PARI) my(x='x+O('x^66)); Vec((1+x-sqrt(1-6*x+x^2))^3/(64*x^3)) \\ _Joerg Arndt_, May 04 2013

%Y Cf. A001003, A006318.

%Y Right-hand column 3 of triangle A011117.

%Y Third column of convolution triangle A011117.

%K nonn,easy

%O 0,2

%A Robert Sulanke (sulanke(AT)diamond.idbsu.edu)

%E More terms from _Emeric Deutsch_, Dec 27 2003