|
|
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).
|
|
3
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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 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.
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)
|
|
LINKS
|
|
|
FORMULA
|
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
T(n,k) = Sum_{i = 0..n} binomial(n,i)*binomial(2*n-k-i-1,n-k-i).
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
|
|
EXAMPLE
|
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;
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)
|
|
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}];
|
|
PROG
|
(Sage)
A110171 = lambda n, k : binomial(n, k)*hypergeometric([k-n, n], [k+1], -1)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|