|
|
A364439
|
|
a(n) is the number of paths with length 3*n that begin at (0,0), end at (0,0), and do not reach (0,0) at any point in between while 0 <= y <= x at every step, where a path is a sequence of steps in the form (1,1), (1,-1), and (-2,0).
|
|
1
|
|
|
1, 1, 4, 33, 367, 4844, 71597, 1147653, 19559062, 349766457, 6502419671, 124822220086, 2461515013103, 49668479230825, 1022258042480874, 21406231023989503, 455112508356168561, 9807294681518154334, 213897254891041613995, 4715809234441541498539
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
If the constraint is removed that the sequence does not reach (0,0) at any point other than the beginning and end of the sequence, this sequence becomes A005789.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Let A represent the (1,1) step, B represent the (1,-1) step, and C represent the (-2,0) step.
For n = 1, the only valid path is ABC.
For n = 2, the 4 valid paths are AABBCC, AABCBC, ABABCC, ABACBC.
|
|
MAPLE
|
b:= proc(n, l) option remember; `if`(n<1, 1, add((h->
`if`(h[2]>h[1] or h[1]>=n or min(h)<0 or n>1 and h=[0$2],
0, b(n-1, h)))(l-w), w=[[1, 1], [1, -1], [-2, 0]]))
end:
a:= n-> b(3*n-1, [2, 0]):
# second Maple program:
f:= proc(n) option remember; (3*n)!*mul(i!/(n+i)!, i=0..2) end:
a:= proc(n) option remember; `if`(n=0, 1,
f(n)-add(f(n-i)*a(i), i=1..n-1))
end:
|
|
MATHEMATICA
|
f[n_] := f[n] = (3n)!*Product[i!/(n+i)!, {i, 0, 2}];
a[n_] := a[n] = If[n == 0, 1, f[n] - Sum[f[n-i]*a[i], {i, 1, n-1}]];
|
|
PROG
|
(C) /* See Hamon Link */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|