square’s edge. A polyomino composed of n squares 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 n from 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 lim n→∞
= K. (This shows that
P(n) has approximate value K
n if n is large, and so the
function grows exponentially.) The exact value of K is
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 rectangle 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 produce 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 placement 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 × n rectangle with
dominoes yields the FIBONACCI NUMBERS.
Generalizations of polyominoes to shapes composed 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 inferences or predictions based on that data. The word population 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 children. 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 population 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 prediction based on biased sampling occurred during the
1936 U.S. presidential elections. The popular publication Literary Digest, as part of the sensationalism leading up to the election, conducted a poll to predict the
outcome of the race. After interviewing a sample of eligible 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 foregone conclusion—Alfred Landon was to win with a
comfortable lead—and they subsequently published
P n
n ( )
n
1 2 3 4 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
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 n from 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 lim n→∞
= K. (This shows that
P(n) has approximate value K
n if n is large, and so the
function grows exponentially.) The exact value of K is
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 rectangle 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 produce 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 placement 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 × n rectangle with
dominoes yields the FIBONACCI NUMBERS.
Generalizations of polyominoes to shapes composed 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 inferences or predictions based on that data. The word population 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 children. 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 population 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 prediction based on biased sampling occurred during the
1936 U.S. presidential elections. The popular publication Literary Digest, as part of the sensationalism leading up to the election, conducted a poll to predict the
outcome of the race. After interviewing a sample of eligible 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 foregone conclusion—Alfred Landon was to win with a
comfortable lead—and they subsequently published
P n
n ( )
n
1 2 3 4 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