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

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

Author

Seiichi Manyama, Dec 19 2020

Keywords

• nonn

Examples

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

Links

• 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).

Crossrefs

Row 3 of A339849.

Cf. A339200.

Programs

Mathematica

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

PARI

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

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 A339850(n):
    return A339849(3, n)
print([A339850(n) for n in range(2, 21)])

Formula

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.