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

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,2

Links

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)

Formula

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

Mathematica

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

Prog

(PARI) 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]
(Python)
# 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)])

Crossrefs

Row 4 of A339849.

Cf. A339201.

Sequence in context: A071614 A045552 A264381 * A297678 A189451 A133718

Adjacent sequences: A339848 A339849 A339850 * A339852 A339853 A339854

Keyword

nonn

Author

Seiichi Manyama, Dec 19 2020

Status

approved