252
Sets, Combinatorics, and Probability
S e c t i o n 4 . 2 Counting
Combinatorics is the branch of mathematics that deals with counting. Counting questions are important whenever we have finite resources (How much storage does a particular database consume? How many users can a given computer
configuration support?) or whenever we are interested in efficiency (How many
computations does a particular algorithm involve?).
Counting questions often boils down to finding how many members there are
in some finite set, that is, what is the cardinality of the set. This seemingly trivial
question can be difficult to answer. We have already answered some “how many”
questions—How many rows are there in a truth table with n statement letters, and
how many subsets are there in a set with n elements? (Actually, as we’ve noted,
these questions can be thought of as the same question.)
multiplication Principle
We solved the truth table question by drawing a tree of possibilities. This tree suggests a general principle that can be used to solve many counting problems. Before
we state the general principle, we look at another tree example.
example 24
A child is allowed to choose one jellybean out of two jellybeans, one red and one
black, and one gummy bear out of three gummy bears, yellow, green, and white.
How many different sets of candy can the child have?
We can solve this problem by breaking the task of choosing candy into two
sequential tasks of choosing the jellybean and then choosing the gummy bear.
The tree of Figure 4.3 shows that there are 2 × 3 = 6 possible outcomes: {R, Y},
{R, G}, {R, W}, {B, Y}, {B, G}, and {B, W}.
{R, Y} {R, G} {R, W} {B, Y} {B, G} {B, W}
Y G
W
Y G
W
R
B
Choose jellybean.
Choose gummy bear.
In this problem the sequence of events could be reversed; the child could
choose the gummy bear first and the jellybean second, resulting in the tree of
Figure 4.4, but the number of outcomes is the same (3 × 2 = 6). Thinking of a sequence of successive events helps us solve the problem, but the sequencing is not
a part of the problem since the set {R, Y} is the same as the set {Y, R}.
{Y, R}
{Y, B} {G, R} {G, B} {W, R} {W, B}
R
B
R
G
B
R
B
Y
W
Choose gummy bear.
Choose jellybean.
Both these trees are “balanced” in the sense that the second level has a fixed number of outcomes regardless of the outcome at the previous level.
figure 4.3
figure 4.4
Sets, Combinatorics, and Probability
S e c t i o n 4 . 2 Counting
Combinatorics is the branch of mathematics that deals with counting. Counting questions are important whenever we have finite resources (How much storage does a particular database consume? How many users can a given computer
configuration support?) or whenever we are interested in efficiency (How many
computations does a particular algorithm involve?).
Counting questions often boils down to finding how many members there are
in some finite set, that is, what is the cardinality of the set. This seemingly trivial
question can be difficult to answer. We have already answered some “how many”
questions—How many rows are there in a truth table with n statement letters, and
how many subsets are there in a set with n elements? (Actually, as we’ve noted,
these questions can be thought of as the same question.)
multiplication Principle
We solved the truth table question by drawing a tree of possibilities. This tree suggests a general principle that can be used to solve many counting problems. Before
we state the general principle, we look at another tree example.
example 24
A child is allowed to choose one jellybean out of two jellybeans, one red and one
black, and one gummy bear out of three gummy bears, yellow, green, and white.
How many different sets of candy can the child have?
We can solve this problem by breaking the task of choosing candy into two
sequential tasks of choosing the jellybean and then choosing the gummy bear.
The tree of Figure 4.3 shows that there are 2 × 3 = 6 possible outcomes: {R, Y},
{R, G}, {R, W}, {B, Y}, {B, G}, and {B, W}.
{R, Y} {R, G} {R, W} {B, Y} {B, G} {B, W}
Y G
W
Y G
W
R
B
Choose jellybean.
Choose gummy bear.
In this problem the sequence of events could be reversed; the child could
choose the gummy bear first and the jellybean second, resulting in the tree of
Figure 4.4, but the number of outcomes is the same (3 × 2 = 6). Thinking of a sequence of successive events helps us solve the problem, but the sequencing is not
a part of the problem since the set {R, Y} is the same as the set {Y, R}.
{Y, R}
{Y, B} {G, R} {G, B} {W, R} {W, B}
R
B
R
G
B
R
B
Y
W
Choose gummy bear.
Choose jellybean.
Both these trees are “balanced” in the sense that the second level has a fixed number of outcomes regardless of the outcome at the previous level.
figure 4.3
figure 4.4