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

1, 2, 6, 17, 61, 220, 883, 3597, 15232, 65130, 282294, 1229729, 5384065, 23630332, 103922707, 457561989, 2016346540, 8890227762, 39212714934, 173001054449, 763388725141, 3368934926716, 14868728620387, 65626328874621, 289666423135048, 1278582804528090

Offset: 0

Author

Thomas Garrison, Jan 26 2022

Keywords

• nonn
• easy

Comments

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

Examples

			The a(2) = 6 ways to partition are:
  +-------+    +---+---+    +-------+
  |       |    |   |   |    |       |
  |       |    |   |   |    +-------+
  |       |    |   |   |    |       |
  +-------+    +---+---+    +-------+
.
  +---+---+    +-------+    +---+---+
  |   |   |    |       |    |   |   |
  |   +---+    +---+---+    +---+---+
  |   |   |    |   |   |    |   |   |
  +---+---+    +---+---+    +---+---+
		

Links

• Thomas Garrison, Table of n, a(n) for n = 0..1000
• Soumil Mukherjee, Thomas Garrison, 2 X n tiling up to symmetries of a rectangle
• Index entries for linear recurrences with constant coefficients, signature (9,-19,-33,143,-63,-175,147).

Crossrefs

The 1 X n case is A005418.

Cf. A034999, A068911 (fully symmetric).

Programs

PARI

\\ here c(n) is A034999(n)
c(n) = polcoef((1-x)*(1-3*x)/(1-6*x+7*x^2) + O(x*x^n), n)
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

Python

# By Soumil Mukherjee
# Algebraic solutions to the number of ways to tile a 2 X n grid
import sys
# Total number of tilings
# Counts different reflections and rotations as distinct
counts = [1,2,8]
def tilings(n):
    if (n < len(counts)): return counts[n]
    for i in range(len(counts), n+1):
        val = 6 * counts[i-1] - 7 * counts[i-2]
        counts.append(val)
    return counts[n]
def getCounts(n):
  return counts[n]
def horizontallySymmetric(i):
    if i == 0: return 1
    return 2 * (3 ** (i-1))
def verticallySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return counts[k+1] - counts[k]
    else:
        return counts[k+1]
def rotationallySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return 2 * counts[k]
    else:
        return counts[k+1]
def perfectlySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return 4 * (3 ** (k-1))
    else:
        return 2 * (3 ** k)
def asymmetric(i):
    return (
        counts[i]
        - verticallySymmetric(i)
        - horizontallySymmetric(i)
        - rotationallySymmetric(i)
        + (2 * perfectlySymmetric(i))
    )
def equivalenceClasses(i):
    tilings(i)
    return (
        (
          counts[i]
          + verticallySymmetric(i)
          + horizontallySymmetric(i)
          + rotationallySymmetric(i)
        )//4
        )

Formula

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

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

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

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

c(n) = A034999(n),

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

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

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

From Andrew Howroyd, Feb 08 2022: (Start)

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

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.

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

(End)

a(n) ~ k*(3 + sqrt(2))^n, where k = (4 + sqrt(2))/56. - Stefano Spezia, Feb 17 2022