A352789 Number of ways to tile a 3 X n strip with squares and P-shaped heptominoes.

1, 1, 1, 9, 17, 31, 109, 251, 553, 1527, 3721, 8799, 22521, 55607, 135161, 337655, 835305, 2051719, 5086601, 12580007, 31019689, 76724327, 189674697, 468351815, 1157626473, 2861142183, 7068302665, 17467362631, 43166610985, 106658791143, 263564545289, 651307249159

Offset

0,4

Comments

a(n) is also the number of ways to tile a 1 X n strip with squares, eight colors of trominoes, and six colors of pentominoes.

Links

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

Index entries for linear recurrences with constant coefficients, signature (1,0,8,0,6).

Formula

a(n) = a(n-1) + 8*a(n-3) + 6*a(n-5).

G.f.: 1/(1 - x - 8*x^3 - 6*x^5). - Stefano Spezia, Apr 03 2022

Example

The a(3) = 9 solutions are as follows:
   _____   _____   _____
  |_|_|_| |   |_| |_|   |
  |_|_|_| |   |_| |_|   |
  |_|_|_| |_____| |_____|
   _____   _____   _____
  |_    | |    _| | |_|_|
  |_|   | |   |_| |     |
  |_|___| |___|_| |_____|
   _____   _____   _____
  |_|_| | |     | |     |
  |     | |_ _  | |  _ _|
  |_____| |_|_|_| |_|_|_|.
From Greg Dresden, Nov 29 2024: (Start)
For the a(4) = 17 solutions, there is one that is all squares, there are eight that have a single P-shaped heptomino flush left (as shown in the eight pictures above, but with a column of three squares on the right), and there are another eight that have a single P-shaped heptomino flush right (as shown in the eight pictures above, but with a column of three squares on the left).
For the a(5) = 31 solutions, there is one that is all squares, 24 that have one P-shaped heptomino (eight flush left, another eight centered, and another eight flush right), and then another six that have two P-shaped heptominos nested together, as shown in these six drawings here:
   _________   _________   _________
  |   |_    | |   |     | |     |   |
  |   |_|   | |   |_ _  | |  _ _|   |
  |_____|___| |_____|_|_| |_|_|_____|
   _________   _________   _________
  |    _|   | |    _|_| | | |_|_    |
  |   |_|   | |   |     | |     |   |
  |___|_____| |___|_____| |_____|___|. (End)

Mathematica

LinearRecurrence[{1, 0, 8, 0, 6}, {1, 1, 1, 9, 17}, 34];

Crossrefs

Sequence in context: A285009 A228260 A147459 * A188559 A014004 A090994

Adjacent sequences: A352786 A352787 A352788 * A352790 A352791 A352792

Keyword

nonn,easy

Author

Drisana Bhatia, Apr 03 2022

Extensions

Corrected by Greg Dresden, Nov 29 2024

Status

approved