A219670 Number of n-step paths on cubic lattice from (0,0,0) to (1,0,0) with moves in any direction on {-1,0,1}^3 and zero moves allowed.

0, 1, 18, 294, 5776, 117045, 2505006, 55138293, 1245056184, 28643604147, 669304345150, 15838583011812, 378828554265096, 9143273873757283, 222407411228180010, 5446827816890184990, 134191612737844924608, 3323506599627088488579, 82700482246125321972582

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..250

Formula

a(n) ~ 3^(3*n+3/2) / (4*Pi*n)^(3/2). - Vaclav Kotesovec, Sep 07 2014

Recurrence (of order 4): (n-1)^2*n^2*(n+1)*(2*n-5)*(7*n^4 - 56*n^3 + 166*n^2 - 216*n + 105)*a(n) = (n-1)*n*(2*n-5)*(2*n-1)*(70*n^6 - 630*n^5 + 2206*n^4 - 3759*n^3 + 3181*n^2 - 1188*n + 144)*a(n-1) + 3*(n-1)*(2*n-3)*(490*n^8 - 5880*n^7 + 30030*n^6 - 85050*n^5 + 145359*n^4 - 152064*n^3 + 93599*n^2 - 30264*n + 3852)*a(n-2) - 27*(n-2)^2*(2*n-5)*(2*n-1)*(70*n^6 - 630*n^5 + 2206*n^4 - 3813*n^3 + 3424*n^2 - 1563*n + 342)*a(n-3) - 729*(n-3)^3*(n-2)^2*(2*n-1)*(7*n^4 - 28*n^3 + 40*n^2 - 24*n + 6)*a(n-4). - Vaclav Kotesovec, Sep 07 2014

a(n) = A002426(n)^2 * A005717(n). - Mark van Hoeij, Nov 13 2022

Maple

a:= proc(n) a(n):= `if`(n<6, [0, 1, 18, 294, 5776, 117045][n+1],
     (n*(n-1)*(453658*n^4-2664929*n^3+6608535*n^2-8353208*n+3876664)
      *a(n-1) +3*(n-1)*(286527*n^5+2962040*n^4-19850405*n^3+25517846
      *n^2+20905560*n-41336424) *a(n-2) -18*(n-2)*(2*n-5)*(1294945*n^4
      -12949450*n^3+54428897*n^2-110276360*n+88672932) *a(n-3) -81*(n-3)
      *(286527*n^5-10125215*n^4+111022145*n^3-530226521*n^2+1163720520*n
      -966508776) *a(n-4) +729*(453658*n^4-6408231*n^3+34683300*n^2
      -84691467*n+77744124)*(n-4)^2 *a(n-5) +19683*(-42552+15593*n)
      *(n-4)^2 *(n-5)^3 *a(n-6))/ (n^2*(n+1)*(n-1)^2*(15593*n-35413)))
    end:
seq (a(n), n=0..30);  # Alois P. Heinz, Nov 28 2012
A005717 := n -> simplify(GegenbauerC(n-1, -n, -1/2));
A002426 := n -> simplify(GegenbauerC(n, -n, -1/2));
seq( A002426(n)^2 * A005717(n), n=0..30 );  # Mark van Hoeij, Nov 13 2022

Prog

(JavaScript)
b=[[1, 1, 1], [1, 1, 0], [1, 1, -1], [1, 0, 1], [1, 0, 0], [1, 0, -1], [1, -1, 1], [1, -1, 0], [1, -1, -1],
[0, 1, 1], [0, 1, 0], [0, 1, -1], [0, 0, 1], [0, 0, 0], [0, 0, -1], [0, -1, 1], [0, -1, 0], [0, -1, -1],
[-1, 1, 1], [-1, 1, 0], [-1, 1, -1], [-1, 0, 1], [-1, 0, 0], [-1, 0, -1], [-1, -1, 1], [-1, -1, 0], [-1, -1, -1]];
function inc(arr, m) {
al=arr.length-1;
full=true;
for (ac=0; ac<=al; ac++) if (arr[ac]!=m) {full=false; break; }
if (full==true) return false;
while (arr[al]==m && al>0) {arr[al]=0; al--; }
arr[al]++;
return true;
}
for (k=0; k<6; k++) {
c=0;
a=new Array();
for (i=0; i<k; i++) a[i]=0;
for (i=0; i<Math.pow(27, k); i++) {
p=[0, 0, 0];
for (j=0; j<k; j++) {p[0]+=b[a[j]][0]; p[1]+=b[a[j]][1]; p[2]+=b[a[j]][2]; }
if (p[0]==1 && p[1]==0 && p[2]==0) c++;
inc(a, 26);
}
document.write(c+", ");
}

Crossrefs

Cf. A219671, A219986.

Cf. A002426, A005717.

Sequence in context: A014899 A048447 A167713 * A166927 A113367 A228604

Adjacent sequences: A219667 A219668 A219669 * A219671 A219672 A219673

Keyword

nonn

Author

Jon Perry, Nov 24 2012

Extensions

More terms from Alois P. Heinz, Nov 28 2012

Status

approved