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

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

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.

Example

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

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

Prog

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

Crossrefs

Row 3 of A339849.

Cf. A339200.

Sequence in context: A257674 A027123 A291236 * A273904 A027125 A027127

Adjacent sequences: A339847 A339848 A339849 * A339851 A339852 A339853

Keyword

nonn

Author

Seiichi Manyama, Dec 19 2020

Status

approved