A333903 Number of directed Hamiltonian paths in a 2*n X n grid starting at the upper left corner and finishing in the lower left corner.

1, 1, 16, 264, 117852, 43399371, 443064195958, 3575671586791915, 831655228913958996424, 147303585340262824414389642, 774577888161337889995061257722609, 3015734636186832309974653370241824509796, 356606519352227259565296610082412177642016167446

Offset

1,3

Links

Ed Wynn, Table of n, a(n) for n = 1..18

Formula

a(n) = A271592(2*n,n).

Example

a(1) = 1;
   S
   |
   *
   |
   E
a(2) = 1;
   S--*
      |
   *--*
   |
   *--*
      |
   E--*
a(3) = 16;
   S--*--*   S--*--*   S--*--*   S--*--*
         |         |         |         |
   *--*--*   *--*--*   *--*--*   *--*--*
   |         |         |         |
   *--*--*   *--*--*   *  *--*   *  *--*
         |         |   |  |  |   |  |  |
   *--*--*   *--*  *   *--*  *   *  *  *
   |         |  |  |         |   |  |  |
   *--*--*   *  *  *   *--*  *   *--*  *
         |   |  |  |   |  |  |         |
   E--*--*   E  *--*   E  *--*   E--*--*
   S--*--*   S--*--*   S--*--*   S--*--*
         |         |         |         |
   *--*  *   *--*  *   *--*  *   *--*  *
   |  |  |   |  |  |   |  |  |   |  |  |
   *  *--*   *  *--*   *  *  *   *  *  *
   |         |         |  |  |   |  |  |
   *--*--*   *  *--*   *  *--*   *  *  *
         |   |  |  |   |         |  |  |
   *--*  *   *--*  *   *--*--*   *  *  *
   |  |  |         |         |   |  |  |
   E  *--*   E--*--*   E--*--*   E  *--*
   S  *--*   S  *--*   S  *--*   S  *--*
   |  |  |   |  |  |   |  |  |   |  |  |
   *--*  *   *--*  *   *--*  *   *--*  *
         |         |         |         |
   *--*--*   *--*--*   *--*  *   *--*  *
   |         |         |  |  |   |  |  |
   *--*--*   *  *--*   *  *--*   *  *  *
         |   |  |  |   |         |  |  |
   *--*  *   *--*  *   *--*--*   *  *  *
   |  |  |         |         |   |  |  |
   E  *--*   E--*--*   E--*--*   E  *--*
   S  *--*   S  *--*   S  *--*   S  *--*
   |  |  |   |  |  |   |  |  |   |  |  |
   *  *  *   *  *  *   *  *  *   *  *  *
   |  |  |   |  |  |   |  |  |   |  |  |
   *--*  *   *--*  *   *  *  *   *  *  *
         |         |   |  |  |   |  |  |
   *--*--*   *--*  *   *--*  *   *  *  *
   |         |  |  |         |   |  |  |
   *--*--*   *  *  *   *--*  *   *--*  *
         |   |  |  |   |  |  |         |
   E--*--*   E  *--*   E  *--*   E--*--*

Prog

(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333903(n):
    universe = tl.grid(n - 1, 2 * n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, 2 * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A333903(n) for n in range(1, 8)])

Crossrefs

Cf. A000532, A271592, A333604, A333606, A333863.

Sequence in context: A113359 A236516 A187453 * A218062 A220757 A166908

Adjacent sequences: A333900 A333901 A333902 * A333904 A333905 A333906

Keyword

nonn

Author

Seiichi Manyama, Apr 09 2020

Extensions

a(9), a(11), a(13) from Seiichi Manyama

a(8), a(10), a(12), a(14)-a(18) from Ed Wynn, Jun 28 2023

Status

approved