A143734 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.

1, 13, 638, 41476, 3015296, 232878412, 18691183682, 1540840801552, 129548309399618, 11057865563760844, 955237244106091682, 83324522236732005112, 7327068320498628273506, 648679579345635742189498, 57761885964038080406607410, 5169168679056263697679753150

Offset

0,2

Comments

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).

Links

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..250 (first 81 terms from Alois P. Heinz)

Formula

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).

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

Example

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

Maple

b:= proc(x, y, z) option remember; `if`(x=0 and y=0 and z=0, 1,
      add(b(x-i, y, z), i=1..x)+ add(b(x, y-i, z), i=1..y)+
      add(b(x, y, z-i), i=1..z)+ add(b(x-i, y-i, z), i=1..min(x, y))+
      add(b(x-i, y, z-i), i=1..min(x, z))+ add(b(x, y-i, z-i),
      i=1..min(y, z))+ add(b(x-i, y-i, z-i), i=1..min(x, y, z)))
    end:
a:= n-> b(n$3): seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2012

Mathematica

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];

Crossrefs

A132595 gives the two-dimensional version of this sequence.

Sequence in context: A362862 A351507 A067407 * A362898 A316331 A217380

Adjacent sequences: A143731 A143732 A143733 * A143735 A143736 A143737

Keyword

nonn

Author

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

Status

approved