People may think that counting is easy, and certainly sometimes it is. But some of the aspects of counting are not simple, especially counting a large number of elements. In this case, we need to use some mathematical skills to find out the answer.
Consider counting the number of elements in a list, where each element has an index beginning with some integer m and ending with some integer n, and m < n. Then there are n - m + 1 elements in the list, from m to n inclusive. For example, if the first index is 0, and the last indexed element is 99, then you have 99 - 0 + 1 = 100 elements. This method also works for counting a certain number of elements from only part of the list (for example, the number of elements between index nos. 12 and 43.)
There are two basic counting principles:
| Sum Rule | Suppose that an operation can be performed by either of two different procedures, with m possible outcomes for the first procedure and n possible outcomes for the second. If the two sets of possible outcomes are disjoint, then the number of possible outcomes for the operation is m + n. |
| Product Rule |
Suppose that an operation consists of k steps and:
the first step can be performed in n1 ways; the second step can be performed in n2 ways (ignoring how the first step was performed), . . .; and the kth step can be performed in nk ways. Then the whole operation can be performed in n1 * n2 * ........... * nk ways. |
Consider the following examples:
| Example 1: | A scholarship is available, and the student to receive this scholarship must be chosen from the Mathematics, Computer Science, or the Engineering Department. How many different choices are there for this student if there are 38 qualified students from the Mathematics Department, 45 qualified students from the Computer Science Department and 27 qualified students from the Engineering Department? |
| Solution: | The procedure of choosing a student from the Mathematics Department has 38 possible outcomes, the procedure of choosing a student from the Computer Science Department has 45 possible outcomes, and the procedure of choosing a student from the Engineering Department has 27 possible outcomes. Therefore, there are (38 + 45 + 27 ) 110 possible choices for the student to receive the scholarship. |
| Example 2: | A man has 10 shirts, 8 pairs of pants and three pairs of shoes. How many different outfits, consisting of one shirt, one pair of pants and one pair of shoes, are possible? |
| Solution: | We have to consider three steps: choose a shirt; choose a pair of pants; and choose a pair of shoes. Choosing a shirt has 10 possible outcomes (as he has ten shirts!), choosing a pair of pants has 8 possible outcomes, and choosing a pair of shoes has 3 possible outcomes. So the number of different outfits is 10 * 8 * 3 = 240. |
Question : How many different outfits, consisting of one shirt, one pair of pants, one pair of shoes and one hat, are possible if he has bought two hats? Click here for answer.
D E F I N I T I O N S
| Permutation | Given n different elements in a set, any ordered arrangement of these elements is called a permutation. |
| r-permutation | An r-permutation of a set of n elements is an ordered selection of r elements taken from the set of n elements. It is denoted by P(n, r). |
Permutations are arrangements of the objects within a set. For example, the set of elements a, b and c has six permutations.
abc, bac, bca, acb, cab, cba
Imagine that we have a set of n elements, how can we find the number permutations of the set?
Try to view creating a permutation as an n-step operation:
1st step: choose the first element. If there are n elements, then there are n possible choices for the first element.
2nd step: choose the second element. Since one element has already been chosen and placed, there are n-1 possible choices remaining.
3rd step: choose the third element. Since two elements have already been chosen and placed, there are n-2 possible choices remaining.
. . . . .
nth step: choose the nth element. Since n-1 elements have already been chosen and placed for the preceding steps, there is only one choice left in the set.
Hence by the product rule, there are n * (n - 1) * (n - 2) * ...... * 2 * 1 ways to perform the entire operation. In other words, there are n! permutations of a set of n elements.
Now, consider the following example:
Given a set of 3 elements a, b, and c. there are six ways to select two elements from the set and write them in order.
ab, ba, bc, cb, ca, ac
This is called a 2-permutation of the set {a, b, c}.
If we are given a set of n elements, and we have to select r elements from the set where r < n, what is the r-permutation of the set?
1st step: choose the first element. If there are n elements, then there are n possible choices for the first element.
2nd step: choose the second element. Since one element has already been chosen and placed, there are n-1 possible choices remaining.
3rd step: choose the third element. Since two elements have already been chosen and placed, there are n-2 possible choices remaining.
. . . . .
rth step: choose the rth element. This is the last step, and since there are n - r + 1 elements remaining, there are clearly n - r + 1 ways left to select an element from the set.
Therefore by the product rule, there are n * (n - 1) * (n - 2) * ....... * (n - r + 1) ways to perform the entire operation.
P(n, r) = n * (n - 1) * (n - 2) * ....... * (n - r + 1)
or equivalently,
P(n, r) =  |
Try to figure out how this equation equals n * (n - 1) * (n - 2) * ....... * (n - r + 1). Click here for explanation.
D E F I N I T I O N
| r-combinations | An r-combination from a set of n elements is a
unordered selection of r elements from the set, where n
and r are nonnegative integers with r <
n. r-combination is denoted by the symbol  ,
read "n choose r," and denotes
the number of subsets of size r (r-combinations)
that can be chosen from a set of n elements. |
In some books and calculators, the symbols C(n, r), nCr,
Cn, r, or nCr are
used instead of .
Consider the following example:
Let L = {Discrete Structures, Assembly Language, C Programming, Computer organization, File Processing}. A student can take three of the five classes in L in one quarter.
A. List all 3-combinations of L.
B. Find 
.
Answers:
| A. | {Discrete Structures, Assembly Language, C Programming} |
| {Discrete Structures, Assembly Language, Computer Organization} | |
| {Discrete Structures, Assembly Language, File Processing} | |
| {Discrete Structures, C Programming, Computer Organization} | |
| {Discrete Structures, C Programming, File Processing} | |
| {Discrete Structures, Computer Organization, File Processing} | |
| {Assembly Language, C Programming, Computer Organization} | |
| {Assembly Language, C Programming, File Processing} | |
| {Assembly Language, Computer Organization, File Processing} | |
| {C Programming, Computer Organization, File Processing} |
There are ten 3-combinations in L.
B. is
the number of 3-combinations of a set with five elements, by part A, =
10.
If we are given a set with n elements, what is the number
of r-combinations from that set? Consider obtaining an r-permutation:
one can first select r elements, which can be done in ways,
and then arrange them, which can be done in r! ways.
Hence, P(n, r) = r!,
= P(n, r)/r!
Since P(n, r) = ,
=
 |
Consider the following example:
Suppose you have a group of 10 children consisting of 4 girls and 6 boys.
A. How many four-person teams can be chosen that consist
of two girls and two boys?
B. How many four-person teams contain at least one girl?
Answers:
A. To solve this problem, we have to do two things:
First choose two girls; then choose two boys.
There are 
ways
to choose two girls out of the four and 
ways
to choose two boys out of the six. Hence by the product
rule,
Number of teams that contain two girls and two boys
= *
= 
* 
= 
* 
= 
= 90
B. The number of teams containing at least one girl =
total number of teams of four - number of teams of four that do not contain any girls.
Total number of teams of four
The total number of teams of four is 
.
The number of teams of four that do not contain any girl equals the number
of teams that contain only boys, which is 
.
Hence, the number of teams that contain at least one girl =
-
=
210 - 15 = 195.
Can you use another method to work out this question? Try it yourself
and check your answer here.
Take a chapter quiz!!
Go
to next chapter.
Go
to Class Agenda.
