A288518 -id:A288518 - cp's OEIS frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 213, 108, 15, 21, 275, 1049, 1049, 275, 21, 28, 681, 5034, 9349, 5034, 681, 28, 36, 1664, 23984, 80626, 80626, 23984, 1664, 36, 45, 4040, 114069, 692194, 1222363, 692194, 114069, 4040, 45

Offset: 1

Douglas Boffey, Nov 14 2013

This sequence is read in a table, thus:
    m ->
    1,  3,  6, 10, …
n   3, 13, 40, …
|   6, 40, …
v  10, …
    …
This sequence gives the number of closed, simple loops on a rectangular lattice of dots, where the edges of the loop can be horizontal or vertical.
This is also the number of solutions to an unclued slitherlink puzzle.
Main diagonal is A140517. - Joerg Arndt, Sep 01 2014
Equivalently, the number of cycles in the grid graph P_{m+1} X P_{n+1}. - Andrew Howroyd, Jun 12 2017

			Table starts:
=================================================================
m\n|  1    2      3       4         5           6            7
---|-------------------------------------------------------------
1  |  1    3      6      10        15          21           28...
2  |  3   13     40     108       275         681         1664...
3  |  6   40    213    1049      5034       23984       114069...
4  | 10  108   1049    9349     80626      692194      5948291...
5  | 15  275   5034   80626   1222363    18438929    279285399...
6  | 21  681  23984  692194  18438929   487150371  12947640143...
7  | 28 1664 114069 5948291 279285399 12947640143 603841648931...
... - _Andrew Howroyd_, Jun 12 2017
a(2,2) = 13, thus:
1)        2)        3)        4)        5)
+-+ +     + +-+     + + +     + + +     +-+ +
| |         | |                         | |
+-+ +     + +-+     +-+ +     + +-+     + + +
                    | |         | |     | |
+ + +     + + +     +-+ +     + +-+     +-+ +
6)        7)        8)        9)        10)
+ +-+     +-+-+     + + +     +-+ +     + +-+
  | |     |   |               | |         | |
+ + +     +-+-+     +-+-+     + +-+     +-+ +
  | |               |   |     |   |     |   |
+ +-+     + + +     +-+-+     +-+-+     +-+-+
11)       12)       13)
+-+-+     +-+-+     +-+-+
|   |     |   |     |   |
+-+ +     + +-+     + + +
  | |     | |       |   |
+ +-+     +-+ +     +-+-+

Douglas Boffey and Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..70 from Douglas Boffey)
Wikipedia, Slitherlink

Rows 2..10 are A059020, A288637, A339117, A339118, A339119, A339120, A339121, A358707, A358785.
Main diagonal is A140517.
Cf. A288518, A003763, A222202.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A231829(n, k):
    universe = tl.grid(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A231829(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Nov 24 2020

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

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 14, 20, 14, 1, 1, 22, 62, 62, 22, 1, 1, 32, 132, 276, 132, 32, 1, 1, 44, 336, 1006, 1006, 336, 44, 1, 1, 58, 688, 3610, 4324, 3610, 688, 58, 1, 1, 74, 1578, 12010, 26996, 26996, 12010, 1578, 74, 1, 1, 92, 3190, 38984, 109722, 229348, 109722, 38984, 3190, 92, 1

Offset: 1

Andrew Howroyd, Feb 09 2020

			Array begins:
================================================
m\n | 1  2   3     4      5       6        7
----+-------------------------------------------
  1 | 1  1   1     1      1       1        1 ...
  2 | 1  4   8    14     22      32       44 ...
  3 | 1  8  20    62    132     336      688 ...
  4 | 1 14  62   276   1006    3610    12010 ...
  5 | 1 22 132  1006   4324   26996   109722 ...
  6 | 1 32 336  3610  26996  229348  1620034 ...
  7 | 1 44 688 12010 109722 1620034 13535280 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path

Rows n=1..9 are A000012, A003682, A003685, A003695, A003778, A145402, A358794, A358795, A358796.
Main diagonal is A120443.
Cf. A064298, A231829, A271465, A271592, A288518, A321172.

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

A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).

Original entry on oeis.org

0, 1, 30, 3, 235, 5148, 6, 1448, 96956, 6014812, 10, 7909, 1622015, 329967798, 57533191444, 15, 40674, 25281625, 16997993692, 9454839968415, 4956907379126694, 21, 202719, 375341540, 834776217484, 1482823362091281, 2480146959625512771, 3954100866385811897908

Offset: 1

Eric W. Weisstein, Mar 20 2019

Paths of length zero are not counted here. - Seiichi Manyama, Dec 15 2020

			   0;
   1,    30;
   3,   235,     5148;
   6,  1448,    96956,     6014812;
  10,  7909,  1622015,   329967798, 57533191444;
  15, 40674, 25281625, 16997993692, ...;

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row n=2..5 give: A339750, A339751, A358626, A358920.

Cf. A288033 (n X n king graph), A288518.

# 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
print([A307026(n, k) for n in range(1, 8) for k in range(1, n + 1)])  # Seiichi Manyama, Dec 15 2020

T(1, n) = binomial(n, 2).

T(n, n) = A288033(n).

a(20)-a(28) from Seiichi Manyama, Dec 15 2020

A360199 Array read by antidiagonals: T(m,n) is the number of induced paths in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 3, 8, 3, 6, 25, 25, 6, 10, 58, 94, 58, 10, 15, 117, 270, 270, 117, 15, 21, 218, 681, 1004, 681, 218, 21, 28, 387, 1597, 3330, 3330, 1597, 387, 28, 36, 666, 3592, 10224, 14864, 10224, 3592, 666, 36, 45, 1123, 7880, 29924, 61165, 61165, 29924, 7880, 1123, 45

Offset: 1

Andrew Howroyd, Jan 29 2023

Paths of length zero are not counted here.

			Array begins:
============================================================
m\n|  1   2    3     4      5       6        7         8 ...
---+--------------------------------------------------------
1  |  0   1    3     6     10      15       21        28 ...
2  |  1   8   25    58    117     218      387       666 ...
3  |  3  25   94   270    681    1597     3592      7880 ...
4  |  6  58  270  1004   3330   10224    29924     85036 ...
5  | 10 117  681  3330  14864   61165   238897    907148 ...
6  | 15 218 1597 10224  61165  334536  1723535   8647932 ...
7  | 21 387 3592 29924 238897 1723535 11546874  75134416 ...
8  | 28 666 7880 85036 907148 8647932 75134416 629381852 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Induced path.

Main diagonal is A360200.
Rows 1..2 are A000217(n-1), A360201.
Cf. A287151 (induced connected subgraphs), A288518 (undirected paths), A360196 (induced cycles), A360202 (induced trees), A360916 (maximum induced paths).

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 8, 4, 1, 1, 5, 17, 17, 5, 1, 1, 6, 38, 52, 38, 6, 1, 1, 7, 78, 160, 160, 78, 7, 1, 1, 8, 164, 469, 824, 469, 164, 8, 1, 1, 9, 332, 1337, 3501, 3501, 1337, 332, 9, 1, 1, 10, 680, 3750, 16262, 22144, 16262, 3750, 680, 10, 1

Offset: 1

Andrew Howroyd, Dec 20 2024

These paths are also called Greek-key tours. The path can end anywhere.

			Array begins:
======================================================
m\n | 1 2   3    4     5      6        7         8 ...
----+-------------------------------------------------
  1 | 1 1   1    1     1      1        1         1 ...
  2 | 1 2   3    4     5      6        7         8 ...
  3 | 1 3   8   17    38     78      164       332 ...
  4 | 1 4  17   52   160    469     1337      3750 ...
  5 | 1 5  38  160   824   3501    16262     68591 ...
  6 | 1 6  78  469  3501  22144   144476    899432 ...
  7 | 1 7 164 1337 16262 144476  1510446  13506023 ...
  8 | 1 8 332 3750 68591 899432 13506023 180160012 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)

Main diagonal is A145157.
Rows 1..8 are A000012, A000027, A046994, A046995, A145156, A160240, A160241, A374307.
Cf. A332307, A064298, A271465, A271592, A288518.

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

A288516 Number of (undirected) paths in the ladder graph P_2 X P_n.

Original entry on oeis.org

1, 12, 49, 146, 373, 872, 1929, 4118, 8589, 17644, 35889, 72538, 146021, 293200, 587801, 1177278, 2356541, 4715412, 9433537, 18870210, 37744021, 75492152, 150988969, 301983206, 603972333, 1207951292, 2415909969, 4831828138, 9663665349, 19327340704

Offset: 1

Andrew Howroyd, Jun 10 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Ladder Graph
Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Row 2 of A288518.

Cf. A288032, A137882, A287992, A020874.

Table[18 (2^n - 1) - n (n^2 + 9 n + 41)/3, {n, 20}] (* Eric W. Weisstein, Jun 30 2017 *)
LinearRecurrence[{6, -14, 16, -9, 2}, {1, 12, 49, 146, 373}, 20] (* Eric W. Weisstein, Jun 30 2017 *)
CoefficientList[Series[(-1 - 6 x + 9 x^2 - 4 x^3)/((-1 + x)^4 (-1 + 2 x)), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 30 2017 *)

Vec((1+6*x-9*x^2+4*x^3)/((1-x)^4*(1-2*x))+O(x^25))

a(n) = 18*(2^n - 1) - n*(n^2 + 9*n + 41)/3 \\ Charles R Greathouse IV, Jun 30 2017

a(n) = 18*(2^n - 1) - n*(n^2 + 9*n + 41)/3. - Eric W. Weisstein, Jun 30 2017
a(n) = 6*a(n-1)-14*a(n-2)+16*a(n-3)-9*a(n-4)+2*a(n-5) for n > 5.
G.f.: x*(1+6*x-9*x^2+4*x^3)/((1-x)^4*(1-2*x)).
a(n) =  18*(2^n-1) - (41*n)/3 - 3*n^2 - n^3/3. - Colin Barker, Jun 11 2017

A288032 Number of (undirected) paths in the n X n grid graph.

Original entry on oeis.org

0, 12, 322, 14248, 1530196, 436619868, 343715004510, 766012555199052, 4914763477312679808, 91781780911712980966236, 5028368533802124263609489682, 813124448051069045700905179168520

Offset: 1

Eric W. Weisstein, Jun 04 2017

Paths of length zero are not counted here. - Andrew Howroyd, Jun 10 2017

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A288518.

Cf. A236753, A288033, A288148, A007764, A121785, A120443.

a(6)-a(12) from Andrew Howroyd, Jun 10 2017

A288527 Number of (undirected) paths in the grid graph P_3 X P_n.

Original entry on oeis.org

3, 49, 322, 1618, 7119, 28917, 111360, 412998, 1490095, 5266919, 18329164, 63032354, 214788229, 726753651, 2445603148, 8194841668, 27369348241, 91175639607, 303133174298, 1006289129240, 3336552385073, 11052905264953, 36588907685926, 121056347131508

Offset: 1

Andrew Howroyd, Jun 10 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 3 of A288518.

Cf. A288516.

Empirical: a(n) = 10*a(n-1)-37*a(n-2)+59*a(n-3)-27*a(n-4)-25*a(n-5)+21*a(n-6)+5*a(n-7)-4*a(n-8)-a(n-9) for n>9.

Empirical g.f.: x*(3 + 19*x - 57*x^2 + 34*x^3 + 43*x^4 - 7*x^5 - 13*x^6 - 2*x^7) / ((1 - x)^3*(1 - 2*x - x^2)^2*(1 - 3*x - x^2)). - Colin Barker, Jun 11 2017

A358800 Number of (undirected) paths in the grid graph P_4 X P_n.

Original entry on oeis.org

6, 146, 1618, 14248, 111030, 801756, 5493524, 36213404, 231727206, 1448346368, 8882264970, 53630707124, 319658314238, 1884696886358, 11010327107946, 63818465537674, 367417387464528, 2102996368589366, 11976130801913690, 67900925937645280, 383491738397537356

Offset: 1

Seiichi Manyama, Dec 01 2022

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (27,-318,2162,-9476,28327,-59457,88270,-90466, 57194,-9664,-20392, 21783,-8809,-724,2316,-732,-135,99,0,-4).

Row 4 of A288518.

G.f.: x*(6 - 16*x - 416*x^2 + 4018*x^3 - 17938*x^4 + 50228*x^5 - 97356*x^6 + 131868*x^7 - 116556*x^8 + 55784*x^9 - 2296*x^10 - 18094*x^11 + 20784*x^12 - 12882*x^13 + 1542*x^14 + 1748*x^15 - 430*x^16 - 4*x^17 - 24*x^18 - 2*x^19 + 4*x^20)/((1 - x)^2*(1 - 3*x + x^2)*(1 - 7*x + 12*x^2 - 7*x^3 + 3*x^4 + 2*x^5)^2*(1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)). - Andrew Howroyd, Jan 27 2023

Terms a(14) and beyond from Andrew Howroyd, Jan 27 2023

A358801 Number of (undirected) paths in the grid graph P_5 X P_n.

Original entry on oeis.org

10, 373, 7119, 111030, 1530196, 19506257, 235936139, 2746052608, 31022271550, 342198075407, 3701853692717, 39403644085768, 413754416309036, 4294547371071725, 44133332753598489, 449640869111701814, 4546623490067918046, 45670109992300898801

Offset: 1

Seiichi Manyama, Dec 01 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200 (terms 1..24 from Seiichi Manyama)

Row 5 of A288518.

cp's OEIS Frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A360199 Array read by antidiagonals: T(m,n) is the number of induced paths in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A288516 Number of (undirected) paths in the ladder graph P_2 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A288032 Number of (undirected) paths in the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A288527 Number of (undirected) paths in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A358800 Number of (undirected) paths in the grid graph P_4 X P_n.

Views

Author

Keywords

Links

Crossrefs