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

%I #32 Jul 07 2021 02:01:41

%S 1,4,13,44,148,498,1676,5640,18980,63872,214944,723336,2434192,

%T 8191616,27566672,92768192,312186304,1050578720,3535439040,

%U 11897565568,40038044736,134737229824,453421769728,1525868548224,5134898635008,17280115002368,58151561641216

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

%H Seiichi Manyama, <a href="/A339850/b339850.txt">Table of n, a(n) for n = 2..1000</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H M. Peto, <a href="https://doi.org/10.31274/rtd-180813-17105">Studies of protein designability using reduced models</a>, Thesis, 2007.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,4,2).

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

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

%e a(2) = 1:

%e *---*

%e / /

%e * *

%e / /

%e *---*

%e a(3) = 4:

%e * *---* *---*---*

%e / \ / / \ /

%e * * * *---* *

%e / / / /

%e *---*---* *---*---*

%e *---*---* *---*---*

%e / / / /

%e * * * * *---*

%e / / \ / / \

%e *---* * *---*---*

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

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

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o def make_T_nk(n, k):

%o grids = []

%o for i in range(1, k + 1):

%o for j in range(1, n):

%o grids.append((i + (j - 1) * k, i + j * k))

%o if i < k:

%o grids.append((i + (j - 1) * k, i + j * k + 1))

%o for i in range(1, k * n, k):

%o for j in range(1, k):

%o grids.append((i + j - 1, i + j))

%o return grids

%o def A339849(n, k):

%o universe = make_T_nk(n, k)

%o GraphSet.set_universe(universe)

%o cycles = GraphSet.cycles(is_hamilton=True)

%o return cycles.len()

%o def A339850(n):

%o return A339849(3, n)

%o print([A339850(n) for n in range(2, 21)])

%Y Row 3 of A339849.

%Y Cf. A339200.

%K nonn

%O 2,2

%A _Seiichi Manyama_, Dec 19 2020