• Arts
• Business
• Computers
• Games
• Health
• Home
• Kids and Teens
• News
• Recreation
• Reference
• Regional
• Science
• Shopping
• Society
• Sports

Polyomino Enumeration

A popular computer game called "Tetris" involves manipulations of various clusters of four squares. The seven distinct types of clusters are illustrated below Clusters of connected squares like this were named "polyominoes" by Solomon Golomb. In particular, if four squares are joined together the result is called a tetromino. The game of Tetris uses all seven possible tetrominoes. Of course, there are only five distinct tetrominoes if you don't count reflections as being different. A pentomino consists of a cluster five squares, and with a little work you can verify that there are 12 distinct pentominoes, not counting rotations and reflections. Similarly, there are 35 distinct hexominoes, 107 distinct septominoes, and so on. We can work out the number of n-ominoes for fairly small values of n, but there is no known formula for the number of n-ominoes in general. For each n there are actually several numbers relating to the enumeration of n-ominoes The table below gives the values of the following functions for n = 1 to 12. e(n) = number of minimal rectangular envelopes (up to rotation) that enclose n contiguous squares. g(n) = number of n-ominoes, not counting rotations or reflections. h(n) = number of n-ominoes, not counting rotations. t(n) = total number of distinct n-ominoes. s(n) = number of n-ominoes that are invariant (up to rotation) under reflection. a(n) = number of elements of h(n) that contribute 1 element to t(n). b(n) = number of elements of h(n) that contribute 2 elements to t(n). c(n) = number of elements of h(n) that contribute 4 elements to t(n). Here's the table: n e(n) g(n) h(n) t(n) s(n) a(n) b(n) c(n) 1 1 1 1 1 1 1 0 0 2 1 1 1 2 1 0 1 0 3 2 2 2 6 2 0 1 1 4 3 5 7 19 3 1 3 3 5 4 12 18 63 6 1 3 14 6 6 35 60 216 10 0 12 48 7 8 108 196 760 20 0 12 184 8 11 369 704 2725 34 3 41 660 9 14 1285 2500 9910 70 2 42 2456 10 17 4655 9189 36446 121 0 155 9034 11 21 17073 33896 135268 250 0 158 33738 12 26 63600 126759 505861 441 9 574 126176 The values of s(n) seem closely rela

Contact Information