n1234 5 6 7 8 9 10 11 12
P(n) 1 1 2 5 12 35 108 369 1,285 4,655 17,073 63,600
406 population
Polyominoes
Pn
n()
square’s edge. A polyomino composed of nsquares is
called an n-polyomino or simply an n-omino.
Two polyominoes are considered equivalent if one
can be picked up, rotated, and possibly flipped, to
match the other. Using this notion of equivalence, there
is then just one 1-omino (called a “monomino”), one
2-omino (the domino), two 3-ominoes (each called a
tromino), and five 4-ominoes (each called a tetromino).
Let P(n) denote the number of distinct n-ominoes.
The following table gives the value of P(n) for nfrom 1
to 12.
The exact values for P(n) up to n= 24 are known, but
finding a general formula for P(n) remains an open
problem. In 1966 mathematician David Klarner
proved that there is a number K(today called Klarner’s
constant) such that limn→∞ = K. (This shows that
P(n) has approximate value Knif nis large, and so the
function grows exponentially.) The exact value of Kis
not known, but mathematicians have established that
it lies between 3.9 and 4.649551. (They suspect its
value lies close to 4.2.)
The order of a polyomino is the smallest number
of identical copies of that polyomino that can be
assembled to form a rectangle. If the creation of a rect-
angle is impossible, then that polyomino is said to
have infinite order. The straight tromino has order one
(it is itself a rectangle) and the bent tromino has order
two. (Two copies of this tromino can interlock to pro-
duce a 2×3 rectangle.) The four tetrominoes illustrated
above have orders 1, 2, 4, 1, and ∞, respectively. (To
see that the final tetromino cannot tile any rectangle,
consider the placement of the tetromino in the top left
corner of the rectangle. Its orientation forces the place-
ment of the tetrominoes below it or to the right of it.)
There are no polyominoes of order three. Counting the
number of different ways to tile a 2 × nrectangle with
dominoes yields the F
IBONACCI NUMBERS
.
Generalizations of polyominoes to shapes com-
posed of fundamental units other than squares (such
as equilateral triangles and regular hexagons) are
called polyforms.
See also
TESSELLATION
.
population See
POPULATION AND SAMPLE
.
population and sample
STATISTICS
is the science of
collecting, tabulating, and summarizing
DATA
obtained
from particular systems of study, and making infer-
ences or predictions based on that data. The word pop-
ulation is used for the group of all the individuals (or
objects or events) that are the subject of the study. A
sample is a representative subgroup or subset of the
population. For example, in a medical study on the
growth rates of 8-year-old children in the United States,
the population would be all 8-year-old American chil-
dren. As it is not feasible to examine every child of a
particular age, a sample of just 1,000 children might be
used for the study.
A sample in which every individual in the popula-
tion has equal chance of being chosen for the sample is
called a random sample. If, in a sample, some portion
of the population is represented more heavily than it
actually occurs, then the sample is called biased. Biased
sampling is to be avoided.
A famous historical example of an erroneous pre-
diction based on biased sampling occurred during the
1936 U.S. presidential elections. The popular publica-
tion Literary Digest, as part of the sensationalism lead-
ing up to the election, conducted a poll to predict the
outcome of the race. After interviewing a sample of eli-
gible voters, chosen by drawing names at random from
telephone books from across the nation, the editors of
the publication concluded that the election was a fore-
gone conclusion—Alfred Landon was to win with a
comfortable lead—and they subsequently published