

A008288


Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals.


91



1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 7, 13, 7, 1, 1, 9, 25, 25, 9, 1, 1, 11, 41, 63, 41, 11, 1, 1, 13, 61, 129, 129, 61, 13, 1, 1, 15, 85, 231, 321, 231, 85, 15, 1, 1, 17, 113, 377, 681, 681, 377, 113, 17, 1, 1, 19, 145, 575, 1289, 1683, 1289, 575, 145, 19, 1, 1, 21, 181, 833, 2241, 3653, 3653
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Also called the tribonacci triangle [Alladi and Hoggatt].  N. J. A. Sloane, Mar 23 2014
D(nk,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0), (0,1), (1,1).  Joerg Arndt, Jul 01 2011
Or, triangle read by rows of coefficients of polynomials P[n](x) defined by P[0] = 1, P[1] = x+1; for n >= 2, P[n] = (x+1)*P[n1] + x*P[n2].
D(n, k) is the number of kmatchings of a comblike graph with n+k teeth. Example: D(1, 3)=7 because the graph consisting of a horizontal path ABCD and the teeth Aa, Bb, Cc, Dd has seven 3matchings: four triples of three teeth and the three triples {Aa, Bb, CD}, {Aa, Dd, BC}, {Cc, Dd, AB}. Also D(3, 1)=7, the 1matchings of the same graph being the seven edges: {AB}, {BC}, {CD}, {Aa}, {Bb}, {Cc}, {Dd}.  Emeric Deutsch, Jul 01 2002
Sum of nth row = A000129(n).  Reinhard Zumkeller, Dec 03 2004
The Asequence for this Riordan type triangle (see the P. Barry comment under Formula) is A112478 and the Zsequence the trivial: {1,0,0,0...}. See the W. Lang link under A006232 for Sheffer a and zsequences where also Riordan A and Zsequences are explained. This leads to the recurrence for the triangle given below.  Wolfdieter Lang, Jan 21 2008
Row sums are A000129.  Roger L. Bagula, Dec 09 2008
The triangle or chess sums, see A180662 for their definitions, link the Delannoy numbers with twelve different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 and Kn15 have been added. It is remarkable that all knight sums are related to the tribonacci numbers, that is, A000073 and A001590, but none of the others.  Johannes W. Meijer, Sep 22 2010
A008288 is jointly generated with A035607 as an array of coefficients of polynomials u(n,x): initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = x*u(n1,x) + v(n1) and v(n,x) = 2*x*u(n1,x) + v(n1,x). See the Mathematica section.  Clark Kimberling, Mar 09 2012
Row n, for n>0, of the Roger L. Bagula's triangle in the Example section shows the coefficients of the polynomial u(n) = c(0) + c(1)*x + ... + c(n)*x^n which is the numerator of the nth convergent of the continued fraction [k, k, k, ... ], where k = sqrt(x) + 1/sqrt(x); see A230000.  Clark Kimberling, Nov 13 2013


REFERENCES

B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5648007388. English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 37.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81.
H. Delannoy. Emploi de l'echiquier pour la resolution de certains problemes de probabilites, Association Francaise pour l'Avancement des Sciences, 18th session, 1895. pp. 7090 (table given on pp. 76)
G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973), 410.
L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Mathematica, 26 (1963) 223229.
Shiva Samieinia, Digital straight line segments and curves. Licentiate Thesis. Stockholm University, Department of Mathematics, Report 2007:6.


LINKS

T. D. Noe, Table of n, a(n) for n=0..5150
K. Alladi and V. E. Hoggatt Jr., On tribonacci numbers and related functions, Fibonacci Quart. 15 (1977), 4245.
C. Banderier and S. Schwer, Why Delannoy numbers?
Paul Barry, On IntegerSequenceBased Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, RiordanBernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2
Paul Barry, On the Inverses of a Family of PascalLike Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.
D. Bump, K. Choi, P. Kurlberg and J. Vaaler, A local Riemann hypothesis, I, Math. Zeit. 233, (2000), 119.
C. Carré, N. Debroux, M. Deneufchatel, J.P. Dubernard et al., Dirichlet convolution and enumeration of pyramid polycubes, 2013.
J. S. Caughman et al., A note on lattice chains and Delannoy numbers, Discrete Math., 308 (2008), 26232628.
J. R. Dias, Properties and relationships of conjugated polyenes having a reciprocal eigenvalue spectrum  dendralene and radialene hydrocarbons , Croatica Chem. Acta, 77 (2004), 325330.
Rebecca HartmanBaker, The Diffusion Equation Method for Global Optimization and Its Application to Magnetotelluric Geoprospecting, University of Illinois, UrbanaChampaign, 2005.
G. Hetyei, Shifted Jacobi polynomials and Delannoy numbers, 2009.  Peter Bala, Oct 28 2008
G. Hetyei, Links we almost missed between Delannoy numbers and Legendre polynomials.  Peter Bala, Nov 10 2008
M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550, 2013.  From N. J. A. Sloane, Feb 13 2013
M. LLadser, Uniform formulae for coefficients of meromorphic functions
E. Lucas, Théorie des Nombres. GauthierVillars, Paris, 1891, Vol. 1, p. 174.
J. W. Meijer, Famous numbers on a chessboard, Acta Nova, Volume 4, No.4, December 2010. pp. 589598.
Mirka Miller, Hebert PerezRoses, and Joe Ryan, The Maximum DegreeandDiameterBounded Subgraph in the Mesh, arXiv preprint arXiv:1203.4069, 2012.
L. Pachter and B. Sturmfels, The mathematics of phylogenomics
R. Pemantle and M. C. Wilson, Asymptotics of multivariate sequences, I: smooth points of the singular variety
J. L. Ramirez and V. F. Sirvent, Incomplete Tribonacci Numbers and Polynomials, Journal of Integer Sequences, Vol. 17, 2014, #14.4.2. See Table 1.  N. J. A. Sloane, Mar 23 2014
Marko Razpet, A selfsimilarity structure generated by king's walk, Algebraic and topological methods in graph theory (Lake Bled, 1999). Discrete Math. 244 (2002), no. 13, 423433. MR1844050 (2002k:05022).
Shiva Samieinia, Home Page.
M. Shattuck, Combinatorial identities for incomplete tribonacci polynomials, arXiv preprint arXiv:1406.2755, 2014.
R. G. Stanton and D. D. Cowan, Note on a "square" functional equation, SIAM Rev., 12 (1970), 277279.
Eric Weisstein's World of Mathematics, Delannoy Number


FORMULA

D(n, 0) = 1 = D(0, n) for n >= 0; D(n, k) = D(n, k1) + D(n1, k1) + D(n1, k).
Sum_{n >= 0, k >= 0} D(n, k)*x^n*y^k = 1/(1xyx*y).
D(n, k) = Sum_{d} binomial(k, d)*binomial(n+kd, k) = Sum_{d} 2^d*binomial(n, d)*binomial(k, d).
Seen as a triangle read by rows: T(n, 0)=T(n, n)=1 for n>=0 and T(n, k)=T(n1, k1)+T(n2, k1)+T(n1, k), 0<k<n and n>1.  Reinhard Zumkeller, Dec 03 2004
Read as a number triangle, this is the Riordan array (1/(1x), x(1+x)/(1x)) with T(n, k)=sum{j=0..nk, C(nk, j)C(k, j)2^j}.  Paul Barry, Jul 18 2005
T(n,k) = sum{j=0..nk, C(k,j)C(nj,k)}.  Paul Barry, May 21 2006
Let y^k(n) be the number of Khalimskycontinuous functions f from [0,n1] to Z such that f(0)=0 and f(n1)=k. Then y^k(n)=D(i,j) for i=1/2(n1k) and j=1/2(n1+k) where n1+k belongs to 2Z.  Shiva Samieinia (shiva(AT)math.su.se), Oct 08 2007
Recurrence for triangle from Asequence (see the W. Lang comment above): T(n,k) = sum(A112478(j)*T(n1,k1+j),j=0..nk), n>=1, k>=1.
From Peter Bala, Jul 17 2008: (Start)
The nth row of the square array is the crystal ball sequence for the product lattice A_1 x...x A_1 (n copies). A035607 is the table of the associated coordination sequences for these lattices.
The polynomial p_n(x) := sum {k = 0..n} 2^k*C(n,k)*C(x,k) = sum {k = 0..n} C(n,k)*C(x+k,n), whose values [p_n(0),p_n(1),p_n(2),... ] give the nth row of the square array, is the Ehrhart polynomial of the ndimensional cross polytope (the hyperoctahedron) [BUMP et al., Theorem 6].
The first few values are p_0(x) = 1, p_1(x) = 2*x+1, p_2(x) = 2*x^2+2*x+1 and p_3(x) = (4*x^3+6*x^2+8*x+3)/3.
The reciprocity law p_n(m) = p_m(n) reflects the symmetry of the table.
The polynomial p_n(x) is the unique polynomial solution of the difference equation (x+1)*f(x+1)  x*f(x1) = (2*n+1)*f(x), normalized so that f(0) = 1.
These polynomials have their zeros on the vertical line Re x = 1/2 in the complex plane; that is, the polynomials p_n(x1), n = 1,2,3,..., satisfy a Riemann hypothesis [BUMP et al., Theorem 4]. The o.g.f. for the p_n(x) is (1+t)^x/(1t)^(x+1) = 1 + (2*x+1)*t + (2*x^2+2*x+1)*t^2 + ... .
The square array of Delannoy numbers has a close connection with the constant log(2). The entries in the nth row of the array occur in the series acceleration formula log(2) = (11/2+1/3...+(1)^(n+1)/n) + (1)^n * sum {k = 1..inf} (1)^(k+1)/(k*T(n,k1)*T(n,k)).
For example, the fourth row of the table (n = 3) gives the series log(2) = 1  1/2 + 1/3  1/(1*1*7) + 1/(2*7*25)  1/(3*25*63) + 1/(4*63*129)  ... . See A142979 for further details.
Also the main diagonal entries (the central Delannoy numbers) give the series acceleration formula sum {n = 1..inf} 1/(n*T(n1,n1)*T(n,n)) = 1/2*log(2), a result due to Burnside.
Similar relations hold between log(2) and the crystal ball sequences of the C_n lattices A142992. For corresponding results for the constants zeta(2) and zeta(3), involving the crystal ball sequences for root lattices of type A_n and A_n x A_n, see A108625 and A143007 respectively. (End)
From Peter Bala, Oct 28 2008: (Start)
Hilbert transform of Pascal's triangle A007318 (see A145905 for the definition of this term).
T(n+a,n) = P_n(a,0;3) for all integer a such that a >= n, where P_n(a,0;x) is the Jacobi polynomial with parameters (a,0) [Hetyei]. The related formula A(n,k) = P_k(0,nk;3) defines the table of asymmetric Delannoy numbers, essentially A049600. (End)
Seen as a triangle read by rows: T(n,k) = (1)^(nk)*Hyper2F1([n+k, k+1], [1], 2) for 0<=k<=n.  Peter Luschny, Aug 02 2014


EXAMPLE

Square array D(i,j) begins:
1 1 1 1 1 1 1 1 ...
1 3 5 7 9 11 13 ...
1 5 13 25 41 61 ...
1 7 25 63 129 231 ...
1 9 41 129 321 681 ...
...
As a triangular array (on its side) this begins
0,0,0,0,0,1,1,11,11 ...
0,0,0,0,1,1,9,9,61 ...
0,0,0,1,1,7,7,41,41 ...
0,0,1,1,5,5,25,25,129 ...
0,1,1,3,3,13,13,63,63 ...
0,0,1,1,5,5,25,25,129 ...
0,0,0,1,1,7,7,41,41 ...
0,0,0,0,1,1,9,9,61 ...
0,0,0,0,0,1,1,11,11 ...
Triangle T(n,k) recurrence: 63 = T(6,3)= 25 +13 +25.
Triangle T(n,k) recurrence with Asequence A112478: 63= T(6,3) = 1*25+2*252*9+6*1 (T entries from row n=5 only).
From Roger L. Bagula, Dec 09 2008: (Start)
As a triangle this begins:
{1},
{1, 1},
{1, 3, 1},
{1, 5, 5, 1},
{1, 7, 13, 7, 1},
{1, 9, 25, 25, 9, 1},
{1, 11, 41, 63, 41, 11, 1},
{1, 13, 61, 129, 129, 61, 13, 1},
{1, 15, 85, 231, 321, 231, 85, 15, 1},
{1, 17, 113, 377, 681, 681, 377, 113, 17, 1},
{1, 19, 145, 575, 1289, 1683, 1289, 575, 145, 19, 1} ... (End)
From Philippe Deléham, Mar 29 2012: (Start)
Subtriangle of the triangle given by (1, 0, 1, 1, 0, 0, 0, ...) DELTA (0, 1, 0, 0, 0, ...) where DELTA is the operator defined in A084938:
1
1, 0
1, 1, 0
1, 3, 1, 0
1, 5, 5, 1, 0
1, 7, 13, 7, 1, 0
1, 9, 25, 25, 9, 1, 0
1, 11, 41, 63, 41, 11, 1, 0 ...
Subtriangle of the triangle given by (0, 1, 0, 0, 0, ...) DELTA (1, 0, 1, 1, 0, 0, 0, ...) where DELTA is the operator defined in A084938:
1
0, 1
0, 1, 1
0, 1, 3, 1
0, 1, 5, 5, 1
0, 1, 7, 13, 7, 1
0, 1, 9, 25, 25, 9, 1
0, 1, 11, 41, 63, 41, 11, 1 ... (End)


MAPLE

A008288 := proc(n, k) option remember; if k = 0 then 1 elif n=k then 1 else A008288(n1, k1) + A008288(n2, k1) + A008288(n1, k) fi; end: seq(seq(A008288(n, k), k=0..n), n=0..10);
P[0]:=1; P[1]:=x+1; for n from 2 to 12 do P[n]:=expand((x+1)*P[n1]+x*P[n2]); lprint(P[n]); lprint(seriestolist(series(P[n], x, 200))); od:


MATHEMATICA

Clear[a]; a[0] = {1}; a[1] = {1, 1}; a[n_] := a[n] = Join[{0}, a[n  2], {0}] + Join[{0}, a[n  1]] + Join[a[n  1], {0}]; Table[a[n], {n, 0, 10}]; Flatten[%] (* Roger L. Bagula, Dec 09 2008 *)
(* Next, A008388 jointly generated with A035607 *)
u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := x*u[n  1, x] + v[n  1, x];
v[n_, x_] := 2 x*u[n  1, x] + v[n  1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%] (* A008288 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%] (* A035607 *)
(* Clark Kimberling, Mar 09 2012 *)
d[n_, k_] := Binomial[n+k, k]*Hypergeometric2F1[k, n, nk, 1]; A008288 = Flatten[Table[d[nk, k], {n, 0, 12}, {k, 0, n}]] (* JeanFrançois Alcover, Apr 05 2012, after 3rd formula *)


PROG

(PARI) /* computation as lattice paths: */
/* same as in A092566, but last line (output) replaced by either of the following */
/* show as square array: */
M
/* show as triangle T(nk, k): */
{ for(n=0, N1, for(k=0, n, print1(T(nk, k), ", "); ); print(); ); }
/* Joerg Arndt, Jul 01 2011 */
(Haskell)
a008288 n k = a008288_tabl !! n !! k
a008288_row n = a008288_tabl !! n
a008288_tabl = map fst $ iterate
(\(us, vs) > (vs, zipWith (+) ([0] ++ us ++ [0]) $
zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 1])
 Reinhard Zumkeller, Jul 21 2013
(Sage)
for k in range(8):
a = lambda n: hypergeometric([n, k], [1], 2)
print [simplify(a(n)) for n in range(11)] # Peter Luschny, Nov 19 2014


CROSSREFS

Sums of antidiagonals = A000129 (Pell numbers), D(n, n) = A001850 (Delannoy numbers), (T(n, 3)) = A001845, (T(n, 4)) = A001846, etc. See also A027618. Rows and diagonals give A001844A001850. Cf. A059446.
See central Delannoy numbers A001850 for further information and references.
Has same main diagonal as A064861. Different from A100936.
Cf. A101164, A101167, A128966.
Cf. A131887, A131935.
Cf. A035607, A108625, A142979, A142992, A143007.
Read mod small primes: A211312A211315.
Triangle sums (see the comments): A000129 (Row1); A056594 (Row2); A000073 (Kn11 & Kn21); A089068 (Kn12 & Kn22); A180668 (Kn13 & Kn23); A180669 (Kn14 & Kn24); A180670 (Kn15 & Kn25); A099463 (Kn3 & Kn4); A116404 (Fi1 & Fi2); A006498 (Ca1 & Ca2); A006498(3*n) (Ca3 & Ca4); A079972 (Gi1 & Gi2); A079972(4*n) (Gi3 & Gi4); A079973(3*n) (Ze1 & Ze2); A079973(2*n) (Ze3 & Ze4).
Cf. A102413, A128966.
Sequence in context: A103450 A128254 A026714 * A238339 A144461 A106597
Adjacent sequences: A008285 A008286 A008287 * A008289 A008290 A008291


KEYWORD

nonn,tabl,nice,easy


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Expanded description from Clark Kimberling, Jun 15 1997
Additional references from Sylviane R. Schwer (schwer(AT)lipn.univparis13.fr), Nov 28 2001
Changed the notation to make the formulae more precise.  N. J. A. Sloane, Jul 01, 2002
More terms from Shiva Samieinia (shiva(AT)math.su.se), Oct 08 2007


STATUS

approved



