A006864 -id:A006864 - cp's OEIS frontend

A180488 Partial sums of A006864.

0, 1, 3, 9, 23, 60, 152, 388, 984, 2501, 6347, 16117, 40911, 103864, 263664, 669352, 1699216, 4313673, 10950739, 27799745, 70572839, 179157364, 454811656, 1154592108, 2931065640, 7440849549, 18889457819, 47953075565

Offset: 1

Jonathan Vos Post, Sep 07 2010

Index entries for linear recurrences with constant coefficients, signature (3,0,-4,3,-1).

Cf. A006864.

a(n) = +3*a(n-1) -4*a(n-3) +3*a(n-4) -a(n-5). G.f.: x^2 / ( (x-1)*(x^4-2*x^3+2*x^2+2*x-1) ). [R. J. Mathar, Sep 19 2010]

Edited (changed definition, deleted incorrect terms) by N. J. A. Sloane, Sep 09 2010

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

Robert FERREOL, Jan 10 2019

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.

			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.

Huaide Cheng, Rows n=2..17 of triangle, flattened
Robert Ferréol, The T(4,5)=14 hamiltonian cycles on 4 X 5 square grid of points; the T(5,6) = 154 cycles on 5 X 6 grid are reduced to 44 different forms.
Germain Kreweras, Dénombrement des cycles hamiltoniens dans un rectangle quadrillé, European Journal of Combinatorics, Volume 13, Issue 6 (1992), page 476.
Robert Stoyan and Volker Strehl, Enumeration of Hamiltonian Circuits in Rectangular Grids, Séminaire Lotharingien de Combinatoire, B34f (1995), 21 pp.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.

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.

# 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)

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+...

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

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Original entry on oeis.org

1, 1, 4, 8, 23, 55, 144, 360, 921, 2329, 5924, 15024, 38159, 96847, 245888, 624176, 1584593, 4022609, 10211940, 25924088, 65811431, 167069767, 424126160, 1076693080, 2733310377, 6938824361, 17615009476, 44717740000, 113521160607, 288186606623

Offset: 1

Sean A. Irvine, Nov 17 2010

			Illustration of a(1)=a(2)=1:
   .    .__.
   |    .__|
   |    |__
   |    .__|
Illustration of a(3)=4:
   .__.__.    .  .__.    .  .__.    .__.__.
   .__.__|    |__|  |    |  |  |    .__.  |
   |__.__.    .__.  |    |__|  |    |  |  |
   .__.__|    |  |__|    .__.__|    |  |__|

Index entries for linear recurrences with constant coefficients, signature (2, 2, -2, 1).

Row 4 of A271592.

Cf. A000532, A014524, A014523, A181689, A003695, A006864.

LinearRecurrence[{2, 2, -2, 1}, {1, 1, 4, 8}, 30] (* T. D. Noe, Nov 06 2013 *)

G.f.: (x^2-x)/(x^4-2*x^3+2*x^2+2*x-1).

a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4), n > 4.

G.f. formula reverted to the original (correct) value by Stefan Bühler, Nov 06 2013

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Original entry on oeis.org

0, 1, 8, 47, 264, 1480, 8305, 46616, 261663, 1468752, 8244304, 46276385, 259755560, 1458042831, 8184190168, 45938958232, 257861540369, 1447411446840, 8124514782015, 45603992276896, 255981331487648

Offset: 0

N. J. A. Sloane

			Illustration of a(1)=1:
   .__.__.__.
   .__.__.__|
Illustration of a few of the 8 solutions to a(2):
   .__.__.__.    .  .__.__.    .  .__.__.    .__.__.__.
   .__.__.  |    |  |  .__|    |__|  .__|    .__.__.__|
   |__   |  |    |__|  |__.    .__.  |__.    |__.__.__.
   .__|  |__|    .__.__.__|    |  |__.__|    .__.__.__|

Vincenzo Librandi, 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
Index entries for linear recurrences with constant coefficients, signature (7,-9,7,-1).

Even bisection of column 4 of A271592.

Cf. A000532, A181688, A014523, A014585, A003695, A006864.

CoefficientList[Series[x (x + 1)/(x^4 - 7 x^3 + 9 x^2 - 7 x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Oct 15 2013 *)

From Colin Barker, May 20 2013: (Start)
a(n) = 7*a(n-1)-9*a(n-2)+7*a(n-3)-a(n-4).
G.f.: x*(x+1)/(x^4-7*x^3+9*x^2-7*x+1). (End)

Name clarified by Andrew Howroyd, Apr 10 2016

A005389 Number of Hamiltonian circuits on 2n times 4 rectangle.

Original entry on oeis.org

1, 6, 37, 236, 1517, 9770, 62953, 405688, 2614457, 16849006, 108584525, 699780452, 4509783909, 29063617746, 187302518353, 1207084188912, 7779138543857, 50133202843990, 323086934794997, 2082156365731164, 13418602439355485, 86477122654688250, 557307869909156153

Offset: 1

N. J. A. Sloane, Simon Plouffe

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

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
T. G. Schmalz, G. E. Hite and D. J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A 17 (1984), 445-453.
Index entries for linear recurrences with constant coefficients, signature (8,-10,0,-1).

Bisection of A006864.

I:=[1,6,37,236]; [n le 4 select I[n] else 8*Self(n-1) -10*Self(n-2) -Self(n-4): n in [1..41]]; // G. C. Greubel, Nov 17 2022

A005389:=-(-1+2*z+z**2)/(1-8*z+10*z**2+z**4); [Conjectured by Simon Plouffe in his 1992 dissertation.]
a:= n -> (Matrix([[0,1,2,-11]]). Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [8,-10,0,-1][i] else 0 fi)^(n))[1,1]: seq (a(n), n=1..25); # Alois P. Heinz, Aug 05 2008

a[1]=1; a[2]=6; a[3]=37; a[4]=236; a[n_] := a[n] = 8*a[n-1]-10*a[n-2]-a[n-4]; Array[a, 23] (* Jean-François Alcover, Mar 13 2014 *)
CoefficientList[Series[(1 - 2 x - x^2)/(1 - 8 x + 10 x^2 + x^4), {x, 0, 30}], x] (* Vincenzo Librandi, Mar 15 2014 *)

def A005389_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-2*x-x^2)/(1-8*x+10*x^2+x^4) ).list()
A005389_list(40) # G. C. Greubel, Nov 17 2022

G.f.: x*(1-2*x-x^2)/(1-8*x+10*x^2+x^4). - Ralf Stephan, Apr 23 2004

cp's OEIS Frontend

A180488 Partial sums of A006864.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A005389 Number of Hamiltonian circuits on 2n times 4 rectangle.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

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.

Views

Author

Keywords

Links

Crossrefs