OFFSET
0,2
COMMENTS
This is a generalization of A177790 from 2D to 3D.
a(n) is also the number of ternary vectors (symbols 0, 1, and 2, for example) that can be composed with 3n elements (same number of each of the symbols) where each symbol cannot be repeated more than twice consecutively. For example, 0,2,1,0,2,2,1,0,1 is allowed, but 0,2,1,1,1,2,2,0,0 is prohibited because the symbol 1 is repeated 3 times.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..250
M. Erickson, S. Fernando, K. Tran, Enumerating rook and queen paths, Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 37-48.
FORMULA
a(n) = [x^n y^n z^n] ((1+x+x^2)*(1+y+y^2)*(1+z+z^2)/(1-x*y*(1+x)*(1+y)-x*z*(1+x)*(1+z)-y*z*(1+y)*(1+z)-2*x*y*z*(1+x)*(1+y)*(1+z))).
Recurrence (20 terms):
a(p,q,r) = a(p-1,q-1,r) +a(p-1,q-2,r) +a(p-2,q-1,r) +a(p-2,q-2,r) +2*a(p-1,q-1,r-1) +a(p,q-2,r-1) +2*a(p-1,q-2,r-1) +a(p-1,q,r-1) +2*a(p-2,q-1,r-1) +a(p-2,q,r-1) +2*a(p-2,q-2,r-1) +a(p,q-1,r-1) +2*a(p-2,q-2,r-2) +a(p,q-1,r-2) +2*a(p-1,q-1,r-2) +a(p,q-2,r-2) +2*a(p-1,q-2,r-2) +a(p-1,q,r-2) +2*a(p-2,q-1,r-2) +a(p-2,q,r-2), for (p,q,r) > 2.
a(p,q,r) = 0 when p or q or r is negative.
Initial conditions: a(0,0,0) = 1, a(1,0,0) = 1, a(1,1,0) = 2, a(1,1,1) = 6, a(2,0,0) = 1, a(2,1,0) = 3, a(2,1,1) = 12, a(2,2,0) = 6, a(2,2,1) = 30, a(2,2,2) = 90.
Symmetry: a(p,q,r) = a(p,r,q) = a(q,p,r) = a(q,r,p) = a(r,p,q) = a(r,q,p).
EXAMPLE
For n=1 the 6 paths are (000>001>011>111), (000>001>101>111), (000>010>011>111), (000>010>110>111), (000>100>101>111), (000>100>110>111).
MAPLE
f:= proc(p, q, r) option remember;
if p<q or q < r then return procname(op(sort([p, q, r], `>`))) fi;
if r < 0 then return 0 fi;
procname(p-1, q-1, r)+procname(p-1, q-2, r)+procname(p-2, q-1, r)+procname(p-2, q-2, r)+2*procname(p-1, q-1, r-1)+procname(p, q-2, r-1)+2*procname(p-1, q-2, r-1)+procname(p-1, q, r-1)+2*procname(p-2, q-1, r-1)+procname(p-2, q, r-1)+2*procname(p-2, q-2, r-1)+procname(p, q-1, r-1)+2*procname(p-2, q-2, r-2)+procname(p, q-1, r-2)+2*procname(p-1, q-1, r-2)+procname(p, q-2, r-2)+2*procname(p-1, q-2, r-2)+procname(p-1, q, r-2)+2*procname(p-2, q-1, r-2)+procname(p-2, q, r-2)
end proc:
f(0, 0, 0) := 1: f(1, 0, 0) := 1:
f(1, 1, 0) := 2: f(1, 1, 1) := 6:
f(2, 0, 0) := 1: f(2, 1, 0) := 3:
f(2, 1, 1) := 12: f(2, 2, 0) := 6:
f(2, 2, 1) := 30: f(2, 2, 2) := 90:
seq(f(n, n, n), n=0..30); # Robert Israel, Nov 26 2014
# Alternative:
b:= proc(i, j, k, t) option remember; `if`(max(i, j, k)=0, 1,
`if`(j>0, b(j-1, `if`(i<k, [i, k], [k, i])[], 1), 0)+
`if`(k>0, b(k-1, `if`(i<j, [i, j], [j, i])[], 1), 0)+
`if`(i>0 and t>0, b(i-1, j, k, t-1), 0))
end:
a:= n-> b(n$3, 2):
seq(a(n), n=0..30); # Alois P. Heinz, Nov 26 2014
MATHEMATICA
(* Very slow *) a[0] = 1; a[n_] := SeriesCoefficient[((1+x+x^2)*(1+y+y^2)*(1+z+z^2)/(1-x*y*(1+x)*(1+y) - x*z*(1+x)*(1+ z) - y*z*(1+y)*(1+z) - 2*x*y*z*(1+x)*(1+y)*(1+z))), {x, 0, n}, {y, 0, n}, {z, 0, n}]; Table[Print[an = a[n]]; an, {n, 0, 10}] (* Jean-François Alcover, Nov 26 2014 *)
b[i_, j_, k_, t_] := b[i, j, k, t] = If[Max[i, j, k] == 0, 1, If[j>0, If[i<k, b[j-1, i, k, 1], b[j-1, k, i, 1]], 0] + If[k>0, If[i<j, b[k-1, i, j, 1], b[k-1, i, j, 1]], 0] + If[i>0 && t>0, b[i-1, j, k, t-1], 0]]; a[n_] := b[n, n, n, 2]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 27 2014, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jean-Pierre Levrel, Nov 21 2014
STATUS
approved