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

%I #73 Mar 15 2023 20:03:42

%S 1,2,6,17,61,220,883,3597,15232,65130,282294,1229729,5384065,23630332,

%T 103922707,457561989,2016346540,8890227762,39212714934,173001054449,

%U 763388725141,3368934926716,14868728620387,65626328874621,289666423135048,1278582804528090

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

%C If all rotations and reflections are considered, a(2)=4 instead of 6.

%H Thomas Garrison, <a href="/A347825/b347825.txt">Table of n, a(n) for n = 0..1000</a>

%H Soumil Mukherjee, Thomas Garrison, <a href="/A347825/a347825_1.pdf">2 X n tiling up to symmetries of a rectangle</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (9,-19,-33,143,-63,-175,147).

%F Define V(n) to be the set of tilings that are vertically symmetric.

%F Define H(n) to be the set of tilings that are horizontally symmetric.

%F Define R(n) to be the set of tilings that are rotationally symmetric.

%F a(n) = (c(n) + |V(n)| + |H(n)| + |R(n)|)/4 for n > 0, where:

%F c(n) = A034999(n),

%F |H(n)| = 2 * (3^n-1),

%F |V(n)| = c(n/2+1) - c(n/2) for even n; otherwise c(floor(n/2)+1),

%F |R(n)| = 2*c(n/2) for even n; otherwise c(floor(n/2)+1).

%F From _Andrew Howroyd_, Feb 08 2022: (Start)

%F a(n) = (c(n) + 2*3^(n-1) + c(floor((n+1)/2)) + c(floor((n+2)/2)))/4 for n > 0, where c(n) = A034999(n).

%F a(n) = 9*a(n-1) - 19*a(n-2) - 33*a(n-3) + 143*a(n-4) - 63*a(n-5) - 175*a(n-6) + 147*a(n-7) for n > 7.

%F G.f.: (1 - 7*x + 7*x^2 + 34*x^3 - 55*x^4 - 31*x^5 + 66*x^6 - 7*x^7)/((1 - 3*x)*(1 - 6*x + 7*x^2)*(1 - 6*x^2 + 7*x^4)).

%F (End)

%F a(n) ~ k*(3 + sqrt(2))^n, where k = (4 + sqrt(2))/56. - _Stefano Spezia_, Feb 17 2022

%e The a(2) = 6 ways to partition are:

%e +-------+ +---+---+ +-------+

%e | | | | | | |

%e | | | | | +-------+

%e | | | | | | |

%e +-------+ +---+---+ +-------+

%e .

%e +---+---+ +-------+ +---+---+

%e | | | | | | | |

%e | +---+ +---+---+ +---+---+

%e | | | | | | | | |

%e +---+---+ +---+---+ +---+---+

%o (Python)

%o # By Soumil Mukherjee

%o # Algebraic solutions to the number of ways to tile a 2 X n grid

%o import sys

%o # Total number of tilings

%o # Counts different reflections and rotations as distinct

%o counts = [1,2,8]

%o def tilings(n):

%o if (n < len(counts)): return counts[n]

%o for i in range(len(counts), n+1):

%o val = 6 * counts[i-1] - 7 * counts[i-2]

%o counts.append(val)

%o return counts[n]

%o def getCounts(n):

%o return counts[n]

%o def horizontallySymmetric(i):

%o if i == 0: return 1

%o return 2 * (3 ** (i-1))

%o def verticallySymmetric(i):

%o if i == 0: return 1

%o k = i//2

%o if (i % 2 == 0):

%o return counts[k+1] - counts[k]

%o else:

%o return counts[k+1]

%o def rotationallySymmetric(i):

%o if i == 0: return 1

%o k = i//2

%o if (i % 2 == 0):

%o return 2 * counts[k]

%o else:

%o return counts[k+1]

%o def perfectlySymmetric(i):

%o if i == 0: return 1

%o k = i//2

%o if (i % 2 == 0):

%o return 4 * (3 ** (k-1))

%o else:

%o return 2 * (3 ** k)

%o def asymmetric(i):

%o return (

%o counts[i]

%o - verticallySymmetric(i)

%o - horizontallySymmetric(i)

%o - rotationallySymmetric(i)

%o + (2 * perfectlySymmetric(i))

%o )

%o def equivalenceClasses(i):

%o tilings(i)

%o return (

%o (

%o counts[i]

%o + verticallySymmetric(i)

%o + horizontallySymmetric(i)

%o + rotationallySymmetric(i)

%o )//4

%o )

%o (PARI) \\ here c(n) is A034999(n)

%o c(n) = polcoef((1-x)*(1-3*x)/(1-6*x+7*x^2) + O(x*x^n), n)

%o a(n) = if(n==0, 1, (c(n) + 2*3^(n-1) + c((n+1)\2) + c((n+2)\2))/4) \\ _Andrew Howroyd_, Feb 08 2022

%Y The 1 X n case is A005418.

%Y Cf. A034999, A068911 (fully symmetric).

%K nonn,easy

%O 0,2

%A _Thomas Garrison_, Jan 26 2022