cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A321172 Triangle read by rows: T(m,n) = number of Hamiltonian cycles on m X n grid of points (m >= 2, 2 <= n <= m).

Original entry on oeis.org

1, 1, 0, 1, 2, 6, 1, 0, 14, 0, 1, 4, 37, 154, 1072, 1, 0, 92, 0, 5320, 0, 1, 8, 236, 1696, 32675, 301384, 4638576, 1, 0, 596, 0, 175294, 0, 49483138, 0, 1, 16, 1517, 18684, 1024028, 17066492, 681728204, 13916993782, 467260456608
Offset: 2

Views

Author

Robert FERREOL, Jan 10 2019

Keywords

Comments

Orientation of the path is not important; you can start going either clockwise or counterclockwise. Paths related by symmetries are considered distinct.
The m X n grid of points when drawn forms a (m-1) X (n-1) rectangle of cells, so m-1 and n-1 are sometimes used as indices instead of m and n (see, e. g., Kreweras' reference below).
These cycles are also called "closed non-intersecting rook's tours" on m X n chess board.

Examples

			T(5,4)=14 is illustrated in the links above.
Table starts:
=================================================================
m\n|  2    3      4       5         6           7            8
---|-------------------------------------------------------------
2  |  1    1      1       1         1           1            1
3  |  1    0      2       0         4           0            8
4  |  1    2      6      14        37          92          236
5  |  1    0     14       0       154           0         1696
6  |  1    4     37     154      1072        5320        32675
7  |  1    0     92       0      5320           0       301384
8  |  1    8    236    1696     32675      301384      4638576
The table is symmetric, so it is completely described by its lower-left half.

Links

Crossrefs

Row/column k=4..12 are: (with interspersed zeros for odd k): A006864, A006865, A145401, A145416, A145418, A160149, A180504, A180505, A213813.
Cf. A003763 (bisection of main diagonal), A222200 (subdiagonal), A231829, A270273, A332307.
T(n,2n) gives A333864.

Programs

  • Python
    # Program due to Laurent Jouhet-Reverdy
def cycle(m, n):
     if (m%2==1 and n%2==1): return 0
     grid = [[0]*n for _ in range(m)]
     grid[0][0] = 1; grid[1][0] = 1
     counter = [0]; stop = m*n-1
     def run(i, j, nb_points):
         for ni, nj in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)] :
             if  0<=ni<=m-1 and 0<=nj<=n-1 and grid[ni][nj]==0 and (ni,nj)!=(0,1):
                 grid[ni][nj] = 1
                 run(ni, nj, nb_points+1)
                 grid[ni][nj] = 0
             elif (ni,nj)==(0,1) and nb_points==stop:
                 counter[0] += 1
     run(1, 0, 2)
     return counter[0]
L=[];n=7#maximum for a time < 1 mn
for i in range(2,n):
    for j in range(2,i+1):
       L.append(cycle(i,j))
print(L)

Formula

T(m,n) = T(n,m).
T(2m+1,2n+1) = 0.
T(2n,2n) = A003763(n).
T(n,n+1) = T(n+1,n) = A222200(n).
G. functions , G_m(x)=Sum {n>=0} T(m,n-2)*x^n after Stoyan's link p. 18 :
G_2(x) = 1/(1-x) = 1+x+x^2+...
G_3(x) = 1/(1-2*x^2) = 1+2*x^2+4*x^4+...
G_4(x) = 1/(1-2*x-2*x^2+2*x^3-x^4) = 1+2*x+6*x^2+...
G_5(x) = (1+3*x^2)/(1-11*x^2-2*x^6) = 1+14*x^2+154*x^4+...

Extensions

More terms from Pontus von Brömssen, Feb 15 2021

A339118 Number of cycles in the grid graph P_6 X P_n.

Original entry on oeis.org

15, 275, 5034, 80626, 1222363, 18438929, 279285399, 4237530095, 64300829449, 975566486675, 14800469958185, 224540402345213, 3406558215857382, 51681816786790684, 784078741397570677, 11895467318139343215, 180469294422664219486, 2737947622842077799930
Offset: 2

Views

Author

Seiichi Manyama, Nov 24 2020

Keywords

Links

Crossrefs

Cf. A140517, A145401, A231829.

Programs

  • Python
    # Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
def A339118(n):
    return A(6, n)
print([A339118(n) for n in range(2, 13)])

Formula

Empirical g.f.: -x^2 * (15 - 325*x + 3889*x^2 - 32204*x^3 + 166496*x^4 - 439661*x^5 + 117553*x^6 + 2506529*x^7 - 5691052*x^8 - 128310*x^9 + 16209330*x^10 - 15148184*x^11 - 17089827*x^12 + 28709449*x^13 + 11141815*x^14 - 27136640*x^15 - 13792528*x^16 + 20876587*x^17 + 15963209*x^18 - 11646759*x^19 - 10681356*x^20 + 3192142*x^21 + 3419602*x^22 - 252986*x^23 - 401310*x^24 - 43774*x^25 + 13852*x^26 + 2950*x^27 - 278*x^28 - 48*x^29 + 4*x^30) / ((-1 + x)^2 * (-1 + 38*x - 580*x^2 + 4945*x^3 - 26274*x^4 + 84913*x^5 - 122213*x^6 - 183068*x^7 + 1124479*x^8 - 1544617*x^9 - 1129508*x^10 + 5346947*x^11 - 3023145*x^12 - 6147688*x^13 + 6904233*x^14 + 3952819*x^15 - 5690282*x^16 - 4144167*x^17 + 3164355*x^18 + 4915006*x^19 - 1267655*x^20 - 3336331*x^21 + 82962*x^22 + 1051157*x^23 + 93428*x^24 - 119962*x^25 - 23089*x^26 + 2688*x^27 + 1368*x^28 - 34*x^29 - 30*x^30 + 2*x^31)). - Vaclav Kotesovec, Dec 09 2020

Extensions

Terms a(13) and beyond from Andrew Howroyd, Dec 08 2020

A005390 Number of Hamiltonian circuits on 2n X 6 rectangle.

Original entry on oeis.org

1, 37, 1072, 32675, 1024028, 32463802, 1033917350, 32989068162, 1053349394128, 33643541208290, 1074685815276400, 34330607094625734, 1096704136430950646, 35034883701169366742, 1119214052513009716324, 35754123580486507079548
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A145401.

Programs

  • Magma
    R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1 -16*x -87*x^2 +1070*x^3 -2206*x^4 +1960*x^5 -2448*x^6 +1053*x^7 +392*x^8 -1517*x^9 +1012*x^10 -120*x^11 -28*x^12 -2*x^13)/(1 -53*x + 802*x^2 -4463*x^3 +10928*x^4 -13708*x^5 +12157*x^6 -7032*x^7 +11272*x^8 -15064*x^9 +13336*x^10 -5948*x^11 +792*x^12 +96*x^13 +4*x^14) )); // G. C. Greubel, Nov 17 2022
  • Mathematica
    Rest@CoefficientList[Series[x*(1 -16*x -87*x^2 +1070*x^3 -2206*x^4 +1960*x^5 -2448*x^6 +1053*x^7 +392*x^8 -1517*x^9 +1012*x^10 -120*x^11 -28*x^12 -2*x^13)/(1 -53*x + 802*x^2 -4463*x^3 +10928*x^4 -13708*x^5 +12157*x^6 -7032*x^7 +11272*x^8 -15064*x^9 +13336*x^10 -5948*x^11 +792*x^12 +96*x^13 +4*x^14), {x,0,40}], x] (* G. C. Greubel, Nov 17 2022 *)
  • SageMath
    def g(x): return x*(1 -16*x -87*x^2 +1070*x^3 -2206*x^4 +1960*x^5 -2448*x^6 +1053*x^7 +392*x^8 -1517*x^9 +1012*x^10 -120*x^11 -28*x^12 -2*x^13)/(1 -53*x + 802*x^2 -4463*x^3 +10928*x^4 -13708*x^5 +12157*x^6 -7032*x^7 +11272*x^8 -15064*x^9 +13336*x^10 -5948*x^11 +792*x^12 +96*x^13 +4*x^14)
def A005390_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( g(x) ).list()
a=A005390_list(40); a[1:] # G. C. Greubel, Nov 17 2022

Formula

a(n) = A145401(2*n). - Sean A. Irvine, Jun 11 2016
G.f.: x*(1 - 16*x - 87*x^2 + 1070*x^3 - 2206*x^4 + 1960*x^5 - 2448*x^6 + 1053*x^7 + 392*x^8 - 1517*x^9 + 1012*x^10 - 120*x^11 - 28*x^12 - 2*x^13)/(1 - 53*x + 802*x^2 - 4463*x^3 + 10928*x^4 - 13708*x^5 + 12157*x^6 - 7032*x^7 + 11272*x^8 - 15064*x^9 + 13336*x^10 - 5948*x^11 + 792*x^12 + 96*x^13 + 4*x^14). - G. C. Greubel, Nov 18 2022

Extensions

More terms from André Pönitz (poenitz(AT)htwm.de), Jun 11 2003

A222195 Order of linear recurrence for number of Hamiltonian cycles in the graph P_n X P_{2k} (n odd) or P_n X P_k (n even), as a function of k.

Original entry on oeis.org

1, 4, 3, 14, 18, 66, 104, 346, 671, 2086, 4479, 13523
Offset: 3

Views

Author

N. J. A. Sloane, Feb 14 2013

Keywords

Links

Crossrefs

Cf. A006864, A006865, A145401, A145416, A145418, A160149, A180504, A180505.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.