|
| |
|
|
A247150
|
|
Number of paths from (0,0,0) to (n,n,n) avoiding 3 or more consecutive right steps, 3 or more consecutive up steps, and 3 or more consecutive away steps.
|
|
1
|
|
|
|
1, 6, 90, 1314, 21084, 353772, 6128208, 108606408, 1958248980, 35787633828, 661145207064, 12322983505860, 231395387482470, 4372431546366636, 83068148270734740, 1585548331063624992, 30388252830928088010, 584527926996090202428, 11279880522021539956860
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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:
# second Maple program:
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):
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
