A272070 Number of ways to quarter a 2n+1 X 2n+1 chessboard with central square removed.

1, 1, 7, 104, 3970, 431932, 137066448, 128095791922, 355704307903818, 2952926822418475378, 73569487283165427567144, 5515501712040561162370942752, 1246743475892797935712690352483842, 850999652841310762943520023896881419780

Offset: 0

Author

Andrew Howroyd, Apr 19 2016

Keywords

• nonn

Comments

The chessboard must be dissected into four identical pieces. All solutions have 90-degree rotational symmetry and solutions that differ only by rotation or reflection are considered equivalent.

The pieces must be polyominoes, without holes. They can't have parts that are only connected through one or more corners: if the piece is larger than one square, each square must share at least one side with some other square of the same piece. - M. F. Hasler, Jun 13 2025

The solutions can be constructed as self-avoiding paths made of horizontal and vertical unit segments, that connect one corner of the central square to some point on the border, also avoiding the 3 other paths obtained by rotation by +-90 and 180 degrees around the center. To avoid counting solutions that are equivalent modulo reflection, it is enough to take the first segment in a fixed direction (e.g., from the upper left corner, always first go up by one unit). - M. F. Hasler, Jun 14 2025

Examples

			For n = 1, we have the 3 X 3 board, with the central square removed.
  In order to split this into four congruent parts, we must use four 2 X 1 tiles.
  Up to reflections, the only solution is :
                                   _____
   A A B    or, in a different    |___| |
   D   B       representation:    | |_|_|
   D C C                          |_|___|
More generally, without loss of generality (i.e., up to reflections), any solution restricted to this 3 X 3 area squares will always be of that form; the entire set of (equivalent) solutions can be obtained by "growing" the four areas (symmetrically) to fill the entire board.
Thus, for n = 2, the 7 solutions for the 5 X 5 board are obtained by filling the outer ring with 4 groups of 2n = 4 adjacent identical letters so that they are in contact with a same letter in the "central ring":
   B B B B C   A B B B B   A A B B B   A A A B B   A A A A B   D A A A A   D D A A A
   A A A B C   A A A B C   A A A B B   A A A B B   D A A B B   D A A B B   D A A B A
   A D   B C   A D   B C   A D   B C   D D   B B   D D   B B   D D   B B   D D   B B
   A D C C C   A D C C C   D D C C C   D D C C C   D D C C B   D D C C B   C D C C B
   A D D D D   D D D D C   D D D C C   D D C C C   D C C C C   C C C C B   C C C B B
(Observe how the groups of four identical letters "travel clockwise" in the outer ring, while the inner ring remains the same. Given that we have 2(n-1) = 2 'A's in the previously outer ring (which always include one in the corner), and we have 2n = 4 'A's to (dis)place in the outer ring, there are 2n+1+2(n-1) = 4n-1 = 7 possibilities here.)
For n = 3, each of the previous 7 solutions gives rise to 4n-1 = 11 distinct solutions for the 7 X 7 board, by again filling the outer ring with 2n = 6 adjacent identical letters A, B, C and D so that at least one is in contact with one of the 2n-2 = 4 identical letters in the second ring. But this doesn't give all of the 104 solutions for the 7 X 7 board. We can get additional solutions by incrementing/decrementing (A > B > C > D > A) squares in the n=2 ring which couldn't be changed before (because it would have created "disconnected components" which are now connected through the outer ring). For example, "incrementing" the letters in the corners of the 3rd solution for n=2 gives the solution (3,78) depicted below, plus 3 other solutions by rotating the outer ring clockwise.  Similarly, we can increment or also decrement the letter in the corner and/or the next one in the 4th solution for n=2, and, e.g., the fourth letter of the 5th n=2 solution, see solution (3,104) below:
             B B B B C C C              D D D A A A A
  solution   B B A B B C C    solution  D D A A B A A
   (3,78):   B A A A B B C    (3,104):  D A A A B B A
  (from      A A D   B C C    (from     D D D   B B B
  solution   A D D C C C D    solution  C D D C C C B
   (2,3))    A A D D C D D     (2,6)    C C D C C B B
             A A A D D D D              C C C C B B B
		

Crossrefs

Cf. A006067, A064941, A257952.

Programs

Mathematica

A006067 = Import["https://oeis.org/A006067/b006067.txt", "Table"][[All, 2]];
a[n_] := A006067[[2n+1]];
a /@ Range[1, 13] (* Jean-François Alcover, Sep 14 2019 *)

Python

# program is unoptimized, slow for n > 5, rather for illustration
def A272070(n, sol=None): # return solution (path) with index sol if given
    if not hasattr(A:=A272070,'sol'): A.sol=[[[]]]
    while n >= len(A.sol):
        L = len(A.sol); width = 2*L+1; A.sol.append(N := [])
        path = [pos := 1+1j]; todo = [pos+2]; steps = 1,1j,-1j,-1
        used = lambda pos: any(pos*s in path for s in steps)
        while todo:
            if pos := todo.pop():
                if width in (abs(pos.real),abs(pos.imag)):
                    N . append(tuple(path+[pos]))
                elif go := [p for s in steps if not used(p := pos+2*s)]:
                    path += [pos]; todo += [0]; todo += go
            else: path.pop()
    return len(A.sol[n]) if sol is None else A.sol[n][sol]
from matplotlib.pyplot import plot,show # only needed for plotting
def A272070_plot(n, sol): # to plot the solution w/ index sol
    for s in (1, 2*n+1): # outer frame and central square
        plot(*([(s:=-s)if(i-j)&1 else s for i in range(5)]for j in range(2)))
    for i in range(4):
        path = [1j*p for p in path] if i else A272070(n,sol)
        plot([p.real for p in path], [p.imag for p in path])
    show(); return path # M. F. Hasler, Jun 14 2025

Formula

a(n) = A006067(2*n+1).

Extensions

a(0) = 1 prepended by M. F. Hasler, Jun 13 2025