login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(n-k,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[n-1] + x*P[n-2].

D(n, k) is the number of k-matchings of a comb-like 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 3-matchings: four triples of three teeth and the three triples {Aa, Bb, CD}, {Aa, Dd, BC}, {Cc, Dd, AB}. Also D(3, 1)=7, the 1-matchings of the same graph being the seven edges: {AB}, {BC}, {CD}, {Aa}, {Bb}, {Cc}, {Dd}. - Emeric Deutsch, Jul 01 2002

Sum of n-th row = A000129(n). - Reinhard Zumkeller, Dec 03 2004

The A-sequence for this Riordan type triangle (see the P. Barry comment under Formula) is A112478 and the Z-sequence the trivial: {1,0,0,0...}. See the W. Lang link under A006232 for Sheffer a- and z-sequences where also Riordan A- and Z-sequences 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(n-1,x) + v(n-1) and v(n,x) = 2*x*u(n-1,x) + v(n-1,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 n-th 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 5-648-00738-8. 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, 18-th session, 1895. pp. 70-90 (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), 4-10.

L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Mathematica, 26 (1963) 223-229.

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), 42-45.

C. Banderier and S. Schwer, Why Delannoy numbers?

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

Paul Barry, Riordan-Bernstein 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 Pascal-Like 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), 1-19.

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), 2623-2628.

J. R. Dias, Properties and relationships of conjugated polyenes having a reciprocal eigenvalue spectrum - dendralene and radialene hydrocarbons , Croatica Chem. Acta, 77 (2004), 325-330.

Rebecca Hartman-Baker, The Diffusion Equation Method for Global Optimization and Its Application to Magnetotelluric Geoprospecting, University of Illinois, Urbana-Champaign, 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. Gauthier-Villars, Paris, 1891, Vol. 1, p. 174.

J. W. Meijer, Famous numbers on a chessboard, Acta Nova, Volume 4, No.4, December 2010. pp. 589-598.

Mirka Miller, Hebert Perez-Roses, and Joe Ryan, The Maximum Degree-and-Diameter-Bounded 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 self-similarity structure generated by king's walk, Algebraic and topological methods in graph theory (Lake Bled, 1999). Discrete Math. 244 (2002), no. 1-3, 423--433. 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), 277-279.

Eric Weisstein's World of Mathematics, Delannoy Number

FORMULA

D(n, 0) = 1 = D(0, n) for n >= 0; D(n, k) = D(n, k-1) + D(n-1, k-1) + D(n-1, k).

Sum_{n >= 0, k >= 0} D(n, k)*x^n*y^k = 1/(1-x-y-x*y).

D(n, k) = Sum_{d} binomial(k, d)*binomial(n+k-d, 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(n-1, k-1)+T(n-2, k-1)+T(n-1, k), 0<k<n and n>1. - Reinhard Zumkeller, Dec 03 2004

Read as a number triangle, this is the Riordan array (1/(1-x), x(1+x)/(1-x)) with T(n, k)=sum{j=0..n-k, C(n-k, j)C(k, j)2^j}. - Paul Barry, Jul 18 2005

T(n,k) = sum{j=0..n-k, C(k,j)C(n-j,k)}. - Paul Barry, May 21 2006

Let y^k(n) be the number of Khalimsky-continuous functions f from [0,n-1] to Z such that f(0)=0 and f(n-1)=k. Then y^k(n)=D(i,j) for i=1/2(n-1-k) and j=1/2(n-1+k) where n-1+k belongs to 2Z. - Shiva Samieinia (shiva(AT)math.su.se), Oct 08 2007

Recurrence for triangle from A-sequence (see the W. Lang comment above): T(n,k) = sum(A112478(j)*T(n-1,k-1+j),j=0..n-k), n>=1, k>=1.

From Peter Bala, Jul 17 2008: (Start)

The n-th 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 n-th row of the square array, is the Ehrhart polynomial of the n-dimensional 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(x-1) = (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(x-1), 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/(1-t)^(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 n-th row of the array occur in the series acceleration formula log(2) = (1-1/2+1/3-...+(-1)^(n+1)/n) + (-1)^n * sum {k = 1..inf} (-1)^(k+1)/(k*T(n,k-1)*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(n-1,n-1)*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,n-k;3) defines the table of asymmetric Delannoy numbers, essentially A049600. (End)

Seen as a triangle read by rows: T(n,k) = (-1)^(n-k)*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 A-sequence A112478: 63= T(6,3) = 1*25+2*25-2*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(n-1, k-1) + A008288(n-2, k-1) + A008288(n-1, 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[n-1]+x*P[n-2]); 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, -n-k, -1]; A008288 = Flatten[Table[d[n-k, k], {n, 0, 12}, {k, 0, n}]] (* Jean-Franç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(n-k, k): */

{ for(n=0, N-1, for(k=0, n, print1(T(n-k, 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 A001844-A001850. 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: A211312-A211315.

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.univ-paris13.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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 19 22:28 EST 2014. Contains 252240 sequences.