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

%I #32 Nov 30 2024 12:58:19

%S 1,1,1,9,17,31,109,251,553,1527,3721,8799,22521,55607,135161,337655,

%T 835305,2051719,5086601,12580007,31019689,76724327,189674697,

%U 468351815,1157626473,2861142183,7068302665,17467362631,43166610985,106658791143,263564545289,651307249159

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

%C 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.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,8,0,6).

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

%F G.f.: 1/(1 - x - 8*x^3 - 6*x^5). - _Stefano Spezia_, Apr 03 2022

%e The a(3) = 9 solutions are as follows:

%e _____ _____ _____

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

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

%e |_|_|_| |_____| |_____|

%e _____ _____ _____

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

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

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

%e _____ _____ _____

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

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

%e |_____| |_|_|_| |_|_|_|.

%e From _Greg Dresden_, Nov 29 2024: (Start)

%e 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).

%e 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:

%e _________ _________ _________

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

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

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

%e _________ _________ _________

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

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

%e |___|_____| |___|_____| |_____|___|. (End)

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

%K nonn,easy

%O 0,4

%A _Drisana Bhatia_, Apr 03 2022

%E Corrected by _Greg Dresden_, Nov 29 2024