A385933 Number of ways to tile a "central bump" strip of length n with 1 X 1 squares and 1 X 3 rectangles.

4, 9, 13, 25, 30, 35, 52, 78, 121, 189, 271, 388, 561, 812, 1204, 1785, 2617, 3837, 5602, 8179, 12000, 17606, 25825, 37881, 55483, 81264, 119089, 174520, 255828, 375017, 549589, 805425, 1180342, 1729779, 2535196, 3715630, 5445561, 7980917, 11696455, 17141772

Offset: 0

Author

Greg Dresden and Saim Usmani, Jul 12 2025

Keywords

• nonn

Comments

a(n) is the number of ways to tile this "central bump" strip of length n (shown here at n=18) with 1 X 1 squares and 1 X 3 rectangles which can be horizontal or vertical:

_

||_

_____________|_|||_____________

|||_|||_|||_|||_|||_|||_|

|||_|

|_|

Examples

			For n = 0 there is no horizontal strip but there is still the "central bump". Here are the a(n) = 4 ways to tile this (disjoint) structure with 1 X 1 squares and 1 X 3 rectangles.
   _           _           _           _
 _|_|_       _|_|_       _|_|_       _|_|_
|_|_|_|     |_____|     |_|_|_|     |_____|
 _____       _____       _____       _____
|_|_|_|     |_|_|_|     |_____|     |_____|
  |_|         |_|         |_|         |_|
		

Crossrefs

Cf. A000930.

Programs

Mathematica

LinearRecurrence[{1,0,1,-1,1,1,0,0,-1},{4,9,13,25,30,35,52,78,121},61]

Formula

a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-5) + a(n-6) - a(n-9).

a(2*n) = a(2*n-2) + a(2*n-4) + 2*a(2*n-6) + a(2*n-7) + a(2*n-8).

a(2*n+1) = a(2*n-1) + 2*a(2*n-4) + a(2*n-5) + 2*a(2*n-6).

a(2*n+3) = 25*b(n)^2 + 26*b(n)*b(n-2) + 10*b(n)*b(n-1) + 9*b(n-2)^2 + 8*b(n-1)*b(n-2) for b(n) = A000930(n) the Narayana Cow sequence.

G.f.: (4 + 5*x + 4*x^2 + 8*x^3 - 3*x^5 - 8*x^6 - x^7)/(1 - x - x^3 + x^4 - x^5 - x^6 + x^9).