A329633 Triangle read by rows: T(n,k) is the number of self-avoiding paths of length n-1+2*k from NW to SW corners in the n X n grid graph (0 <= k <= A000217(n-1), n >= 1).
1, 1, 1, 1, 3, 5, 2, 1, 6, 16, 39, 61, 47, 8, 1, 10, 40, 125, 400, 1048, 1905, 2372, 1839, 764, 86, 1, 15, 85, 335, 1237, 4638, 15860, 44365, 99815, 181995, 262414, 285086, 218011, 104879, 26344, 1770
Offset: 1
Examples
T(3,0) = 1;
S
|
*
|
E
T(3,1) = 3;
S--* S--* S
| | |
*--* * *--*
| | |
E E--* E--*
T(3,2) = 5;
S--*--* S--*--* S--*--* S--* S
| | | | |
*--*--* *--* * *--* *--*--*
| | | | |
E E--* E--*--* E--*--* E--*--*
T(3,3) = 2;
S--*--* S *--*
| | | |
*--* * *--* *
| | | |
E *--* E--*--*
Triangle starts:
==========================================================
n\k| 0 1 2 3 4 5 6 ... 10 ... 15
---|------------------------------------------------------
1 | 1;
2 | 1, 1;
3 | 1, 3, 5, 2;
4 | 1, 6, 16, 39, 61, 47, 8;
5 | 1, 10, 40, 125, 400, 1048, 1905, ... , 86;
6 | 1, 15, 85, 335, 1237, 4638, 15860, ......... , 1770;
Links
- Seiichi Manyama, Rows n = 1..9, flattened
Programs
-
Python
# Using graphillion from graphillion import GraphSet import graphillion.tutorial as tl def A329633(n): if n == 1: return [1] universe = tl.grid(n - 1, n - 1) GraphSet.set_universe(universe) start, goal = 1, n paths = GraphSet.paths(start, goal) return [paths.len(n - 1 + 2 * k).len() for k in range(n * (n - 1) // 2 + 1)] print([i for n in range(1, 7) for i in A329633(n)])
Formula
T(n,0) = 1.
T(n,1) = A000217(n-1).