A385868 Number of ways to tile a hexagonal strip made up of n equilateral triangles, using triangles, diamonds, and trapezoids.

1, 1, 2, 4, 7, 13, 39, 66, 110, 200, 604, 1032, 1741, 3149, 9476, 16202, 27337, 49461, 148841, 254466, 429308, 776774, 2337580, 3996430, 6742361, 12199339, 36711974, 62764458, 105889743, 191592331, 576566591, 985724436, 1663012914, 3008983882, 9055057632, 15480937786

Offset: 0

Author

Greg Dresden and Sean Choi, Jul 10 2025

Keywords

• nonn
• easy

Comments

Here is the hexagonal strip:

______________ __

/\ /\ /\ /\ / \ /

/\/\/\/\/ ... \/

\ /\ /\ /\ /\ /\

\/\/\/\/\ /\

The three types of tiles are triangles, diamonds, and trapezoids (each of which can be rotated). Here are the three types of tiles:

__ __ __

\ / \ \ / \

\/ and \_\ and /____\.

Compare to A356622 and A356623, which are on a similar board but only use triangles and diamonds.

Examples

			Here is one of the a(13) = 3149 possible tilings for this strip of 13 triangular cells:
   ____________
  /   /\   \   \
 /__ /__\   \ __\
 \      /\  /\
  \____/__\/__\.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (0,0,0,15,0,0,0,9,0,0,0,32,0,0,0,9,0,0,0,1,0,0,0,-1).

Crossrefs

Cf. A356623, A356623.

Programs

Mathematica

a[0] = 1; a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 7; a[5] = 13; a[6] = 39; a[7] = 66;
a[n_] := a[n] = Switch[Mod[n, 4],
    0, a[n-1] + a[n-3] + 2 a[n-4] + 3 a[n-5] + 2 a[n-6] + a[n-7],
    1, a[n-1] + a[n-2] + a[n-4] + a[n-5] + a[n-6],
    2, a[n-1] + a[n-2] + 3 a[n-3] + a[n-4] + 3 a[n-5] + 2 a[n-6] + a[n-7],
    3, a[n-1] + a[n-2] + a[n-3] + a[n-4] + a[n-5] + a[n-6]];
Table[a[n], {n, 0, 40}]

Formula

a(n) = 15*a(n-4) + 9*a(n-8) + 32*a(n-12) + 9*a(n-16) + 1*a(n-20) - 1*a(n-24).

a(4*n+2) = t(2*n+1)^2 + t(2*n)^2 + 2*t(2*n)*t(2*n-1) + a(4*n) + 2*a(4*n-1) + Sum_{i=1..n-1} a(4*i)*(t(2*(n-i))^2 + 2*t(2*(n-i))*t(2*(n-i)-1)) + Sum_{i=1..n-1} a(4*i-1)*2*t(2*(n-i))^2, for t(n) = A000073(n+2).

G.f.: (x^18-x^17+x^16-x^14+4*x^12-6*x^11-x^10+4*x^9+4*x^8-6*x^7-9*x^6+2*x^5+8*x^4-4*x^3 -2*x^2-x-1) / (-x^24+x^20+9*x^16+32*x^12+9*x^8+15*x^4-1). - Alois P. Heinz, Jul 21 2025