A110171 Triangle read by rows: T(n,k) (0 <= k <= n) is the number of Delannoy paths of length n that start with exactly k (0,1) steps (or, equivalently, with exactly k (1,0) steps).

1, 2, 1, 8, 4, 1, 38, 18, 6, 1, 192, 88, 32, 8, 1, 1002, 450, 170, 50, 10, 1, 5336, 2364, 912, 292, 72, 12, 1, 28814, 12642, 4942, 1666, 462, 98, 14, 1, 157184, 68464, 27008, 9424, 2816, 688, 128, 16, 1, 864146, 374274, 148626, 53154, 16722, 4482, 978, 162, 18, 1

Offset: 0

Author

Emeric Deutsch, Jul 14 2005

Keywords

• nonn
• tabl

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 k for k >= 1 has g.f. z^k*R^(k-1)*g*(1+z*R), where R = 1 + zR + zR^2 = (1 - z - sqrt(1-6z+z^2))/(2z) is the g.f. of the large Schroeder numbers (A006318) and g = 1/sqrt(1-6z+z^2) is the g.f. of the central Delannoy numbers (A001850).

Sum_{k=0..n} k*T(n,k) = A050151(n) (the partial sums of the central Delannoy numbers) = (1/2)*n*R(n), where R(n) = A006318(n) is the n-th large Schroeder number.

From Paul Barry, May 07 2009: (Start)

Riordan array ((1+x+sqrt(1-6x+x^2))/(2*sqrt(1-6x+x^2)), (1-x-sqrt(1-6x+x^2))/2).

Inverse of Riordan array ((1-2x-x^2)/(1-x^2), x(1-x)/(1+x)). (End)

Examples

			T(2,1)=4 because we have NED, NENE, NEEN and NDE.
Triangle starts:
    1;
    2,  1;
    8,  4,  1;
   38, 18,  6,  1;
  192, 88, 32,  8,  1;
From _Paul Barry_, May 07 2009: (Start)
Production matrix is
   2, 1,
   4, 2, 1,
   6, 2, 2, 1,
   8, 2, 2, 2, 1,
  10, 2, 2, 2, 2, 1,
  12, 2, 2, 2, 2, 2, 1,
  14, 2, 2, 2, 2, 2, 2, 1,
  16, 2, 2, 2, 2, 2, 2, 2, 1,
  18, 2, 2, 2, 2, 2, 2, 2, 2, 1 (End)
		

Links

• G. C. Greubel, Rows n = 0..100 of triangle, flattened
• P. Peart and W.-J. Woan, A divisibility property for a subgroup of Riordan matrices, Discrete Applied Mathematics, Vol. 98, Issue 3, Jan 2000, 255-263.
• Robert A. Sulanke, Objects Counted by the Central Delannoy Numbers, Journal of Integer Sequences, Volume 6, 2003, Article 03.1.5.
• W.-j. Woan, The Lagrange Inversion Formula and Divisibility Properties, JIS 10 (2007) 07.7.8, example 5.

Crossrefs

Cf. A001850, A002003, A006318, A050146, A050151, A113139, A118384.

Programs

Maple

Q:=sqrt(1-6*z+z^2): G:=(1+z+Q)/Q/(2-t+t*z+t*Q): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 10 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 10 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form

Mathematica

T[n_, n_] = 1;
T[n_, k_] := Sum[Binomial[n, i] Binomial[2n-k-i-1, n-k-i], {i, 0, n}];
Table[T[n, k], {n, 0, 9}, {k, 0, n}]//Flatten (* Jean-François Alcover, Jun 13 2019 *)

Sage

A110171 = lambda n,k : binomial(n, k)*hypergeometric([k-n, n], [k+1], -1)
for n in (0..9): [round(A110171(n,k).n(100)) for k in (0..n)] # Peter Luschny, Sep 17 2014

Formula

T(n,0) = A002003(n) for n >= 1.

T(n,1) = A050146(n) for n >= 1.

Row sums are the central Delannoy numbers (A001850).

G.f.: (1+z+Q)/(Q(2-t+tz+tQ)), where Q=sqrt(1-6z+z^2).

T(n,k) = x^(n-k)*((1+x)/(1-x))^n. - Paul Barry, May 07 2009

T(n,k) = C(n, k)*hypergeometric([k-n, n], [k+1], -1). - Peter Luschny, Sep 17 2014

From Peter Bala, Jun 29 2015: (Start)

T(n,k) = Sum_{i = 0..n} binomial(n,i)*binomial(2*n-k-i-1,n-k-i).

Matrix product A118384 * A007318^(-1)

Riordan array has the form ( x*h'(x)/h(x), h(x) ) with h(x) = ( 1 - x - sqrt(1 - 6*x + x^2) )/2 and so belongs to the hitting time subgroup H of the Riordan group (see Peart and Woan). (End)

T(n,k) = P(n-k, k, -1, 3), where P(n, alpha, beta, x) is the n-th Jacobi polynomial with parameters alpha and beta. Cf. A113139. - Peter Bala, Feb 16 2020