A180584 -id:A180584 - cp's OEIS frontend

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

1, 1, 4, 1, 3, 4, 1, 6, 6, 4, 1, 5, 22, 12, 4, 1, 8, 30, 82, 24, 4, 1, 7, 86, 160, 306, 48, 4, 1, 10, 126, 776, 850, 1142, 96, 4, 1, 9, 318, 1484, 7010, 4520, 4262, 192, 4, 1, 12, 510, 6114, 18452, 63674, 24040, 15906, 384, 4, 1, 11, 1182, 12348, 126426, 229698, 578090, 127860, 59362, 768, 4

Offset: 1

Andrew Howroyd, Feb 18 2025

The case for P_n X C_2 is determined using a double edge for C_2.

			Array begins:
=========================================================
n\k | 2   3     4      5       6        7          8 ...
----+---------------------------------------------------
  1 | 1   1     1      1       1        1          1 ...
  2 | 4   3     6      5       8        7         10 ...
  3 | 4   6    22     30      86      126        318 ...
  4 | 4  12    82    160     776     1484       6114 ...
  5 | 4  24   306    850    7010    18452     126426 ...
  6 | 4  48  1142   4520   63674   229698    2588218 ...
  7 | 4  96  4262  24040  578090  2861964   53055038 ...
  8 | 4 192 15906 127860 5247824 35663964 1087362018 ...
   ...

Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.

Columns 2..12 are A123932(n-1), A003945(n-1), A003699, A003731, A180582, A180583, A180584, A180585, A180586, A180587, A180588.
Rows 1..2 are A000012, A103889(n+1).
Cf. A222196 (order of recurrences), A222197 (main diagonal), A270273, A321172.

A180582 Number of Hamiltonian cycles in C_6 X P_n.

Original entry on oeis.org

1, 8, 86, 776, 7010, 63674, 578090, 5247824, 47640092, 432480632, 3926091512, 35641352528, 323554871864, 2937255393440, 26664624744320, 242063463190976, 2197470272854016, 19948799940346880, 181096701955896896, 1644009442040416928, 14924441010395894048, 135485194778650515104

Offset: 1

Artem M. Karavaev, Sep 10 2010

Seiichi Manyama, Table of n, a(n) for n = 1..500
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, signature (9,0,10,-28,-36,-32,-12).

Column k=6 of A359855.

Cf. A003699, A003731, A180583, A180584, A180585, A180586, A180587, A180588.

a(n) = if(n<1, 0, if(n<=8, [1, 8, 86, 776, 7010, 63674, 578090, 5247824][n], -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) ) );
/* Joerg Arndt, Sep 02 2012 */

# 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 A180582(n):
    universe = make_CnXPk(6, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A180582(n) for n in range(1, 30)])  # Seiichi Manyama, Nov 25 2020

a(n) = -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) for n > 8.

G.f.: x*(x +1)*(6*x^6 -14*x^5 -2*x^4 -24*x^3 +16*x^2 -2*x +1)/(12*x^7 +32*x^6 +36*x^5 +28*x^4 -10*x^3 -9*x +1). - Colin Barker, Sep 01 2012

A180583 Number of Hamiltonian cycles in C_7 X P_n.

Original entry on oeis.org

1, 7, 126, 1484, 18452, 229698, 2861964, 35663964, 444486280, 5539931796, 69048910000, 860620499760, 10726732430288, 133697577587000, 1666401898058352, 20769976722986288, 258876295158900832, 3226625529605854320, 40216553455854426560, 501257787787122948736

Offset: 1

Artem M. Karavaev, Sep 10 2010

Andrew Howroyd, Table of n, a(n) for n = 1..500
Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
Index entries for linear recurrences with constant coefficients, signature (12,18,-112,-440,-772,-196,2064,3724,2040,496,128,-16).

Column k=7 of A359855.

Cf. A003699, A003731, A180582, A180584, A180585, A180586, A180587, A180588.

a(n) = -16a(n-12) + 128a(n-11) + 496a(n-10) + 2040a(n-9) + 3724a(n-8) + 2064a(n-7) - 196a(n-6) - 772a(n-5) - 440a(n-4) - 112a(n-3) + 18a(n-2) + 12a(n-1) for n > 13.

G.f.: x*(16*x^12 -16*x^11 +8*x^10 -192*x^9 +588*x^8 +1996*x^7 +700*x^6 -474*x^5 -400*x^4 -42*x^3 +24*x^2 -5*x +1)/(16*x^12 -128*x^11 -496*x^10 -2040*x^9 -3724*x^8 -2064*x^7 +196*x^6 +772*x^5 +440*x^4 +112*x^3 -18*x^2 -12*x +1). - Colin Barker, Sep 01 2012

a(18) onwards from Andrew Howroyd, Feb 18 2025

A222196 Order of linear recurrence for number of Hamiltonian cycles in the graph C_n X P_k as a function of k.

Original entry on oeis.org

1, 2, 3, 7, 12, 20, 51, 74, 246, 303, 1320, 1514, 7936, 8363

Offset: 3

N. J. A. Sloane, Feb 14 2013

Artem M. Karavaev, Hamilton Cycles

Cf. A003699, A003731, A180582, A180583, A180584, A180585, A180586, A180587, A180588.

Cf. also A222195.

cp's OEIS Frontend

A359855 Array read by antidiagonals: T(n,k) is the number of Hamiltonian cycles in the stacked prism graph P_n X C_k, n >= 1, k >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A180582 Number of Hamiltonian cycles in C_6 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A180583 Number of Hamiltonian cycles in C_7 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A222196 Order of linear recurrence for number of Hamiltonian cycles in the graph C_n X P_k as a function of k.

Views

Author

Keywords

Links

Crossrefs