A333464 Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NE and SW corners.

1, 0, 2, 20, 752, 84008, 29145982, 30795358024, 99417240957788

Offset: 1

Author

Seiichi Manyama, Mar 22 2020

Keywords

• nonn
• more

Comments

a(11) = 29262010991555584566654. - Seiichi Manyama, Apr 07 2020

Examples

			a(3) = 2;
   S--*--+   S  *--+
         |   |  |  |
   *--+--*   *  +  *
   |         |  |  |
   +--*--E   +--*  E
a(4) = 20;
   S--*--*--+   S--*--*--+   S--*--*--+
            |            |            |
   *--*--+--*   *--*--+--*   *--*  +--*
   |            |            |  |  |
   *  +--*      *  +--*--*   *  +--*
   |  |  |      |  |     |   |
   +--*  *--E   +--*     E   +--*--*--E
   S--*--*--+   S--*--*--+   S--*--*--+
            |            |            |
      *--+--*      *--+--*      *--+  *
      |            |            |  |  |
   *--+  *--*   *--+         *--+  *--*
   |     |  |   |            |
   +--*--*  E   +--*--*--E   +--*--*--E
   S--*--*--+   S--*  *--+   S--*  *--+
            |      |  |  |      |  |  |
         +--*   *--*  +  *      *--+  *
         |      |     |  |            |
   *--+--*      *  +--*  *   *--+--*--*
   |            |  |     |   |
   +--*--*--E   +--*     E   +--*--*--E
   S--*  *--+   S  *--*--+   S  *--*--+
      |  |  |   |  |     |   |  |     |
      *  +  *   *--*  +--*   *  *--+  *
      |  |  |         |      |     |  |
   *--+  *  *   *--+--*      *  +--*  *
   |     |  |   |            |  |     |
   +--*--*  E   +--*--*--E   +--*     E
   S  *--*--+   S  *--*--+   S     *--+
   |  |     |   |  |     |   |     |  |
   *  *  +--*   *  *  +--*   *--*--+  *
   |  |  |      |  |  |               |
   *  +  *      *  +  *--*   *--+--*--*
   |  |  |      |  |     |   |
   +--*  *--E   +--*     E   +--*--*--E
   S     *--+   S     *--+   S     *--+
   |     |  |   |     |  |   |     |  |
   *--*  +  *   *  *--+  *   *  *--+  *
      |  |  |   |  |     |   |  |     |
   *--+  *  *   *  +--*  *   *  +  *--*
   |     |  |   |     |  |   |  |  |
   +--*--*  E   +--*--*  E   +--*  *--E
   S     *--+   S     *--+
   |     |  |   |     |  |
   *  *--+  *   *     +  *
   |  |     |   |     |  |
   *  +     *   *  +--*  *
   |  |     |   |  |     |
   +--*     E   +--*     E
		

Crossrefs

Cf. A007764, A333455.

Programs

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333464(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n
    paths = GraphSet.paths(start, goal)
    for i in range(n):
        paths = paths.including((n - 1) * (i + 1) + 1)
    return paths.len()
print([A333464(n) for n in range(1, 10)])

Ruby

def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x == n - 1 && y == n - 1 && (0..n - 1).all?{|i| used[(n - 1) * (i + 1)] == true}
  cnt = 0
  used[x + y * n] = true
  @move.each{|mo|
    cnt += search(x + mo[0], y + mo[1], n, used)
  }
  used[x + y * n] = false
  cnt
end
def A(n)
  return 1 if n == 1
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333464(n)
  (1..n).map{|i| A(i)}
end
p A333464(6)