A034182 Number of not-necessarily-symmetric n X 2 crossword puzzle grids.

1, 5, 15, 39, 97, 237, 575, 1391, 3361, 8117, 19599, 47319, 114241, 275805, 665855, 1607519, 3880897, 9369317, 22619535, 54608391, 131836321, 318281037, 768398399, 1855077839, 4478554081, 10812186005, 26102926095, 63018038199, 152139002497, 367296043197

Offset: 1

Author

Erich Friedman

Keywords

• nonn
• easy

Comments

n X 2 binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row. - R. H. Hardin, Mar 21 2002

Define a triangle with T(n,1) = T(n,n) = n*(n-1) + 1, n>=1, and its interior terms via T(r,c) = T(r-1,c) + T(r-1,c-1)+ T(r-2,c-1), 2<=cJ. M. Bergot, Mar 16 2013

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 145.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-1)

Crossrefs

Row 2 of A292357.

Column sums of A059678.

Cf. A001333, A034184, A034187, A052542 (first differences).

Programs

Haskell

a034182 n = a034182_list !! (n-1)
a034182_list = 1 : 5 : (map (+ 4) $
   zipWith (+) a034182_list (map (* 2) $ tail a034182_list))
-- Reinhard Zumkeller, May 23 2013

Mathematica

{1}~Join~NestList[{#2, 2 #2 + #1 + 4} & @@ # &, {1, 5}, 28][[All, -1]] (* Michael De Vlieger, Oct 02 2017 *)

Formula

a(n) = 2a(n-1) + a(n-2) + 4.

(1 + 5x + 15x^2 + ...) = (1 + 2x + 2x^2 + ...) * (1 + 3x + 7x^2 + ...), convolution of A040000 and left-shifted A001333.

a(n) = (-4 + (1-sqrt(2))^(1+n) + (1+sqrt(2))^(1+n))/2. G.f.: x*(1+x)^2/((1-x)*(1 - 2*x - x^2)). - Colin Barker, May 22 2012

a(n) = A001333(n+1)-2. - R. J. Mathar, Mar 28 2013

a(n) = A048739(n-3) +2*A048739(n-2) +A048739(n-1). - R. J. Mathar, Jun 15 2020