A333510 Number of self-avoiding walks in the n X 2 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.
1, 8, 29, 80, 195, 444, 969, 2056, 4279, 8788, 17885, 36176, 72875, 146412, 293649, 588312, 1177855, 2357188, 4716133, 9434336, 18871091, 37744988, 75493209, 150990120, 301984455, 603973684, 1207952749, 2415911536, 4831829819, 9663667148, 19327342625, 38654694456, 77309399055, 154618809252
Offset: 1
Keywords
Examples
a(1) = 1;
+--+
a(2) = 8;
+--+ + + +--* + *
| | | |
* * *--* * + *--+
-------------------------
*--+ * + *--* * *
| | | |
+ * +--* + + +--+
a(3) = 29;
+--+ + + + + +--* + *
| | | | | |
* * *--* * * * + *--+
| |
* * * * *--* * * * *
--------------------------------
+ * +--* +--* + * + *
| | | | |
* + *--* * * *--* * *
| | | | | |
*--* *--+ * + * + *--+
--------------------------------
*--+ * + * + *--* * *
| | | | |
+ * +--* + * + + +--+
| |
* * * * *--+ * * * *
--------------------------------
* * *--* * * * * *--+
| | |
+ + + * +--* + * *--*
| | | | | |
*--* * + * + *--+ +--*
--------------------------------
*--+ * + * + *--* * *
| | | | |
* * *--* * * * + *--+
| | | | |
+ * + * +--* + * + *
--------------------------------
* * *--* * * * *
| |
* + * * *--* * *
| | | | |
+--* + + + + +--+
Crossrefs
Column k=2 of A333509.
Programs
-
Python
# Using graphillion from graphillion import GraphSet import graphillion.tutorial as tl def A(start, goal, n, k): universe = tl.grid(n - 1, k - 1) GraphSet.set_universe(universe) paths = GraphSet.paths(start, goal) return paths.len() def A333509(n, k): if n == 1: return 1 s = 0 for i in range(1, n + 1): for j in range(k * n - n + 1, k * n + 1): s += A(i, j, k, n) return s def A333510(n): return A333509(n, 2) print([A333510(n) for n in range(1, 20)])
Formula
Conjecture: a(n) = (27*2^n - n^3 - 26*n - 24)/3.
Conjecture: G.f.: x*(1+2*x-5*x^2+2*x^3+2*x^4)/((1-x)^4*(1-2*x)).