A208215 Number of ways of dividing a 3 X n rectangle into rectangles of integer side lengths.
1, 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, 315981452, 3165414034, 31710994234, 317682195692, 3182564368244, 31883205466534, 319408833724882, 3199866987994304, 32056562443839284, 321145602837871522, 3217266324544621714, 32230871396722195484
Offset: 0
Examples
For n=1 the a(1) = 4 ways to divide 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.
- J. Smith and H. Verrill, On dividing rectangles into rectangles.
- Index entries for linear recurrences with constant coefficients, signature (15,-55,51).
Programs
-
Mathematica
Join[{1}, LinearRecurrence[{15, -55, 51}, {4, 34, 322}, 20]] (* Bruno Berselli, Apr 24 2012 *)
Formula
a(n) = 18*a(n-1) -100*a(n-2) +216*a(n-3) -153*a(n-4) with n>4 (see paper in Link lines, p. 1).
G.f.: 1+2*x*(2-13*x+16*x^2) / (1-15*x+55*x^2-51*x^3) = 1+2*x*(2-19*x+55*x^2-48*x^3) / (1-18*x+100*x^2-216*x^3+153*x^4). [Bruno Berselli, Apr 24 2012]
a(n) = 15*a(n-1) -55*a(n-2) +51*a(n-3) with n>3. [Bruno Berselli, Apr 24 2012]
Extensions
More terms from Bruno Berselli, Apr 24 2012
a(0) added by Alois P. Heinz, Dec 10 2012