A034999 Number of ways to cut a 2 X n rectangle into rectangles with integer sides.

1, 2, 8, 34, 148, 650, 2864, 12634, 55756, 246098, 1086296, 4795090, 21166468, 93433178, 412433792, 1820570506, 8036386492, 35474325410, 156591247016, 691227204226, 3051224496244, 13468756547882, 59453967813584, 262442511046330, 1158477291582892

Offset

0,2

Comments

Hankel transform is 1, 4, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... . - Philippe Deléham, Dec 10 2011

Links

Table of n, a(n) for n=0..24.

David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.

Index entries for linear recurrences with constant coefficients, signature (6,-7).

Formula

a(n) = 1+3^(n-1) + Sum_{i=1..n-1} (1+3^(i-1)) a(n-i).

a(n) = 6a(n - 1) - 7a(n - 2), a(n) = ((4 + sqrt(2)) (3 + sqrt(2))^n + (4 - sqrt(2)) (3 - sqrt(2))^n)/14. - N. Sato, May 10 2006

G.f.: (1-x)*(1-3*x)/(1-6*x+7*x^2). - Richard Stanley, Dec 09 2011

E.g.f.: (3 + exp(3*x)*(4*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/7. - Stefano Spezia, Feb 17 2022

a(n) = 2*A086351(n-1), n>0. - R. J. Mathar, Apr 07 2022

Example

For n=2 the a(2) = 8 ways to cut are:
.___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.
|   |  | | |  |___|  | |_|  |_| |  |___|  |_|_|  |_|_|
|___|  |_|_|  |___|  |_|_|  |_|_|  |_|_|  |___|  |_|_|  .

Crossrefs

Column 2 of A116694. - Alois P. Heinz, Dec 10 2012

Sequence in context: A014445 A113440 A296227 * A067336 A245090 A151829

Adjacent sequences: A034996 A034997 A034998 * A035000 A035001 A035002

Keyword

nonn,easy

Author

Erich Friedman

Extensions

a(0) added by Richard Stanley, Dec 09 2011

Status

approved