A339849 -id:A339849 - cp's OEIS frontend

A339190 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph.

3, 4, 4, 8, 16, 8, 16, 120, 120, 16, 32, 744, 2830, 744, 32, 64, 4922, 50354, 50354, 4922, 64, 128, 31904, 1003218, 2462064, 1003218, 31904, 128, 256, 208118, 19380610, 139472532, 139472532, 19380610, 208118, 256, 512, 1354872, 378005474, 7621612496, 22853860116, 7621612496, 378005474, 1354872, 512

Offset: 2

Seiichi Manyama, Nov 27 2020

			Square array T(n,k) begins:
   3,     4,        8,         16,            32,               64, ...
   4,    16,      120,        744,          4922,            31904, ...
   8,   120,     2830,      50354,       1003218,         19380610, ...
  16,   744,    50354,    2462064,     139472532,       7621612496, ...
  32,  4922,  1003218,  139472532,   22853860116,    3601249330324, ...
  64, 31904, 19380610, 7621612496, 3601249330324, 1622043117414624, ...

Seiichi Manyama, Antidiagonals n = 2..12, flattened
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Rows and columns 3..5 give A339200, A339201, A339202.
Main diagonal gives A140519.
Cf. A321172, A339098, A339849.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339190(n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A339190(j + 2, i - j + 2) for i in range(10 - 1) for j in range(i + 1)])

T(n,k) = T(k,n).

A338970 Number of Hamiltonian circuits within parallelograms of size 6 X n on the triangular lattice.

Original entry on oeis.org

1, 148, 3851, 104100, 3292184, 100766213, 3061629439, 93391009587, 2848083212818, 86830428575045, 2647502223122183, 80723479583077760, 2461270742015683063, 75044735473463888913, 2288131799382045208904, 69765663287027937162894, 2127171274594978600181825

Offset: 2

Seiichi Manyama, Dec 22 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..500
Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13.
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 6 of A339849.

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A338970(n):
    return A339849(6, n)
print([A338970(n) for n in range(2, 21)])

a(n) = 17*a(n-1) + 308*a(n-2) + 3718*a(n-3) - 8944*a(n-4) - 203602*a(n-5) - 1760279*a(n-6) + 4214627*a(n-7) + 41830213*a(n-8) + 225676161*a(n-9) - 831546864*a(n-10) - 1396419616*a(n-11) + 512302093*a(n-12) + 33910901047*a(n-13) - 148248035667*a(n-14) - 71591956081*a(n-15) - 513969061657*a(n-16) + 7189182969047*a(n-17) - 715460439786*a(n-18) - 14144097438176*a(n-19) - 98092600745077*a(n-20) + 85281523978859*a(n-21) + 258795398812831*a(n-22) + 401976432666415*a(n-23) - 697015148397353*a(n-24) - 1758566032640649*a(n-25) - 264807487370149*a(n-26) + 4376962161634247*a(n-27) + 3596247130566579*a(n-28) - 6063704165801647*a(n-29) - 8646051339082444*a(n-30) + 5835042622094674*a(n-31) + 6933527488046106*a(n-32) - 7132151429649894*a(n-33) + 20873887165808038*a(n-34) + 29863609327174220*a(n-35) - 87774083631942821*a(n-36) - 68828169378762625*a(n-37) + 225928479008894240*a(n-38) + 166683205556809600*a(n-39) - 356968376341177252*a(n-40) - 245673717744507896*a(n-41) + 422903422959769596*a(n-42) + 289000909472562036*a(n-43) - 361042953299243779*a(n-44) - 202310840488094013*a(n-45) + 242723645635132041*a(n-46) + 82279920889031937*a(n-47) - 155265862998823478*a(n-48) - 13018457616632292*a(n-49) + 67639720944495480*a(n-50) - 9667244690991964*a(n-51) - 31287094134056814*a(n-52) + 1545150609982282*a(n-53) + 8997455545061173*a(n-54) + 24411045321863*a(n-55) + 1327281913998467*a(n-56) - 170070264293775*a(n-57) - 805550117698830*a(n-58) + 216517794712850*a(n-59) - 52923920646375*a(n-60) - 35520984357973*a(n-61) + 51225395752594*a(n-62) - 8890010884230*a(n-63) - 16237588330384*a(n-64) + 11906791455940*a(n-65) - 1733110955966*a(n-66) - 1390781505668*a(n-67) + 906089436294*a(n-68) - 184492249544*a(n-69) - 33856007801*a(n-70) + 30446303315*a(n-71) - 8206589201*a(n-72) + 1104875633*a(n-73) - 70159467*a(n-74) + 579969*a(n-75) + 16576*a(n-76) + 100*a(n-77) for n > 80.

A339622 Number of Hamiltonian circuits within parallelograms of size 7 X n on the triangular lattice.

Original entry on oeis.org

1, 498, 26499, 1475286, 100766213, 6523266332, 418172485806, 26971800950170, 1738936046774850, 112060168171247368, 7222422644817870197, 465494892350086836970, 30001329862709920944426, 1933604967243463575726934, 124622105764386987040047037, 8031972575008760516889720476

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..150
Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. (a(n) is equal to h6(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 7 of A339849.

Cf. A145416.

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339622(n):
    return A339849(7, n)
print([A339622(n) for n in range(2, 8)])

A339850 Number of Hamiltonian circuits within parallelograms of size 3 X n on the triangular lattice.

Original entry on oeis.org

1, 4, 13, 44, 148, 498, 1676, 5640, 18980, 63872, 214944, 723336, 2434192, 8191616, 27566672, 92768192, 312186304, 1050578720, 3535439040, 11897565568, 40038044736, 134737229824, 453421769728, 1525868548224, 5134898635008, 17280115002368, 58151561641216

Offset: 2

Seiichi Manyama, Dec 19 2020

nonn

			a(2) = 1:
      *---*
     /   /
    *   *
   /   /
  *---*
a(3) = 4:
      *   *---*      *---*---*
     / \ /   /        \     /
    *   *   *      *---*   *
   /       /      /       /
  *---*---*      *---*---*
      *---*---*      *---*---*
     /       /      /       /
    *   *   *      *   *---*
   /   / \ /      /     \
  *---*   *      *---*---*

Seiichi Manyama, Table of n, a(n) for n = 2..1000
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.
Index entries for linear recurrences with constant coefficients, signature (2,4,2).

Row 3 of A339849.

Cf. A339200.

Drop[CoefficientList[Series[(x (1 + x))^2/(1 - 2 x - 4 x^2 - 2 x^3), {x, 0, 28}], x], 2] (* Michael De Vlieger, Jul 06 2021 *)

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

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339850(n):
    return A339849(3, n)
print([A339850(n) for n in range(2, 21)])

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

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

A339851 Number of Hamiltonian circuits within parallelograms of size 4 X n on the triangular lattice.

Original entry on oeis.org

1, 13, 80, 549, 3851, 26499, 183521, 1269684, 8782833, 60764640, 420375910, 2908245096, 20119820809, 139192751951, 962962619849, 6661962019139, 46088745527485, 318850883829314, 2205872265781839, 15260652269262421, 105576152878533354, 730396306808551777, 5053023343572544589

Offset: 2

Seiichi Manyama, Dec 19 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..1000
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.
Index entries for linear recurrences with constant coefficients, signature (3,21,44,-5,-47,-26,83,-81,39,-10,1)

Row 4 of A339849.

Cf. A339201.

CoefficientList[Series[x^2(1+10x+20x^2-8x^3-43x^4+9x^5+34x^6-42x^7+24x^8-7x^9+x^10)/(1-3x-21x^2-44x^3+5x^4+47x^5+26x^6-83x^7+81x^8-39x^9+10x^10-x^11),{x,0,30}],x] (* or *) LinearRecurrence[{3,21,44,-5,-47,-26,83,-81,39,-10,1},{1,13,80,549,3851,26499,183521,1269684,8782833,60764640,420375910},30] (* Harvey P. Dale, Mar 30 2023 *)

N=40; a=vector(N); a[2]=1; a[3]=13; a[4]=80; a[5]=549; a[6]=3851; a[7]=26499; a[8]=183521; a[9]=1269684; a[10]=8782833; a[11]=60764640; a[12]=420375910; for(n=13, N, a[n]=3*a[n-1]+21*a[n-2]+44*a[n-3]-5*a[n-4]-47*a[n-5]-26*a[n-6]+83*a[n-7]-81*a[n-8]+39*a[n-9]-10*a[n-10]+a[n-11]); a[2..N]

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339851(n):
    return A339849(4, n)
print([A339851(n) for n in range(2, 21)])

a(n) = 3*a(n-1) + 21*a(n-2) + 44*a(n-3) - 5*a(n-4) - 47*a(n-5) - 26*a(n-6) + 83*a(n-7) - 81*a(n-8) + 39*a(n-9) - 10*a(n-10) + a(n-11) for n > 12.

G.f.: x^2*(1 + 10*x + 20*x^2 - 8*x^3 - 43*x^4 + 9*x^5 + 34*x^6 - 42*x^7 + 24*x^8 - 7*x^9 + x^10) / (1 - 3*x - 21*x^2 - 44*x^3 + 5*x^4 + 47*x^5 + 26*x^6 - 83*x^7 + 81*x^8 - 39*x^9 + 10*x^10 - x^11). - Vaclav Kotesovec, Dec 23 2020

A339852 Number of Hamiltonian circuits within parallelograms of size 5 X n on the triangular lattice.

Original entry on oeis.org

1, 44, 549, 7104, 104100, 1475286, 20842802, 295671198, 4190083085, 59374628434, 841470846944, 11925007688342, 168996943899738, 2394974040514288, 33940795571394262, 480998063196253650, 6816550836218124869, 96601974078400509612, 1369012239935377295854, 19401203058253673198258

Offset: 2

Seiichi Manyama, Dec 19 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..500
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.
Index entries for linear recurrences with constant coefficients, signature (8,62,384,160,-1628,-11310,9700,-16019,102564, -98380,263340, -429661,174728,-361330,147404,284641,24764,182412,-156248, -138559,14756,14496,-3660,-2640,328,80,-8)

Row 5 of A339849.

Cf. A339202.

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339852(n):
    return A339849(5, n)
print([A339852(n) for n in range(2, 21)])

a(2)..a(31) = [1, 44, 549, 7104, 104100, 1475286, 20842802, 295671198, 4190083085, 59374628434, 841470846944, 11925007688342, 168996943899738, 2394974040514288, 33940795571394262, 480998063196253650, 6816550836218124869, 96601974078400509612, 1369012239935377295854, 19401203058253673198258, 274947636268050621400764, 3896469848341602644039976, 55219522831075639350876744, 782553393257523404353337072, 11090096073215866151573834374, 157165289898796544200350430624, 2227296155585971455156172389428, 31564527815820044279227403214372, 447322379530320420841684880901414, 6339309505792160540792742125116082] and

a(n) = 8*a(n-1) + 62*a(n-2) + 384*a(n-3) - 160*a(n-4) - 1628*a(n-5) - 11310*a(n-6) + 9700*a(n-7) - 16019*a(n-8) + 102564*a(n-9) - 98380*a(n-10) + 263340*a(n-11) - 429661*a(n-12) + 174728*a(n-13) - 361330*a(n-14) + 147404*a(n-15) + 284641*a(n-16) + 24764*a(n-17) + 182412*a(n-18) - 156248*a(n-19) - 138559*a(n-20) + 14756*a(n-21) + 14496*a(n-22) - 3660*a(n-23) - 2640*a(n-24) + 328*a(n-25) + 80*a(n-26) - 8*a(n-27) for n > 31.

A339854 Number of Hamiltonian circuits within parallelograms of size n X n on the triangular lattice.

Original entry on oeis.org

1, 4, 80, 7104, 3292184, 6523266332, 56203566442908, 2176852129116199068, 373334515946952014204102, 281931891850296665963970600460, 939652851372937937187518231503848142, 13807942929878598929190143960742601141566220, 893498265685263112931409501489577970162598024007690

Offset: 2

Seiichi Manyama, Dec 19 2020

nonn

			a(2) = 1:
    *---*
   /   /
  *---*
a(3) = 4:
      *   *---*      *---*---*
     / \ /   /        \     /
    *   *   *      *---*   *
   /       /      /       /
  *---*---*      *---*---*
      *---*---*      *---*---*
     /       /      /       /
    *   *   *      *   *---*
   /   / \ /      /     \
  *---*   *      *---*---*

Ed Wynn, Table of n, a(n) for n = 2..16

Main diagonal of A339849.

Cf. A140519.

More terms from Ed Wynn, Jun 28 2023

A339960 Number of Hamiltonian circuits within parallelograms of size 8 X n on the triangular lattice.

Original entry on oeis.org

1, 1676, 183521, 20842802, 3061629439, 418172485806, 56203566442908, 7621726574570613, 1033232532941136255, 139934009951521872490, 18955155770535463735959, 2567688102114635009977537, 347811042296785583958285788, 47113523803568895604053871759, 6381875340326645360658645942215

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..100
Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. (a(n) is equal to h7(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 8 of A339849.

Cf. A145418.

# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339849(n, k):
    universe = make_T_nk(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339960(n):
    return A339849(8, n)
print([A339960(n) for n in range(2, 8)])

A339961 Number of Hamiltonian circuits within parallelograms of size 9 X n on the triangular lattice.

Original entry on oeis.org

1, 5640, 1269684, 295671198, 93391009587, 26971800950170, 7621726574570613, 2176852129116199068, 621423541447699842468, 177129811732376379317558, 50496098726203776039975335, 14395928063309130831417237704, 4103904494029399087473676726278

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..50
Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. (a(n) is equal to h8(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 9 of A339849.

Cf. A160149.

A339962 Number of Hamiltonian circuits within parallelograms of size 10 X n on the triangular lattice.

Original entry on oeis.org

1, 18980, 8782833, 4190083085, 2848083212818, 1738936046774850, 1033232532941136255, 621423541447699842468, 373334515946952014204102, 223802065032649969887333948, 134170413630013820290109500226, 80436114451156297907062202392494, 48216986287603185632341666866663007

Offset: 2

Seiichi Manyama, Dec 25 2020

nonn

Olga Bodroža-Pantić, Harris Kwong and Milan Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs, Discrete Appl. Math. 201 (2016) 1-13. (a(n) is equal to h9(n-1) defined by this paper)
M. Peto, Studies of protein designability using reduced models, Thesis, 2007.

Row 10 of A339849.

Cf. A180504.

cp's OEIS Frontend

A339190 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A338970 Number of Hamiltonian circuits within parallelograms of size 6 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A339622 Number of Hamiltonian circuits within parallelograms of size 7 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A339850 Number of Hamiltonian circuits within parallelograms of size 3 X n on the triangular lattice.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A339851 Number of Hamiltonian circuits within parallelograms of size 4 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A339852 Number of Hamiltonian circuits within parallelograms of size 5 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A339854 Number of Hamiltonian circuits within parallelograms of size n X n on the triangular lattice.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A339960 Number of Hamiltonian circuits within parallelograms of size 8 X n on the triangular lattice.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A339961 Number of Hamiltonian circuits within parallelograms of size 9 X n on the triangular lattice.

Views

Author

Keywords