Enumeration and Listing of N-Square Pieces

The square-pieces of up to six squares were first listed in the variant chess magazine Fairy Chess Review (Volume 3, Issue 5, April 1937 pages 46-7) in "A Notation for Dissection Problems" by T. R. Dawson and W. E. Lester. They wrote: "It may be noted that the numbering and orientation has been done on systematic lines as follows. The pieces are ranged in increasing size. Where they are of the same size the number of files increases from left to right, while squares on second and later files move successively lower." These rules however are not sufficient to fix the list exactly (both in the sequence and orientation of the pieces), and I am not clear if additional unstated rules were in operation or whether an arbitrary element was involved. For details of the FCR numbering scheme see: Key to FCR Notation

However, a fully systematic listing is indeed possible. This can be done by interpreting each n-square piece as a binary number. To do this we imagine an array of 0s in rows of n. Then we represent the n-square shape as an array of 1s, replacing some of these 0s, and arranged to give the smallest possible binary number when read from the top left row by row. This principally means that the first 1 should be as low as possible and as far to the right as possible (so that the first power of 2 in the sum of binary terms is as low as possible).

For instance the first asymmetric omino, the L-shaped 4-square piece, can occur in eight different orientations, and these can be interpreted as binary numbers as shown here where the eight orientations are arranged in increasing sequence of the number represented. The numbers below the binary arrays show the decimal equivalents of the binary numbers.

0000	0000	0000	0000	0001	0010	0011	0011
0001	0100	0111	0111	0001	0010	0001	0010
0111	0111	0001	0100	0011	0011	0001	0010
= 23	= 71	= 113	= 116	= 275	= 547	= 785	= 802

For each value of n, the numbers defined by this method are in order of magnitude, and no two can be equal, so they provide an exact sequencing and orientation of the ominoes.

By this binary number method the pieces from 1 to 5 squares are represented as:

I choose to letter (or number) the sets and number the ominoes within each set, whereas in FCR the whole sequence was numbered 1 to 21. This sequence agrees with that given by Dawson and Lester except for transposition of the [5]-pieces 5 (15) and 6 (14). The relative orientations also agree except in the cases of the [4]-piece 5 (9), and the [5]-pieces 5 (15), 8 (17), 10 (19) and 11 (20).

The 6-square pieces were first enumerated by H. D. Benjamin in Problemist Fairy Chess Supplement, December 1934. Here is the listing of the 35 pieces by the binary number method:

I number this set 1 to 35. (Dawson and Lester used 22 to 56 but their sequence departs considerably from the binary number method.)

The 108 pieces of 7 squares were first counted by F. Douglas and W. E. Lester in FCR April 1937. A listing of the pieces was made by Frans Hansson in 1938, following a similar scheme to that used in FCR for the pieces 1 to 6, however no 7-square piece dissections were published in FCR, so the numbering was not used. Here is my listing by the binary number method:

The first correct counts of the 8 and 9 square pieces were done by Dr J. Niemann (FCR June 1938), his count of the 10s however (FCR December 1939) was one short and the correct figure was nor found until 1966 by T. R. Parkin (reported in the UK edition of Golomb's book, Polyominoes). Niemann's method of counting the pieces was to group them according to the dimensions of the smallest rectangle from which they can be cut.

This table shows the numbers of square-pieces of all sizes up to 10 classified by outline rectangle.

n	1	2	3	4	5	6	7	8	9	10
1×n	1	1	1	1	1	1	1	1	1	1
2×2			1	1
2×3				3	2	1
2×4					3	6	2	1
2×5						5	11	10	3	1
2×6							5	19	22	15
2×7								7	28	52
2×8									7	40
2×9										9
3×3					6	7	7	3	1
3×4						15	39	59	42	21
3×5							25	96	210	255
3×6								35	188	550
3×7									49	332
3×8										63
4×4							18	77	181	266
4×5								61	383	1304
4×6									97	822
4×7										155
5×5									73	529
5×6										240
Total	1	1	2	5	12	35	108	369	1285	4655

The count of the 4×4 ten-pieces is a particularly difficult and interesting enumeration. For Chessics #28 I checked the count by dividing the 4×4 into its 2×2 quarters and classifying the pieces by the ways in which the 6 squares that are cut away are distributed among the quarters. There are 13 cases, as shown in the chart below, with the number of pieces of each type and the number of symmetric pieces of each type, given below each case-diagram.

4 2 0 0	4 0 0 2	4 1 0 1	4 1 1 0	3 3 0 0	3 0 0 3	3 2 0 1	3 2 1 0	3 1 0 2	3 1 1 1	2 2 2 0	2 2 1 1	2 1 1 2	totals
2	1	14	10	0	2	16	17	26	63	11	65	39	266
0	0	0	4	0	1	0	0	0	5	1	6	5	22

In enumerating these care must be taken to exclude cases where the ten squares do not form a connected whole and, where symmetry is possible, not to count the asymmetric cases twice.

For the record, the numbers of square-pieces of all sizes up to 24 were calculated, with a little computer help, by H. Redelmeier in 1981 (Discrete Mathematics, volume 36, pp191-203).