A333455 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 NW and SE corners.

1, 2, 10, 124, 4620, 536360, 189313340, 201653395768, 651683788574786

Offset: 1

Author

Seiichi Manyama, Mar 22 2020

Keywords

• nonn
• more

Comments

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

Examples

			a(2) = 2;
   S--*   S
      |   |
      E   *--E
a(3) = 10;
   S--*--*   S--*--*   S--*
         |         |      |
      +--*   *--+--*      +--*
      |      |               |
      *--E   *--*--E         E
   S--*      S--*      S  *--*
      |         |      |  |  |
      +      *--+      *  +  *
      |      |         |  |  |
      *--E   *--*--E   *--*  E
   S  *--*   S         S
   |  |  |   |         |
   *--+  *   *  +--*   *--+--*
         |   |  |  |         |
         E   *--*  E         E
   S
   |
   *--+
      |
      *--E
a(4) = 124;
   S--*--*--*   S--*--*--*   S--*--*--*
            |            |            |
   *--+--*  *   *--+--*  *   *--+  *--*
   |     |  |   |     |  |   |  |  |
   *--*  +--*   *     +--*   *  *--+
      |         |            |
      *--*--E   *--*--*--E   *--*--*--E
   ... and so on.
		

Crossrefs

Cf. A000108, A007764.

Programs

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333455(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 - 1):
        paths = paths.including((n + 1) * i + 1)
    return paths.len()
print([A333455(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 - 2).all?{|i| used[(n + 1) * i] == 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)
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333455(n)
  (1..n).map{|i| A(i)}
end
p A333455(6)