A006067 Number of ways to quarter an n X n chessboard, with the central square removed for odd n. (Formerly M3769)

1, 1, 1, 5, 7, 37, 104, 766, 3970, 43318, 431932, 7695805, 137066448, 4015896016, 128095791922, 6371333036059, 355704307903818, 30153126159555641, 2952926822418475378, 431453249608567040694, 73569487283165427567144, 18558756256964594960321428

Offset

1,4

Comments

To "quarter" means to dissect in 4 parts, identical up to rotation, whose interior must be connected. (I.e., the parts must be polyominoes, any 1 X 1 square of which must share a side with some other 1 X 1 square of the part, unless there's only one.) Solutions that differ only by rotation or reflection are not counted separately.

See A257952 for much more information.

See A272070 for information on odd terms.

References

M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 189.

T. R. Parkin, personal communication.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..28

Audrey Gruenberger (Editor), Checkerboard - Problem 15, Popular Computing, Vol. 1, No. 7 (1973), front cover and page 2. (Local copy of a scan of the cover illustration showing the a(6)-1 = 36 nontrivial solutions for n = 6, omitting the trivial solution using four squares.)

Formula

a(2n) = A257952(n), a(2n+1) = A272070(n). - Andrew Howroyd, Apr 19 2016

Example

For n = 1, we have the 1 X 1 board of which we remove the central square, so nothing is left, and the empty tiling is the only possible tiling.
For n = 2, we have the 2 X 2 board which can only be quartered using four 1 X 1 squares, so a(2) = 1 as well.
For n = 3, the 3 X 3 board without the central square can only be quartered using four 2 X 1 rectangles, so a(3) = 1 as well. (The two different solutions where the top rectangle is aligned to the left or to the right are counted as one, since they only differ by reflection.)
For n = 4 there is the trivial solution using squares, one using straight 4 X 1 tiles, one using T-shaped tiles, and two non-isomorphic ones using L-shaped tiles, one with a central symmetry and one with an axial symmetry:
          A A B B       A B C D       A B B B        A A B B        A A B B
  square: A A B B   I:  A B C D   T:  A A B C   Lc:  A C B D   La:  A C D B
          C C D D       A B C D       A D C C        A C B D        A C D B
          C C D D       A B C D       D D D C        C C D D        C C D D

Crossrefs

Cf. A257952, A064941, A272070.

Sequence in context: A342504 A192156 A322380 * A244260 A178428 A147760

Adjacent sequences: A006064 A006065 A006066 * A006068 A006069 A006070

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

a(8) corrected, a(9)-a(22) from Andrew Howroyd, Apr 18 2016

Name edited to clarify definition for odd n, and other edits by M. F. Hasler, Jun 13 2025

Status

approved