A003213 Number of ways to quarter a 2n X 2n chessboard. (Formerly M3987)

1, 1, 5, 37, 782, 44240

Offset

0,3

Comments

Warning: it now seems very likely that this is an incorrect version of A257952. - N. J. A. Sloane, Apr 17 2016

Number of ways to dissect a 2n X 2n chessboard into 4 congruent pieces.

One can ask the same question for a 2n+1 X 2n+1 board if one omits the center square: this gives A006067.

a(0)=1, since there is one way to do nothing.

Comment from Andrew Howroyd, Apr 18 2016: (Start)

This sequence is wrong because of a bug in Mr. Parkin's code, and amazingly I can pinpoint exactly what the bug is! (I can reproduce his results.)

Firstly the description of the problem and its solution in Mr. Parkin's letter is very clear -- he doesn't leave a lot of room for misinterpretation (this is hugely to his credit). He also includes a very clear description of his algorithm, so I decided I would just code it up. I obtained Giovanni Resta's results as given in A257952 -- there is nothing wrong with Mr Parkin's algorithm.

A detailed breakdown of Parkin's results is also provided in the letter. All the results match with the exception of the final line. (This would be highly improbable if there was a completely different interpretation.) In any case, one sentence stood out as a possible red flag: "Further, there are potential mirror image paths in both cases when starting on the centre lines and these are prevented by requiring a turn in one direction on the path prior to allowing a turn in the other direction" (bottom of page 6). The discrepancy in results does indeed relate to the center line and if I modify my code to lose the flag on recursion, then I get Mr. Parkin's results (so turn in one direction is only prohibited for one step). (End)

References

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

Popular Computing (Calabasas, CA), Vol. 1 (No. 7, 1973), Problem 15, front cover and page 2.

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

Links

Table of n, a(n) for n=0..5.

T. R. Parkin, Letter to N. J. A. Sloane, Feb 01, 1974. This letter contained as an attachment the following 11-page letter to Fred Gruenberger.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 1.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 2.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 3.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 4.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 5.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 6.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 7.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 8.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 9.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 10.

T. R. Parkin, Letter to Fred Gruenberger, Jan 29, 1974, Page 11.

T. R. Parkin, Discussion of Problem 15, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-4.

T. R. Parkin, Discussion of Problem 15, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-5.

T. R. Parkin, Discussion of Problem 15, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-6.

T. R. Parkin, Discussion of Problem 15, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-7.

T. R. Parkin, Discussion of Problem 15, Popular Computing (Calabasas, CA), Vol. 2, Number 15 (June 1974), page PC15-8.

Popular Computing (Calabasas, CA), Illustration showing that a(3) = 37, Vol. 1 (No. 7, 1973), front cover. (One of the 37 is simply the square divided into four quadrants.)

Crossrefs

Bisection of A006067. Cf. A064941.

See A257952 for another version.

Sequence in context: A180275 A257952 A240186 * A166851 A090439 A089795

Adjacent sequences: A003210 A003211 A003212 * A003214 A003215 A003216

Keyword

nonn,more

Author

N. J. A. Sloane

Status

approved