A333580 -id:A333580 - cp's OEIS frontend

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 2, 1, 1, 0, 1, 0, 4, 0, 1, 0, 1, 4, 8, 8, 1, 1, 0, 1, 0, 23, 0, 16, 0, 1, 0, 1, 8, 55, 86, 47, 32, 1, 1, 0, 1, 0, 144, 0, 397, 0, 64, 0, 1, 0, 1, 16, 360, 948, 1770, 1584, 264, 128, 1, 1, 0, 1, 0, 921, 0, 11658, 0, 6820, 0, 256, 0, 1

Offset: 1

Andrew Howroyd, Apr 10 2016

			The start of the sequence as table:
* 1 0   0   0     0     0       0       0          0 ...
* 1 1   1   1     1     1       1       1          1 ...
* 1 0   2   0     4     0       8       0         16 ...
* 1 1   4   8    23    55     144     360        921 ...
* 1 0   8   0    86     0     948       0      10444 ...
* 1 1  16  47   397  1770   11658   59946     359962 ...
* 1 0  32   0  1584     0   88418       0    4999752 ...
* 1 1  64 264  6820 52387  909009 8934966  130373192 ...
* 1 0 128   0 28002     0 7503654       0 2087813834 ...
* ...

Andrew Howroyd, Antidiagonals n = 1..27, flattened

Column 4 is aerated A014524, column 5 is A014585.
Rows include A181688, A181689.
Main diagonal is A000532.
Cf. A333580.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A271592(n, k):
    if k == 1: return 1
    universe = tl.grid(k - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A271592(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])  # Seiichi Manyama, Mar 28 2020

T(n,m)=0 for n odd and m even, T(1,n)=0 for n>1.

T(2,n)=T(n,1)=T(2*n,2)=1, T(3,2*n+1)=T(n+1,3)=2^n.

A001184 Number of simple Hamiltonian paths connecting opposite corners of a 2n+1 X 2n+1 grid.

Original entry on oeis.org

1, 2, 104, 111712, 2688307514, 1445778936756068, 17337631013706758184626, 4628650743368437273677525554148, 27478778338807945303765092195103685118924

Offset: 0

Don Knuth, Dec 07 1995

Cf. A121788, A333580.

a(n) = A121788(2n), n>0. - Ashutosh Mehra, Dec 19 2008

a(7)-a(8) copied from A121788 by Alois P. Heinz, Sep 27 2014

A014584 Number of Hamiltonian paths in a 5 X n grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

0, 1, 1, 8, 20, 104, 378, 1670, 6706, 28417, 117204, 490865, 2039569, 8512474, 35444636, 147780722, 615715196, 2566325356, 10694300534, 44570089963, 185740837148, 774080813649, 3225945847829, 13444117980220, 56028001091944, 233495908297044, 973089296878098, 4055332929187618, 16900521902518438

Offset: 0

N. J. A. Sloane

nonn

The difference between A014584 and A014585 needs to be clarified. - N. J. A. Sloane, Feb 08 2013

The difference is that this sequence counts Hamiltonian paths that start in the lower left corner and end in the upper right. A014585 counts Hamiltonian paths that start in the lower left and finish in the lower right. - Ruben Zilibowitz, Jul 05 2015

Seiichi Manyama, Table of n, a(n) for n = 0..1000
K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.
Index entries for sequences related to graphs, Hamiltonian

Row n=5 of A333580.

Cf. A014585.

The reference gives a generating function.

Definition clarified by Ruben Zilibowitz, Jul 05 2015

a(24)-a(28) from Seiichi Manyama, Mar 27 2020

A333585 Number of Hamiltonian paths in a 10 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 256, 117204, 68939685, 43598351250, 28467653231928, 18879702000329222, 12620031290571348940, 8469937551020819909757, 5696439378813116535052879, 3835239247888770485464962184, 2583576672252172117218927779417, 1740899369113326621618848563838108

Offset: 0

Seiichi Manyama, Mar 27 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Index entries for sequences related to graphs, Hamiltonian

Cf. A014523, A333580.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333585(n):
    return A333580(10, 2 * n + 1)
print([A333585(n) for n in range(7)])

Terms a(7) and beyond from Andrew Howroyd, Jan 30 2022

A333581 Number of Hamiltonian paths in a 6 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 16, 378, 10204, 286395, 8142184, 232408228, 6641558434, 189856823709, 5427696641303, 155171211771501, 4436158800822989, 126824318787312712, 3625748174071085779, 103655548766966797516, 2963380335725281547187, 84719269552230266413889, 2422015949371169505273833

Offset: 0

Seiichi Manyama, Mar 27 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for sequences related to graphs, Hamiltonian

Cf. A014523, A333580.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333581(n):
    return A333580(6, 2 * n + 1)
print([A333581(n) for n in range(10)])

Terms a(10) and beyond from Andrew Howroyd, Jan 30 2022

A333582 Number of Hamiltonian paths in a 7 X n grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 1, 32, 111, 1670, 10204, 111712, 851073, 8261289, 68939685, 637113287, 5521505724, 49977297839, 440051896440, 3947537767621, 34992551369200, 312684850861298, 2779712414621925, 24796726969942763, 220708765035288988, 1967401456946216789, 17520501580778152908

Offset: 1

Seiichi Manyama, Mar 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..500
Index entries for sequences related to graphs, Hamiltonian

Row n=7 of A333580.

Cf. A014584.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333582(n):
    return A333580(n, 7)
print([A333582(n) for n in range(1, 25)])

A333583 Number of Hamiltonian paths in an 8 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 64, 6706, 851073, 114243216, 15695570146, 2178079125340, 303568139329711, 42388918310108440, 5923750747499881068, 828111786035239457647, 115782566867663040724929, 16189114623816733581826838, 2263672174616450290622937801, 316525123224847580237219904819

Offset: 0

Seiichi Manyama, Mar 27 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
Index entries for sequences related to graphs, Hamiltonian

Cf. A014523, A333580.

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

Terms a(7) and beyond from Andrew Howroyd, Jan 30 2022

A333584 Number of Hamiltonian paths in a 9 X n grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 1, 128, 624, 28417, 286395, 8261289, 114243216, 2688307514, 43598351250, 928370853748, 16331387665387, 330593938169845, 6062963019120077, 119575303856316650, 2240422461856052342, 43592076562463162280, 825830699757513748579, 15955080499901505066753

Offset: 1

Seiichi Manyama, Mar 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Index entries for sequences related to graphs, Hamiltonian

Row n=9 of A333580.

Cf. A014584.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333584(n):
    return A333580(n, 9)
print([A333584(n) for n in range(1, 20)])

A333863 Number of Hamiltonian paths in a 2(2n+1) X (2*n+1) grid starting at the upper left corner and finishing in the lower right corner.

Original entry on oeis.org

1, 16, 117204, 440051896440, 825830699757513748579, 769203260676279544212492116449800, 354179806054404909542325896762875458037457353029, 80433401895946253522491939742836167238530417144721958187080077425

Offset: 0

Seiichi Manyama, Apr 08 2020

nonn

Ed Wynn, Table of n, a(n) for n = 0..9

Cf. A001184, A333580, A333585, A333864.

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

a(n) = A333580(2*(2*n+1), 2*n+1).

More terms from Ed Wynn, Jun 28 2023

cp's OEIS Frontend

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A001184 Number of simple Hamiltonian paths connecting opposite corners of a 2n+1 X 2n+1 grid.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A014584 Number of Hamiltonian paths in a 5 X n grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A333585 Number of Hamiltonian paths in a 10 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A333581 Number of Hamiltonian paths in a 6 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A333582 Number of Hamiltonian paths in a 7 X n grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A333583 Number of Hamiltonian paths in an 8 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A333584 Number of Hamiltonian paths in a 9 X n grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A333863 Number of Hamiltonian paths in a 2*(2*n+1) X (2*n+1) grid starting at the upper left corner and finishing in the lower right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

Extensions

A333863 Number of Hamiltonian paths in a 2(2n+1) X (2*n+1) grid starting at the upper left corner and finishing in the lower right corner.