A110122 Number of Delannoy paths of length n with no EE's crossing the line y = x (i.e., no two consecutive E steps from the line y = x+1 to the line y = x-1).

1, 3, 12, 53, 247, 1192, 5897, 29723, 152020, 786733, 4111295, 21661168, 114925697, 613442227, 3291704108, 17745496453, 96062011319, 521943400056, 2845404909129, 15558847792747, 85311186002036, 468951179698653, 2583765541267647, 14266052382826208

Offset

0,2

Comments

A Delannoy path of length n is a path from (0,0) to (n,n), consisting of steps E=(1,0), N=(0,1) and D=(1,1).

Column 0 of A110121.

Links

Nathaniel Johnston, Table of n, a(n) for n = 0..500

P. Fahr and C. M. Ringel, A partition formula for Fibonacci Numbers, JIS 11 (2008) Article 08.1.4.

Pedro Fernando Fernández Espinosa and Agustín Moreno Cañadas, Homological Ideals as Integer Specializations of Some Brauer Configuration Algebras, arXiv:2104.00050 [math.RT], 2021.

M. D. Hirschhorn, On Recurrences of Fahr and Ringel Arising in Graph Theory , JIS 12 (2009) 09.6.8

Harris Kwong, On recurrences of Fahr and Ringel: an alternate approach, Fibonacci Quart. 48 (2010), no. 4, 363-365.

H. Prodinger, Generating functions related to partition formulas for Fibonacci Numbers, JIS 11 (2008) Article 08.1.8.

Robert A. Sulanke, Objects Counted by the Central Delannoy Numbers, Journal of Integer Sequences, Volume 6, 2003, Article 03.1.5.

Formula

G.f.: 1/((1-zR)^2-z), where R = 1 + zR + zR^2 = (1 - z - sqrt(1 - 6z + z^2))/(2z) is the g.f. of the large Schroeder numbers (A006318).

a(n) = (1/(n+1))Sum_{k=0..n} (k+1) * Sum_{i=0..n-k} binomial(n+1, i)*binomial(2*n-k-i, n) * A000045(k+1). - Vladimir Kruchinin, Apr 18 2011

Recurrence: (2*n^2+9*n+7)*a(n) - (26*n^2+135*n+151)*a(n+1) + (88*n^2+528*n+746)*a(n+2) - (26*n^2+177*n+277)*a(n+3) + (2*n^2+15*n+25)*a(n+4)=0. - Vaclav Kotesovec, Sep 08 2012

a(n) ~ (10+7*sqrt(2))*sqrt((3*sqrt(2)-4)/Pi) * (3+2*sqrt(2))^n/n^(3/2). - Vaclav Kotesovec, Dec 11 2012

Example

a(2) = 12 because, among the 13 (=A001850(2)) Delannoy paths of length 2, only NEEN has an EE crossing the line y=x.

Maple

R:=(1-z-sqrt(1-6*z+z^2))/2/z: G:=1/((1-z*R)^2-z): Gser:=series(G, z=0, 27): 1, seq(coeff(Gser, z^n), n=1..24);

Mathematica

Flatten[{1, RecurrenceTable[{(2*n^2+9*n+7)*a[n]-(26*n^2+135*n+151) *a[n+1]+(88*n^2+528*n+746)*a[n+2]-(26*n^2+177*n+277)*a[n+3]+(2*n^2+15*n+25)*a[n+4]==0, a[1]==3, a[2]==12, a[3]==53, a[4]==247}, a, {n, 25}]}] (* Vaclav Kotesovec, Sep 09 2012 *)

Prog

(Maxima)
a(n):=sum((k+1)/(n+1)*sum(binomial(n+1, i)*binomial(2*n-k-i, n), i, 0, n-k) *fib(k+1), k, 0, n); /* Vladimir Kruchinin, Apr 18 2011 */

Crossrefs

Cf. A001850, A110121.

Sequence in context: A151203 A262442 A026781 * A307412 A302188 A060460

Adjacent sequences: A110119 A110120 A110121 * A110123 A110124 A110125

Keyword

nonn

Author

Emeric Deutsch, Jul 13 2005

Extensions

Minor edits by Vaclav Kotesovec, Mar 31 2014

Status

approved