A108666 Number of (1,1)-steps in all Delannoy paths of length n.

0, 1, 8, 57, 384, 2505, 16008, 100849, 628736, 3888657, 23900040, 146146473, 889928064, 5399971161, 32668236552, 197123362785, 1186790473728, 7131032334369, 42773183020296, 256161548120857, 1531966218561920, 9150330147133161, 54591847064667528, 325361790187810257

Offset: 0

Author

Emeric Deutsch, Jul 07 2005

Keywords

• nonn

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).

Examples

			a(2)=8 because in the 13 (=A001850(2)) Delannoy paths of length 2, namely, DD, DNE,DEN,NED,END,NDE,EDN,NENE,NEEN,ENNE,ENEN,NNEE and EENN, we have a total of eight D steps.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
• Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014) #14.1.5
• Robert A. Sulanke, Objects Counted by the Central Delannoy Numbers, Journal of Integer Sequences, Volume 6, 2003, Article 03.1.5.

Crossrefs

a(n)/n = A047781(n) (for n >= 1).

Cf. A001850, A104684.

Programs

Maple

a := n -> add(k*binomial(n,k)*binomial(2*n-k,n),k=1..n): seq(a(n),n=0..24);
# Alternative:
a := n -> n^2*hypergeom([-n+1, -n+1], [2], 2):
seq(simplify(a(n)), n=0..24); # Peter Luschny, Jan 20 2020

Mathematica

CoefficientList[Series[x*(1-x)/(1-6*x+x^2)^(3/2), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 18 2012 *)

PARI

for(n=0,25, print1(sum(k=0,n, k*binomial(n,k)*binomial(2*n-k,n)), ", ")) \\ G. C. Greubel, Jan 31 2017

Python

from math import comb
def A108666(n): return sum(comb(n,k)**2*k<Chai Wah Wu, Mar 22 2023

Formula

a(n) = Sum_{k=0..n} k*A104684(k).

a(n) = Sum_{k=1..n} k*binomial(n, k)*binomial(2*n-k, n).

G.f.: x*(1-x)/(1-6*x+x^2)^(3/2).

D-finite with recurrence (n-1)*(2*n-3)*a(n) = 4*(3*n^2-6*n+2)*a(n-1) - (n-1)*(2*n-1)*a(n-2). - Vaclav Kotesovec, Oct 18 2012

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

a(n) = n^2*hypergeom([-n+1, -n+1], [2], 2). - Peter Luschny, Jan 20 2020

a(n) = Sum_{k=1..n} 2^(k-1)*k*binomial(n,k)^2. - Ridouane Oudra, Jun 15 2025