6.1 The Basics Of Counting Flashcards
THE PRODUCT RULE
Suppose that a procedure can be broken down into a sequence of
two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first
task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.
An extended version of the product rule:
Suppose that a procedure is carried
out by performing the tasks T1, T2, … , Tm in sequence. If each task Ti
, i = 1, 2, … , n, can be
done in ni ways, regardless of how the previous tasks were done, then there are n1 ⋅ n2 ⋅⋯⋅ nm
ways to carry out the procedure. This version of the product rule can be proved by mathematical
induction from the product rule for two tasks
THE SUM RULE
If a task can be done either in one of n1 ways or in one of n2 ways, where
none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 + n2
ways to do the task.
The product rule is often phrased in terms of sets in this way:
If A1, A2, … , Am are finite
sets, then the number of elements in the Cartesian product of these sets is the product of the
number of elements in each set. To relate this to the product rule, note that the task of choosing an element in the Cartesian product A1 × A2 × ⋯ × Am is done by choosing an element
in A1, an element in A2, … , and an element in Am. By the product rule it follows that
|A1 × A2 × ⋯ × Am| = |A1| ⋅ |A2| ⋅⋯⋅ |Am|.
We can extend the sum rule to more than two tasks. ?
Suppose that a task can be done in one
of n1 ways, in one of n2 ways, … , or in one of nm ways, where none of the set of ni ways of
doing the task is the same as any of the set of nj ways, for all pairs i and j with 1 ≤ i < j ≤ m.
Then the number of ways to do the task is n1 + n2 + ⋯ + nm.
The sum rule can be phrased in terms of sets as:
If A1, A2, … , Am are pairwise disjoint
finite sets, then the number of elements in the union of these sets is the sum of the numbers of
elements in the sets. To relate this to our statement of the sum rule, note there are |Ai
| ways to
choose an element from Ai for i = 1, 2, … , m. Because the sets are pairwise disjoint, when we
select an element from one of the sets Ai
, we do not also select an element from a different set
Aj
. Consequently, by the sum rule, because we cannot select an element from two of these sets
at the same time, the number of ways to choose an element from one of the sets, which is the
number of elements in the union, is
|A1 ∪ A2 ∪ ⋯ ∪ Am| = |A1| + |A2| + ⋯ + |Am| when Ai ∩ Aj = for all i, j.
This equality applies only when the sets in question are pairwise disjoint.
The Subtraction Rule (Inclusion–Exclusion for Two Sets)
If a task can be done in either n1 ways or n2 ways, then the
number of ways to do the task is n1 + n2 minus the number of ways to do the task that are
common to the two different ways.
The subtraction rule is also known as the principle of inclusion–exclusion, especially when
it is used to count the number of elements in the union of two sets.
Because there are |A1 ∪ A2| ways to select an element
in either A1 or in A2, and |A1 ∩ A2| ways to select an element common to both sets, we have
|A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.
The subtraction rule, or the principle of inclusion–exclusion, can be generalized to find the
number of ways to do one of n different tasks or, equivalently, to find the number of elements
in the union of n sets, whenever n is a positive integer
THE DIVISION RULE
Application:
There are n∕d ways to do a task if it can be done using a procedure
that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to
way w.
Remark: The division rule comes in handy when it appears that a task can be done in n different
ways, but it turns out that for each way of doing the task, there are d equivalent ways of doing it. Under these circumstances, we can conclude that there are n∕d inequivalent ways of doing
the task.
restate the division rule in terms of sets:
“If the finite set A is the union of n pairwise
disjoint subsets each with d elements, then n = |A|∕d.”
formulate the division rule in terms of functions:
“If f is a function from A
to B where A and B are finite sets, and that for every value y ∈ B there are exactly d values
x ∈ A such that f(x) = y (in which case, we say that f is d-to-one), then |B| = |A|∕d.”
Tree Diagrams:
A tree consists of a root, a number
of branches leaving the root, and possible additional branches leaving the endpoints of other
branches.
To use trees in counting, we use a branch
to represent each possible choice. We represent the possible outcomes by the leaves, which are
the endpoints of branches not having other branches starting at them.
