cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A257952 Number of ways to quarter a 2n X 2n chessboard.

Original entry on oeis.org

1, 1, 5, 37, 766, 43318, 7695805, 4015896016, 6371333036059, 30153126159555641, 431453249608567040694, 18558756256964594960321428, 2411839397220672351872242339314, 945878376319424018440202856702995909, 1121914029089423867715407724741780046405923
Offset: 0

Views

Author

Giovanni Resta, May 14 2015

Keywords

Comments

Number of ways to dissect a 2n X 2n chessboard into 4 congruent pieces. As stated by Thomas R. Parkin in his letter (see Links), the dissections belong to two classes. One in which the cuts divide the chessboard into four pieces which are 90-degree rotationally symmetric, the other in which the square is first bisected in two rectangles and then each rectangle is divided into two pieces which are 180-degree rotationally symmetric.
Two dissections are considered distinct if they belong to two different classes, even if the tile is the same. In both classes reflections and rotations are not counted, and moreover in the second class two dissections are considered the same if they differ only by the orientation of the tiles.

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.

Links

Crossrefs

Cf. A003213 (another version, but probably incorrect - N. J. A. Sloane, Apr 17 2016), A006067, A064941, A113900, A268606.

Programs

Formula

a(n) = A006067(2n) for n>0. - Jean-François Alcover, Sep 14 2019, after Andrew Howroyd in A006067.

Extensions

a(9)-a(14) from Andrew Howroyd, Apr 18 2016

A003213 Number of ways to quarter a 2n X 2n chessboard.

Original entry on oeis.org

1, 1, 5, 37, 782, 44240
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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

Crossrefs

Bisection of A006067. Cf. A064941.
See A257952 for another version.

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

Original entry on oeis.org

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

Views

Author

Andrew Howroyd, Apr 19 2016

Keywords

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

A003155 Number of ways to halve an n X n chessboard.

Original entry on oeis.org

1, 1, 1, 6, 15, 255, 1897, 92263, 1972653, 281035054, 17635484470, 7490694495750, 1405083604458437, 1789509008288411290
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

This is the number of ways to cut an n X n chessboard along grid lines into two identical pieces. In the case that n is odd the central square is first removed to ensure an even number of squares. Solutions that differ only by rotation or reflection are considered equivalent. - Andrew Howroyd, Apr 19 2016

References

  • M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 189.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A113900, A006067, A257952, A271741.

Formula

a(2n) = A113900(n). - Andrew Howroyd, Apr 19 2016

Extensions

a(10) corrected and a(11)-a(14) from Andrew Howroyd, Apr 19 2016
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.