login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A333574 Number of  Hamiltonian paths in the n X 2 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side. 2
1, 2, 4, 6, 10, 14, 20, 26, 34, 42, 52, 62, 74, 86, 100, 114, 130, 146, 164, 182, 202, 222, 244, 266, 290, 314, 340, 366, 394, 422, 452, 482, 514, 546, 580, 614, 650, 686, 724, 762, 802, 842, 884, 926, 970, 1014, 1060, 1106, 1154, 1202, 1252, 1302, 1354, 1406, 1460 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Colin Barker, Table of n, a(n) for n = 1..1000

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

FORMULA

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

From Colin Barker, Mar 27 2020: (Start)

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

a(n) = (9 + (-1)^(1+n) - 4*n + 2*n^2) / 4 for n>1.

(End)

EXAMPLE

a(1) = 1;

   +--+

a(2) = 2;

   +  +   *--*

   |  |   |  |

   *--*   +  +

a(3) = 4;

   +  +   +--*   *--+   *--*

   |  |      |   |      |  |

   *  *   *--*   *--*   *  *

   |  |   |         |   |  |

   *--*   *--+   +--*   +  +

PROG

(PARI) N=66; x='x+O('x^N); Vec(x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)))

(Python)

# Using graphillion

from graphillion import GraphSet

import graphillion.tutorial as tl

def A(start, goal, n, k):

    universe = tl.grid(n - 1, k - 1)

    GraphSet.set_universe(universe)

    paths = GraphSet.paths(start, goal, is_hamilton=True)

    return paths.len()

def A333571(n, k):

    if n == 1: return 1

    s = 0

    for i in range(1, n + 1):

        for j in range(k * n - n + 1, k * n + 1):

            s += A(i, j, k, n)

    return s

def A333574(n):

    return A333571(n, 2)

print([A333574(n) for n in range(1, 25)])

CROSSREFS

Column k=2 of A333571.

Cf. A333510.

Sequence in context: A094589 A071425 A115065 * A008804 A001307 A322010

Adjacent sequences:  A333571 A333572 A333573 * A333575 A333576 A333577

KEYWORD

nonn,easy

AUTHOR

Seiichi Manyama, Mar 27 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 17:43 EDT 2020. Contains 337393 sequences. (Running on oeis4.)