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

%I #47 Mar 15 2023 20:02:29

%S 1,2,8,34,148,650,2864,12634,55756,246098,1086296,4795090,21166468,

%T 93433178,412433792,1820570506,8036386492,35474325410,156591247016,

%U 691227204226,3051224496244,13468756547882,59453967813584,262442511046330,1158477291582892

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

%C Hankel transform is 1, 4, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... . - _Philippe Deléham_, Dec 10 2011

%H David A. Klarner and Spyros S. Magliveras, <a href="https://doi.org/10.1016/S0195-6698(88)80062-3">The number of tilings of a block with blocks</a>, European Journal of Combinatorics 9 (1988), 317-330.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (6,-7).

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

%F 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

%F G.f.: (1-x)*(1-3*x)/(1-6*x+7*x^2). - _Richard Stanley_, Dec 09 2011

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

%F a(n) = 2*A086351(n-1), n>0. - _R. J. Mathar_, Apr 07 2022

%e For n=2 the a(2) = 8 ways to cut are:

%e .___. .___. .___. .___. .___. .___. .___. .___.

%e | | | | | |___| | |_| |_| | |___| |_|_| |_|_|

%e |___| |_|_| |___| |_|_| |_|_| |_|_| |___| |_|_| .

%Y Column 2 of A116694. - _Alois P. Heinz_, Dec 10 2012

%K nonn,easy

%O 0,2

%A _Erich Friedman_

%E a(0) added by _Richard Stanley_, Dec 09 2011