A307026 -id:A307026 - cp's OEIS frontend

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

1, 1, 1, 1, 12, 1, 1, 48, 48, 1, 1, 208, 392, 208, 1, 1, 768, 4678, 4678, 768, 1, 1, 2752, 43676, 171592, 43676, 2752, 1, 1, 9472, 406396, 4743130, 4743130, 406396, 9472, 1, 1, 32000, 3568906, 132202038, 364618672, 132202038, 3568906, 32000, 1

Offset: 1

Andrew Howroyd, Jan 16 2022

			Array begins:
===========================================================
m\n | 1    2      3         4           5             6 ...
----+------------------------------------------------------
  1 | 1    1      1         1           1             1 ...
  2 | 1   12     48       208         768          2752 ...
  3 | 1   48    392      4678       43676        406396 ...
  4 | 1  208   4678    171592     4743130     132202038 ...
  5 | 1  768  43676   4743130   364618672   28808442502 ...
  6 | 1 2752 406396 132202038 28808442502 6544911081900 ...
     ...

Andrew Howroyd, Table of n, a(n) for n = 1..231
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph

Rows 1..5 are A000012, A339760, A339761, A339762, A339763.
Main diagonal is A308129.
Cf. A272445, A307026, A329118, A339098, A339190.

T(m,n) = T(n,m).

A339750 Number of (undirected) paths in the 2 X n king graph.

Original entry on oeis.org

1, 30, 235, 1448, 7909, 40674, 202719, 994268, 4837337, 23441366, 113377235, 547864528, 2646278093, 12779454410, 61709221831, 297968336836, 1438739595201, 6946894643134, 33542671171515, 161958548471736, 782005482553269, 3775857399168946, 18231454211243951, 88029252078796716

Offset: 1

Seiichi Manyama, Dec 15 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 2 of A307026.

Cf. A288516, A339760.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal)
    return paths.len()
def A307026(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339750(n):
    return A307026(n, 2)
print([A339750(n) for n in range(1, 21)])

Empirical g.f.: x*(16*x^4 - 48*x^3 + 32*x^2 - 20*x - 1) / ((x-1)^2 * (2*x - 1)^2 * (4*x^2 + 4*x - 1)). - Vaclav Kotesovec, Dec 16 2020

A339751 Number of (undirected) paths in the 3 X n king graph.

Original entry on oeis.org

3, 235, 5148, 96956, 1622015, 25281625, 375341540, 5384233910, 75321922433, 1034169469257, 13999362291892, 187462552894846, 2489361245031701, 32843155609675341, 431132757745615932, 5637280548371484492, 73484574453020315121, 955615821857238062353, 12403944194214668554202

Offset: 1

Seiichi Manyama, Dec 15 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..40
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 3 of A307026.

Cf. A288527, A339761.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal)
    return paths.len()
def A307026(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339751(n):
    return A307026(n, 3)
print([A339751(n) for n in range(1, 21)])

Empirical g.f.: x*(3 + 142*x - 1234*x^2 + 6033*x^3 - 4437*x^4 + 1913*x^5 - 647*x^6 + 24874*x^7 + 25724*x^8 + 1737*x^9 + 10969*x^10 + 22767*x^11 + 24670*x^12 + 12330*x^13 + 1616*x^14 + 240*x^15 + 1008*x^16) / ((1 - x)^2 * (-1 + 8*x + 14*x^2 + 5*x^3 + 6*x^4)^2*(1 - 13*x - 2*x^2 + 45*x^3 - 24*x^4 - 22*x^5 + 9*x^6 + 8*x^7 - 6*x^8)). - Vaclav Kotesovec, Dec 16 2020

A358665 Number of (undirected) paths in the 7 X n king graph.

Original entry on oeis.org

21, 202719, 375341540, 834776217484, 1482823362091281, 2480146959625512771, 3954100866385811897908, 6098277513580967335984126, 9152733286084921835343938561, 13441847550989968623927296910019, 19393111514791549266474890223886106, 27568262002518118100083519899700564808

Offset: 1

Seiichi Manyama, Dec 12 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 7 of A307026.

Terms a(8) and beyond from Andrew Howroyd, Jan 28 2023

A358626 Number of (undirected) paths in the 4 X n king graph.

Original entry on oeis.org

6, 1448, 96956, 6014812, 329967798, 16997993692, 834776217484, 39563650279918, 1823748204789500, 82228567227405462, 3641260776226602674, 158852482151721371580, 6843583319011989465314, 291698433877308327463184

Offset: 1

Seiichi Manyama, Dec 06 2022

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..25
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 4 of A307026.

Cf. A288033, A338617, A339198, A339201, A339762.

A358920 Number of (undirected) paths in the 5 X n king graph.

Original entry on oeis.org

10, 7909, 1622015, 329967798, 57533191444, 9454839968415, 1482823362091281, 224616420155224372, 33098477832558055458, 4770920988514661692889, 675419680016870426617489, 94197848411355615226343472

Offset: 1

Seiichi Manyama, Dec 06 2022

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..17
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 5 of A307026.

Cf. A288033, A339199, A339202, A339257, A339763.

A358676 Number of (undirected) paths in the 6 X n king graph.

Original entry on oeis.org

15, 40674, 25281625, 16997993692, 9454839968415, 4956907379126694, 2480146959625512771, 1199741105997010103190, 564696981034110130721083, 260043412621117997164783364, 117628771690070383600923005043, 52423243374584008151179491288866

Offset: 1

Seiichi Manyama, Dec 12 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 6 of A307026.

Terms a(12) and beyond from Andrew Howroyd, Jan 28 2023

cp's OEIS Frontend

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A339750 Number of (undirected) paths in the 2 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A339751 Number of (undirected) paths in the 3 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A358665 Number of (undirected) paths in the 7 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A358626 Number of (undirected) paths in the 4 X n king graph.

Views

Author

Keywords

Links

Crossrefs

A358920 Number of (undirected) paths in the 5 X n king graph.

Views

Author

Keywords

Links

Crossrefs

A358676 Number of (undirected) paths in the 6 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions