A006067 Number of ways to quarter an n X n chessboard, with the central square removed for odd n.
1, 1, 1, 5, 7, 37, 104, 766, 3970, 43318, 431932, 7695805, 137066448, 4015896016, 128095791922, 6371333036059, 355704307903818, 30153126159555641, 2952926822418475378, 431453249608567040694, 73569487283165427567144, 18558756256964594960321428
Offset: 1
Examples
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
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
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
Comments