A003752 -id:A003752

Search: a003752 -id:a003752

Displaying 1-5 of 5 results found.

page 1

A268894

Number of Hamiltonian paths in C_n X P_n.

+10
5

1, 4, 144, 4016, 152230, 14557092, 1966154260, 761411682704, 411068703517542, 684434716944151900, 1572754514153890134760, 11579615738168536799184984, 117186519917858266359631481672, 3877921919790491112398750141807648, 176258463464553583688099296874564393850, 26493868301658838913487471166447301509560736

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

This is the number of undirected paths.

LINKS

Table of n, a(n) for n=1..16.

Artem M. Karavaev, Hamilton Paths

Eric Weisstein's World of Mathematics, Hamiltonian Path

Eric Weisstein's World of Mathematics, Stacked Prism Graph

CROSSREFS

Cf. A003763, A222197, A120443, A268838.

Cf. A003752, A003732.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Feb 15 2016

STATUS

approved

A338960

Number of (undirected) paths in C_4 X P_n.

+10
5

12, 444, 7584, 103184, 1246892, 14010212, 150042016, 1554630384, 15735477148, 156604841764, 1539509238384, 14997746124304, 145132198165132, 1397493793301476, 13407313676392384, 128278229316758192, 1224872135665718780, 11678406201771406628, 111224649402691424912, 1058446545979095492816

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

Table of n, a(n) for n = 1..20

PROG

(Python)

# Using graphillion

from graphillion import GraphSet

def make_CnXPk(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))

grids.append((i + (n - 1) * k, i))

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_CnXPk(n, k)

GraphSet.set_universe(universe)

paths = GraphSet.paths(start, goal)

return paths.len()

def B(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 A338960(n):

return B(4, n)

print([A338960(n) for n in range(1, 11)])

CROSSREFS

Cf. A003752, A338709, A338961, A338962, A338963.

KEYWORD

nonn

AUTHOR

Seiichi Manyama, Dec 18 2020

STATUS

approved

A003689

Number of Hamiltonian paths in K_3 X P_n.

+10
3

3, 30, 144, 588, 2160, 7440, 24576, 78912, 248448, 771456, 2371968, 7241856, 21998976, 66586752, 201025920, 605781120, 1823094144, 5481472128, 16470172032, 49464779904, 148508372352, 445764192384, 1337792747904

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

REFERENCES

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

Index entries for linear recurrences with constant coefficients, signature (7,-16,12).

FORMULA

a(n) = 7*a(n-1) - 16*a(n-2) + 12*a(n-3), n>5.

a(n) = 128 * 3^(n-2) - (21*n + 57) * 2^(n-2), n>2. - Ralf Stephan, Sep 26 2004

G.f.: 3*x*(1+3*x-6*x^2+8*x^3-4*x^4) / ((1-3*x)*(1-2*x)^2). [R. J. Mathar, Dec 16 2008]

MATHEMATICA

Join[{3, 30}, LinearRecurrence[{7, -16, 12}, {144, 588, 2160}, 30]] (* Harvey P. Dale, Apr 26 2014 *)

CoefficientList[Series[3 (1 + 3 x - 6 x^2 + 8 x^3 - 4 x^4)/((1 - 3 x) (1 - 2 x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 27 2014 *)

PROG

(Magma) [3, 30] cat [128*3^(n-2)-(21*n+57)*2^(n-2): n in [3..30]]; // Vincenzo Librandi, Apr 27 2014

(Python)

# Using graphillion

from graphillion import GraphSet

def make_CnXPk(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))

grids.append((i + (n - 1) * k, i))

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_CnXPk(n, k)

GraphSet.set_universe(universe)

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

return paths.len()

def B(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 A003689(n):

return B(3, n)

print([A003689(n) for n in range(1, 21)]) # Seiichi Manyama, Dec 18 2020

CROSSREFS

Cf. A003732, A003752, A268894.

KEYWORD

nonn,easy

AUTHOR

Frans J. Faase

STATUS

approved

A295786

a(n) = A173675(A025487(n)).

+10
2

1, 1, 1, 4, 1, 8, 1, 14, 72, 1, 20, 22, 584, 1, 62, 32, 4016, 1, 132, 16880, 44, 45696, 276, 24656, 1, 336, 413484, 58, 11323440, 1006, 140624, 1, 688, 9044404, 74, 2384871120, 3610, 2480304, 761960, 1, 35281856, 1578, 68984506112, 4324, 183901520, 92, 446907448224, 12010, 677849536, 3976704, 1, 2683205048, 3190, 93749829120

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

Terms in A173675 are only determined by their prime signature. A025487 gives the least positive integer having its prime signature. Combining these sequences removes a lot of duplicates making it somewhat easier to show terms.

a(54) = A284673(5) = 93749829120. - Andrew Howroyd, Oct 26 2019

Many terms from Kloczkowski & Jernigan's Table IV (which has A003752 as a column) show up in the Data section of this sequence. For the (partial) explanation of that, see Andrew Howroyd's comment in A173675. - Andrey Zabolotskiy, Aug 07 2023

LINKS

Table of n, a(n) for n=1..54.

David A. Corneth, Prime signatures for some k and the corresponding values for A173675(k).

A. Kloczkowski and R. L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. II. Cubic lattice, J. Chem. Phys., 109 (1998), 5147-5159.

CROSSREFS

Cf. A025487, A173675.

KEYWORD

nonn

AUTHOR

David A. Corneth, Dec 25 2017

EXTENSIONS

Terms a(29) and beyond from Andrew Howroyd, Oct 26 2019

STATUS

approved

A338297

Number of Hamiltonian paths in C_6 X P_n.

+10
1

6, 228, 4800, 76116, 1094316, 14557092, 183735204, 2230289220, 26275912776, 302338568832, 3412921463352, 37923555328200, 415863933818988, 4509400849281240, 48428461587426108, 515767225814395500, 5452991323044249720, 57282647077608267072, 598324561437126968664, 6217929367753246782612

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..25

PROG

(Python)

# Using graphillion

from graphillion import GraphSet

def make_CnXPk(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))

grids.append((i + (n - 1) * k, i))

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_CnXPk(n, k)

GraphSet.set_universe(universe)

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

return paths.len()

def B(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 A338297(n):

return B(6, n)

print([A338297(n) for n in range(1, 11)])

CROSSREFS

Cf. A003689 (C_3 X P_n), A003752 (C_4 X P_n), A003732 (C_5 X P_n), A268894 (C_n X P_n).

Cf. A180582, A339143, A338962.

KEYWORD

nonn

AUTHOR

Seiichi Manyama, Dec 18 2020

STATUS

approved

page 1

Search completed in 0.055 seconds