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

Author

Seiichi Manyama, Mar 30 2020

Keywords

• nonn
• tabf

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

Crossrefs

Row sums give A271507.

T(n,(n-1)*n/2) gives A000532(n).

Cf. A000217, A333520.

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).