|
|
A333686
|
|
Number of self-avoiding paths in (2*n+1) X 3 grid starting the upper left corner, passing through the center of grid and finishing the lower right corner.
|
|
2
|
|
|
1, 10, 101, 1105, 12046, 131399, 1433341, 15635350, 170555501, 1860475165, 20294671306, 221380909199, 2414895329881, 26342467719490, 287352249584501, 3134532277710025, 34192502805225766, 372982998579773399, 4068620481572281621, 44381842298715324430, 484131644804296287101
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
Conjecture: G.f.: (1-3*x-x^2)*(1+3*x+x^2+x^3)/((1-x)*(1+x)*(1+x+x^2)*(1-11*x+x^2)).
Conjecture: a(n) = 10*a(n-1) + 10*a(n-2) - 10*a(n-4) - 10*a(n-5) + a(n-6) for n>5.
|
|
EXAMPLE
|
a(0) = 1;
S--+--E
a(1) = 10;
S--*--* S--*--* S--* S--* S--*
| | | | |
+--* *--+--* +--* + *--+
| | | | |
*--E *--*--E E *--E *--*--E
S *--* S *--* S S S
| | | | | | | | |
* + * *--+ * * +--* *--+--* *--+
| | | | | | | | |
*--* E E *--* E E *--E
a(2) = 101;
S--*--* S--*--* S--*--* S--*--* S--*--*
| | | | |
*--*--* *--*--* *--*--* *--*--* *--*--*
| | | | |
*--+--* *--+ *--+ *--+ * +--*
| | | | | | |
* *--* *--* * *--* *
| | | | |
E *--*--E E *--E E
... and so on.
|
|
PROG
|
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
if n == 0 or k == 0: return 1
universe = tl.grid(2 * n, 2 * k)
GraphSet.set_universe(universe)
start, goal = 1, (2 * n + 1) * (2 * k + 1)
paths = GraphSet.paths(start, goal).including((start + goal) // 2)
return paths.len()
print([A333686(n) for n in range(20)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|