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
Examples
For n=2 the a(2) = 8 ways to cut are: .___. .___. .___. .___. .___. .___. .___. .___. | | | | | |___| | |_| |_| | |___| |_|_| |_|_| |___| |_|_| |___| |_|_| |_|_| |_|_| |___| |_|_| .
Links
- 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).
Crossrefs
Column 2 of A116694. - Alois P. Heinz, Dec 10 2012
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
Extensions
a(0) added by Richard Stanley, Dec 09 2011
Comments