Delannoy Number

Author

Eric W. Weisstein
October 4, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/DelannoyNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/DelannoyNumber.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Code

Delannoy[0]:=1
Delannoy[1]:=3
Delannoy[n_]:= Delannoy[n]=(3(2n-1) Delannoy[n-1]-(n-1) Delannoy[n-2])/n

Delannoy[0, n_] := 1
Delannoy[n_, 0] := 1
Delannoy[1, 1] := 3
Delannoy[n_, k_] :=Delannoy[n, k]=Delannoy[n, k - 1] + Delannoy[n - 1, k - 1] + Delannoy[n - 1, k]

Enumeration

Delannoy/@Range[0,10]

Table[d[n,m],{n,0,5},{m,0,7}]//MatrixForm

Table[Delannoy[n,m],{n,0,15},{m,0,15}]//MatrixForm

Table[Delannoy[n,m],{n,0,5},{m,0,n}]

Read by antidiagonals:
http://www.research.att.com/~njas/sequences/A008288

Powers of 10

Series

Series[Hypergeometric2F1[-n,n+1,1,-1],{n,∞,1}]

Series[LegendreP[n,3],{n,∞,2}]

Enumeration

Table[Digits[Hypergeometric2F1[-10^n,10^n+1,1,-1]],{n,0,7}]//Timing

Table[Digits[Hypergeometric2F1[-10^n,10^n+1,1,-1]],{n,0,8}]//Timing

...crashes on Mac...

Exact

N[Log[10,3+2Sqrt[2]],20]

Limit

Limit[Log[10,Hypergeometric2F1[-n+1,n+1,1,-1]]/n,n->∞]//Timing

SequenceLimit

ListPlot[Table[Log[10,Hypergeometric2F1[-n,n+1,1,-1]]/n,{n,1,1000}],PlotJoined->True,PlotStyle->Red]

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[-n,n+1,1,-1]]/n,{n,1,1000}],100]]//Timing

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[-n,n+1,1,-1]]/n,{n,1,10^4}],100]]//Timing

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[-n,n+1,1,-1]]/n,{n,1,10^4}],500]]//Timing

Generating Function

D(a,b)

Series[(1/(1-x-y-x y)),{x,0,4},{y,0,4}]

SeriesCoefficient[(1/(1-x-y-x y)),{x,0,n},{y,0,k}]//InputForm

Series[(1/(1-x-y-x y)),{x,0,3},{y,0,3}]//Normal

Table[Binomial[k+n,k] Hypergeometric2F1[-n,-k,-k-n,-1](x^n)(y^k),{k,0,3},{n,0,3}]

Sum[Binomial[k+n,k] Hypergeometric2F1[-n,-k,-k-n,-1](x^n)(y^k),{k,0,∞},{n,0,∞}]

D(n)

GeneratingFunction[Hypergeometric2F1[1+n,-n,1,-1],n,x]

GeneratingFunction[LegendreP[n,3],n,x]

FullSimplify[Hypergeometric2F1[1+n,-n,1,-1]-LegendreP[n,3]]

Table[Hypergeometric2F1[1+n,-n,1,-1],{n,0,10}]

Series[(1/(Sqrt[1-6x+x^2])),{x,0,5}]

Sum[LegendreP[n,3](x^n),{n,0,∞}]

Sum[Hypergeometric2F1[1+n,-n,1,-1](x^n),{n,0,∞}]//InputForm

V5

<<DiscreteMath`RSolve`

SeriesTerm[(1/(Sqrt[1-6x+x^2])),{x,0,n}]

V7

SeriesCoefficient[(1/(Sqrt[1-6x+x^2])),{x,0,n}]

Mod (m)

MakeBoxes[label[n_],TraditionalForm]:=RowBox[{RowBox[{"D","(",RowBox[{"a",",","b"}],")"}]," ",RowBox[{"(",RowBox[{"mod"," ",MakeBoxes[n,TraditionalForm]}],")"}]}]

Show[GraphicsArray[
Block[{$DisplayFunction=Identity},Partition[Table[ArrayPlot[Mod[With[{d=256},Table[Delannoy[n, m], {n, 0, d},{m, 0, d}]],m],
ColorFunction->(Hue[#/10]&),ColorFunctionScaling->False,PlotLabel->TraditionalForm[label[m]]],{m,3,8}],3]]],ImageSize->500
]//Timing

Sums

D(n,k)==(∑_(d=0)^n)(Binomial[k, d]) (Binomial[-d+k+n, k])

Sum[Binomial[k,d]Binomial[n+k-d,k],{d,0,n}]

Table[Binomial[k+n,k] Hypergeometric2F1[-n,-k,-k-n,-1],{k,0,5},{n,0,8}]//TableForm

D(n,k)==(∑_(d=0)^n)(2^d) (Binomial[k, d]) (Binomial[n, d])

Sum[(2^d)Binomial[n,d]Binomial[k,d],{d,0,n}]

Table[DifferenceRoot[Function[{𝓎,𝓃},{(2 k n+(-2 k-2 n) 𝓃+2 (𝓃^2)) 𝓎[𝓃]+(-1-2 k n+(-2+2 k+2 n) 𝓃-3 (𝓃^2)) 𝓎[1+𝓃]+(1+2 𝓃+(𝓃^2)) 𝓎[2+𝓃]==0,𝓎[0]==0,𝓎[1]==1}]][1+n]-Binomial[k+n,k] Hypergeometric2F1[-n,-k,-k-n,-1],{k,0,5},{n,0,5}]//Flatten//Union

D(n)==(∑_(k=0)^n)(Binomial[n, k]) (Binomial[k+n, k])

V6

Sum[Binomial[n,k]Binomial[n+k,k],{k,0,n}]

V7

Sum[Binomial[n,k]Binomial[n+k,k],{k,0,n}]

Identities

D(n,k)==(Binomial[k+n, k]) (Hypergeometric2F1[-k, -n, -k-n, -1])

Table[Binomial[k+n,k] Hypergeometric2F1[-n,-k,-k-n,-1],{k,0,5},{n,0,5}]//TableForm

D(n)==(Hypergeometric2F1[n+1, -n, 1, -1])

Table[Hypergeometric2F1[1+n,-n,1,-1],{n,0,10}]

FullSimplify[Hypergeometric2F1[1+n,-n,1,-1]]

FunctionExpand[Hypergeometric2F1[1+n,-n,1,-1]]

D(n)==(LegendreP[n, 3])

Table[LegendreP[n,3],{n,0,10}]

FullSimplify[Hypergeometric2F1[1+n,-n,1,-1]-LegendreP[n,3]]

Recurrence

D(a,b)

RSolve[{d[a,b]==d[a-1,b]+d[a,b-1]+d[a-1,b-1],d[0,0]==1},d[a,b],{a,b}]

RSolve[{d[a,b]==d[a-1,b]+d[a,b-1]+d[a-1,b-1],d[0,b]==1,d[a,0]==1,d[1,1]==3},d[a,b],{a,b}]

D(n)

V5

<<DiscreteMath`RSolve

RSolve[{d[n]==((3(2n-1)d[n-1]-(n-1)d[n-2])/n),d[0]==1,d[1]==3},d[n],n]

V7

RSolve[{d[n]==((3(2n-1)d[n-1]-(n-1)d[n-2])/n),d[0]==1,d[1]==3},d[n],n]

Primes

(p=Position[Delannoy/@Range[1000],_?PrimeQ]//Flatten)//Timing

(p=Position[Delannoy/@Range[10^4],_?PrimeQ]//Flatten)//Timing

(p=Position[Delannoy/@Range[10^5],_?PrimeQ]//Flatten)//Timing

Digits[Delannoy[8]]//Timing

(p=Position[Delannoy/@Range[2 10^5],_?PrimeQ]//Flatten)//Timing

...

p={1};
t=AbsoluteTime[];
d2=1;
d1=3;
Do[
d=(3(2n-1) d1-(n-1) d2)/n;
d2=d1;
d1=d;
If[PrimeQ[d],Print["PRIME: ",AppendTo[p,n]]];
If[Mod[n,1000]==0,Print[n," ",Round[AbsoluteTime[]-t],"..."]],
{n,2,10^6}
]

Delannoy/@p

Graphics

si[{segs_,grid_,box___},{n_,k_}]:=Module[{i},
	Table[
		Show[Graphics[{
	{GrayLevel[.7],Polygon[box[n][[i]]]},
	grid[k],
	{Thickness[.05],RGBColor[1,0,0],Line[Map[path,segs[n]][[i]]]}
}],
AspectRatio->Automatic,DisplayFunction->Identity],
{i,Length[segs[n]]}]
]

SquareGrid[n_,j_:0]:=Module[{i},
{GrayLevel[.5],Table[{Line[{{j,i},{n,i}}],Line[{{i,j},{i,n}}]},{i,j,n}]}
]

SquareGrid[x_List]:=Module[{i},
{GrayLevel[.5],
Table[Line[{{x[[1,1]],i},{x[[2,1]],i}}],{i,x[[1,2]],x[[2,2]]}],
Table[Line[{{i,x[[1,2]]},{i,x[[2,2]]}}],{i,x[[1,1]],x[[2,1]]}]
}]
Null

d[1]:={{ne},{n,e},{e,n}}
d[2]:={{e,e,n,n},{e,ne,n},{e,n,e,n},{e,n,ne},{e,n,n,e},{n,e,ne},
		{n,e,n,e},{n,ne,e},{n,n,e,e},{ne,ne},{n,e,e,n},{ne,n,e},
		{ne,e,n}}

Show[GraphicsArray[
	Flatten[{{si[{d,SquareGrid},1]},
partition[si[{d,SquareGrid},2],5]},1]],
	DisplayFunction->$DisplayFunction]

Relationship to Cholesky Decomposition

CholeskyDecomposition[Table[Delannoy[n, m], {n, 0, 10},{m, 0, 10}]]

DiagonalMatrix[Table[Sqrt[2]^(-n), {n, 0, 10}]]// MatrixForm

With[{d=10},Transpose[CholeskyDecomposition[Table[Delannoy[n, m], {n, 0, d},
{m, 0, d}]]].DiagonalMatrix[Table[Sqrt[2]^(-n), {n, 0, d}]]
]//MatrixForm

With[{d=10},Table[Binomial[n,m], {n, 0, d},{m, 0, d}]]//MatrixForm