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

Author

Seiichi Manyama, Dec 19 2020

Keywords

• nonn

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)

Crossrefs

Row 4 of A339849.

Cf. A339201.

Programs

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

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

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