324
Sets, Combinatorics, and Probability
3. The principle of inclusion and exclusion applies to
the union of any number of sets as long as at least
one of them is finite.
4. The pigeonhole principle is a way to count the
number of elements in the union of disjoint sets, or
“pigeonholes.”
5. The piegeonhole principle guarantees that if there
are 8 people in a room, at least 2 must have been
born on the same day of the week.
Section 4.4
1. A permutation is an ordered arrangement of
objects.
2. The number of combinations of r objects out of n,
r > 1, is fewer than the number of permutations of
r objects out of n.
3. To find the number of ways a subset of r objects can
be selected from n objects, use the formula P(n, r).
4. The number of permutations of the letters in a word
with three sets of re peated letters is n!/3.
5. The formula C(r + n − 1, r) computes the number
of combinations of r ob jects out of n objects where
objects may be used repeatedly.
Section 4.5
1. Pascal’s triangle consists of rows that represent the
number of ways to arrange r out of n objects for
various r.
2. Pascal’s formula says that an “interior” number
in Pascal’s triangle is the sum of the two numbers
directly above it in the triangle.
3. In the expansion of a binomial to the nth power, the
kth term is found in row k of Pascal’s triangle.
4. A combinatorial argument is one that is based on
counting techniques.
5. The coefficient of the seventh term in the expansion
of (a + b)
12
is given by the expression C(12, 6).
Section 4.6
1. The probability of an event always falls in the range
between 0 and 1.
2. In a sample space with n equally likely outcomes,
the probability distribution is 1/n for each
outcome.
3. To find the probability of several events occurring, multiply the probabilities of the individual
events.
4. A random variable is a variable whose value
is randomly assigned using a random number
generator.
5. If E 1 and E 2 are disjoint events whose union
equals the sample space, then Bayes’ theorem
allows you to derive the conditional probability
P(E 1 0 F ) if you know P(F 0 E 1 ), P(F 0 E 2 ), P(E 1 )
and P(E 2 ).
o n t H e c o m p u t e R
For Exercises 1−10, write a computer program that
produces the desired output from the given input.
1. Input: Elements in a finite set S
Output: Elements in ℘(S)
Algorithm: Use recursion.
2. Input: Arithmetic expression in postfix notation
(see Exercise 45 in Sec tion 4.1)
Output: Value of the expression
3. Input: Arithmetic expression in infix notation (see
Exercise 45 in Section 4. 1)
Output: Postfix form of the expression
Do this problem in two ways:
a. Assume that the input is fully parenthesized.
b. Do not assume that the input is fully parenthesized, but apply the proper order of precedence
of operators within the program (order of precedence of operators is parenthesized expressions
first, then exponentiation, then multiplication and
division, then addition and subtraction).
4. Input: Values for n and r, 0 ≤ r ≤ n
Output: Value of P(n, r)
5. Input: Values for n and r, 0 ≤ r ≤ n
Output: Value of C(n, r)
6. Input: Value for n
Output: All values of C(n, r), 0 ≤ r ≤ n
Sets, Combinatorics, and Probability
3. The principle of inclusion and exclusion applies to
the union of any number of sets as long as at least
one of them is finite.
4. The pigeonhole principle is a way to count the
number of elements in the union of disjoint sets, or
“pigeonholes.”
5. The piegeonhole principle guarantees that if there
are 8 people in a room, at least 2 must have been
born on the same day of the week.
Section 4.4
1. A permutation is an ordered arrangement of
objects.
2. The number of combinations of r objects out of n,
r > 1, is fewer than the number of permutations of
r objects out of n.
3. To find the number of ways a subset of r objects can
be selected from n objects, use the formula P(n, r).
4. The number of permutations of the letters in a word
with three sets of re peated letters is n!/3.
5. The formula C(r + n − 1, r) computes the number
of combinations of r ob jects out of n objects where
objects may be used repeatedly.
Section 4.5
1. Pascal’s triangle consists of rows that represent the
number of ways to arrange r out of n objects for
various r.
2. Pascal’s formula says that an “interior” number
in Pascal’s triangle is the sum of the two numbers
directly above it in the triangle.
3. In the expansion of a binomial to the nth power, the
kth term is found in row k of Pascal’s triangle.
4. A combinatorial argument is one that is based on
counting techniques.
5. The coefficient of the seventh term in the expansion
of (a + b)
12
is given by the expression C(12, 6).
Section 4.6
1. The probability of an event always falls in the range
between 0 and 1.
2. In a sample space with n equally likely outcomes,
the probability distribution is 1/n for each
outcome.
3. To find the probability of several events occurring, multiply the probabilities of the individual
events.
4. A random variable is a variable whose value
is randomly assigned using a random number
generator.
5. If E 1 and E 2 are disjoint events whose union
equals the sample space, then Bayes’ theorem
allows you to derive the conditional probability
P(E 1 0 F ) if you know P(F 0 E 1 ), P(F 0 E 2 ), P(E 1 )
and P(E 2 ).
o n t H e c o m p u t e R
For Exercises 1−10, write a computer program that
produces the desired output from the given input.
1. Input: Elements in a finite set S
Output: Elements in ℘(S)
Algorithm: Use recursion.
2. Input: Arithmetic expression in postfix notation
(see Exercise 45 in Sec tion 4.1)
Output: Value of the expression
3. Input: Arithmetic expression in infix notation (see
Exercise 45 in Section 4. 1)
Output: Postfix form of the expression
Do this problem in two ways:
a. Assume that the input is fully parenthesized.
b. Do not assume that the input is fully parenthesized, but apply the proper order of precedence
of operators within the program (order of precedence of operators is parenthesized expressions
first, then exponentiation, then multiplication and
division, then addition and subtraction).
4. Input: Values for n and r, 0 ≤ r ≤ n
Output: Value of P(n, r)
5. Input: Values for n and r, 0 ≤ r ≤ n
Output: Value of C(n, r)
6. Input: Value for n
Output: All values of C(n, r), 0 ≤ r ≤ n