A143734 - OEIS

%I #18 Sep 05 2014 17:26:59

%S 1,13,638,41476,3015296,232878412,18691183682,1540840801552,

%T 129548309399618,11057865563760844,955237244106091682,

%U 83324522236732005112,7327068320498628273506,648679579345635742189498,57761885964038080406607410,5169168679056263697679753150

%N Number of paths of a generalized chess Queen from (0,0,0) to (n,n,n) in a cube, in which the Queen moves toward the goal point at each step.

%C a(n) is the number of sequences whose terms are multiples of (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,0,1), (1,1,0), or (1,1,1) and whose sum is (n,n,n).

%H Alois P. Heinz and Vaclav Kotesovec, <a href="/A143734/b143734.txt">Table of n, a(n) for n = 0..250</a> (first 81 terms from Alois P. Heinz)

%F q(1,1,1) = 1; q(1,1,2) = 1; q(1,2,1) = 1; q(1,1,2) = 1; q(i_,j,k) = Sum(q(x,j,k), {x,1,i-1}) + Sum(q(i,y,k), {y,1,j-1}] + Sum(q(i,j,z), {z,1,k-1}) + Sum(q(i-w,j-w,k), {w,1,Min(i,j)}) + Sum(q(i,j-w,k-w), {w,1,Min(j, k)}) + Sum(q(i-w,j,k-w), {w,1,Min(i,k)}) + Sum(q(i-w,j-w,k-w), {w,1,Min(i,j,k)}); a(n) = q(n,n,n).

%F a(n) ~ c * d^(3*n) / n, where d = 4.575760096729293131840036142861966071... is the root of the equation -8 - 11*d - 9*d^2 - 2*d^3 + d^4 = 0, and c = 0.14917103190900041974882341373298677... . - _Vaclav Kotesovec_, Aug 23 2014

%e a(1)=13 because there are 13 generalized Queen paths from (0,0,0) to (1,1,1).

%p b:= proc(x, y, z) option remember; `if`(x=0 and y=0 and z=0, 1,

%p       add(b(x-i, y, z), i=1..x)+ add(b(x, y-i, z), i=1..y)+

%p       add(b(x, y, z-i), i=1..z)+ add(b(x-i, y-i, z), i=1..min(x, y))+

%p       add(b(x-i, y, z-i), i=1..min(x, z))+ add(b(x, y-i, z-i),

%p       i=1..min(y, z))+ add(b(x-i, y-i, z-i), i=1..min(x, y, z)))

%p     end:

%p a:= n-> b(n$3): seq(a(n), n=0..20);  # _Alois P. Heinz_, Jul 23 2012

%t q[1, 1, 1] = 1; q[1, 1, 2] = 1; q[1, 2, 1] = 1; q[1, 1, 2] = 1; q[i_, j_, k_] := q[i, j, k] = Sum[q[x, j, k], {x, 1, i - 1}] + Sum[q[i, y, k], {y, 1, j - 1}] + Sum[q[i, j, z], {z, 1, k - 1}] + Sum[q[i - w, j - w, k], {w, 1, Min[i, j]}] + Sum[q[i, j - w, k - w], {w, 1, Min[j, k]}] + Sum[q[i - w, j, k - w], {w, 1, Min[i, k]}] + Sum[q[i - w, j - w, k - w], {w, 1, Min[i, j, k]}]; a[n_] := q[n, n, n];

%Y A132595 gives the two-dimensional version of this sequence.

%K nonn

%O 0,2

%A Martin J. Erickson (erickson(AT)truman.edu), Aug 30 2008