A158091 The number of ways that a straight line segment of length n, marked into n equal units, can be surrounded in a plane by one layer of regular polygons of unit edge that fit together without any gaps or overlaps, such that every polygon shares either a vertex or an exact unit edge with the segment. ("Line wreaths of length n.") Ways that differ by reflection or rotation are not counted as different.

21, 114, 154, 348, 748, 1824, 4402, 11177, 28334, 73281, 189501, 493774, 1286655, 3362376, 8787092, 22988862, 60144668, 157418794

Offset: 0

Author

David Pasino, Mar 12 2009

Keywords

• nonn

Comments

If n > 1, the only polygons that can be on the interior of the line are squares or else triangles and hexagons. The only further determining principle on the interior is that no two hexagons can have their bases adjacent on the same side of the line, lest they overlap in area. Such scattering of hexagons leads to Fibonacci numbers in the formula. There are 11 ways to cover the two end units, and depending on the two polygons on an end unit, each end has various ways to be completed to a surrounding of the endpoint.

Formula

a(0) = 21, a(1) = 114, and if n >= 2 let F the Fibonacci sequence A000045 and let m = n/2 if n is even, or m = (n+3)/2 if n is odd, then a(n) = 7 + 6*F(n-2) + 27*F(n-1) + 31*F(n) + F(n-2)^2 + 18*F(n-1)^2 + 25*F(n)^2 + 40*F(n)*F(n-1) + 8*F(n-1)*F(n-2) + 8*F(n)*F(n-2) + 2*F(m)*F(m-1) + (3*F(m-1) + 7*F(m) + F(m-1)^2 + 5*F(m)^2)/2.

That's by slight recombination of how the formula reads off from the 11 configurations of the end units. Then by Fibonacci identities the quadratic terms can be converted to linear combinations of Fibonacci numbers with roughly double the index, producing the following formula, with F as before, and D = 1 if n is odd, D = 0 if n is even:

a(0) = 21, a(1) = 114, and if n >= 2 then a(n) = (9/5)*(F(2n+3) + F(2n+5)) + (1/10)*((51 + 6D)*F(n+2) + (56+6D)*F(n+4)) + (1/2)*(F((n+3D)/2) + 3F((n+4+3D)/2)) + 7 - (8/5)*(-1)^n - (2/5)*(-1)^((n-D)/2).