login
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).
4
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
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.
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
Sequence in context: A151203 A262442 A026781 * A307412 A302188 A060460
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 13 2005
EXTENSIONS
Minor edits by Vaclav Kotesovec, Mar 31 2014
STATUS
approved