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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 13 2005
EXTENSIONS
Minor edits by Vaclav Kotesovec, Mar 31 2014
STATUS
approved