COUNTING
Techniques for counting are important in mathematics and in computer science, specially in the analysis of algorithms.
PERMUTATIONS
- is an arrangement of all or part of a set of objects wherein the composition of the group and the order of the items within the group are both considered.
Theorem 1 : Supposed that two tasks T1 and T2 are to be performed in sequence. If T1 can be performed in n1 ways, and for each of these ways T2 can be performed in n2 ways, then the sequence T1 T2 can be performed in n1n2 ways.
Theorem 1 is called the multiplication principle of counting.
Theorem 2 : Supposed that tasks T1, T2, . . . Tk are to be performed in sequence. If T1 can be performed in n1 ways, and for each of these T2 can be performed in n2 ways, and for each of these n1n2 ways of performing T1 T2 in sequence, T3 can be performed in n3 ways, and so on, then the sequence T1, T2, . . . Tk , can be performed in exactly n1 n2 , . . . , nk ways.
Possible ways of performing Task 1 Possible ways of performing Task 1
Possible ways of performing Task 1, then Task 2 in sequence
Ex. 1. Label plates for cars are consists of three beginning letters followed by three digits. How many distinct label plates are possible if ( a ) repetitions are allowed and ( b ) repetitions is not allowed?
2. Label plates for motorcycles are consists of four beginning digits followed by two letters. How many distinct label plates are possible if ( a ) repetitions are allowed and ( b ) repetitions is not allowed?
3. Label identifier for computer system, consists of one letter followed by three digits. How many distinct label identifiers are possible if ( a ) repetitions are allowed and ( b) repetitions is not allowed?
Problem 1. How many distinct sequences, each of length r , can be formed using elements from a set A if a) elements in the sequence can be repeated, (b) all elements in the sequence must be distinct?
· · · |
“Position 1” “Position 2” “Position 3” “Position r – 1” “Position r ”
Let T1 be the task to fill “position 1”, T2 be the task to fill “position 2” and so on. Then the combined task T1 T2 T3 . . . Tr represents the formation of the sequence. As a solution to problem 1 letter ( a ) T1 can be accomplished in n ways, since we can copy any element of A for “position 1”. The same is true for each of task T2 , T3 . . . Tr . Then by the extended multiplication principle, the number of sequences that can be formed is
n . n . . . n = n r
Theorem 3 : Let A be a set with n elements and 1 <= r <= n . Then the number of sequences of length r can be formed from elements of A, allowing repetitions, is n r.
Ex. 1. How many 3-letter words can be formed from the letters in the set { a , b , y , z } if
repetition of letters is allowed.
n = 4 , r = 3 , hence by Theorem 3, the number of words are 43 = 64.
As a solution to problem 1 letter ( b ) T1 can be performed in n ways, since any element of set A can be chosen for the first position. Whichever element is chosen , only ( n – 1 ) elements remain, so that T2 can be performed in (n – 1 ) ways, and so on until Tr can be performed in n – ( r – 1 ) or ( n – r + 1 ) ways. Thus by the extended principle of multiplication, a sequence of r distinct elements of set A can be formed in n ( n – 1 ) ( n – 2 ) . . . ( n – r + 1 ) ways.
A sequence of r distinct elements of A is often called a permutation of A taken r at a time, nPr. . nPr is called the number of permutations of n objects taken r at a time.
Theorem 4. If 1 <= r <= n then nPr , the number of permutations of n objects taken r at a time, is
n . ( n – 1 ) . ( n – 2 ) . . . ( n – r + 1 ).
When r = n , the distinct arrangements of the elements of set A is counted with | A | = n, into sequences of length n called a permutation of A.
The number of permutations of A is nPn or n . ( n – 1 ) . ( n – 2 ) . . . 2 . 1, if n >= 1. This number is also written as n! , read as n factorial. 0! is 1.
nPn = n! and nPr = n! .
( n – r )!
Examples :
1. How many permutations can be formed from the elements of A = { a, b, c, d }
2. How many permutations can be formed from a deck of cards ?
3. How many “words” of three distinct letters can be formed from the letters of STOMACH?
Theorem 5 : The number of distinguishable permutations that can be formed from a collection of objects
where the first object appears k1 times, the second object k2 times, and so on is
Example :
1. Determine the number of distinguishable “words” that can be formed from the letters of
MASSACHUSETTS, ZAMBOANGA, ALAMADA, PULUPANDAN and TAWITAWI.
2. A bank password consists of two letters of the English alphabet followed by two digits. How many
different passwords are there ?
3. A coin is tossed four times and the result of each toss is recorded. How many different sequences of heads and tails are possible ?
4. Compute each of the following : 4P4 , 6 P5 , 7 P 2 , n Pn – 1 , n Pn – 2 , n + 1 Pn – 1 , n – 2 Pn – 3
5. In how many ways can six men and six women be seated in a row if
a) any person may sit next to any other, b) men and women must occupy alternate seats?
6. A fair six-sided is tossed four times and the numbers shown are recorded in a sequence. How many
different sequences are there ?
7. Compute the number of permutations of the given set :
a) { w, x, y, z } c) { 4, 7, 10, 13, 17 }
b) { a, b, 1, 2, 3, c } d) { 2, 4, 6, 8, 8, 10 }
8. Find the number of permutations of A taken r at a time :
a) A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } and r = 6
b) A = { x | x is an integer and x2 < 83 } and r = 3
c) A = { x | x is an even integer and 7 < x < 33 } and r = 4
COMBINATIONS
The multiplication principle and counting methods for permutations all apply to situations where order matters. The traditional name for an r-element subset of an n-element set A is a combination of A, taken r at a time.
A combination of r objects taken from a set S of n objects is a subset of S whose composition does not take into account ordering or arrangement of the elements.
Example 1. Let A = { w, x, y, z }. The following are all distinct combinations of A, taken 3 at a time.
A1 = { w, x, y } , A2 = { w, x, z } , A3 = { w, y, z } , A4 = { x, y, z }. Note that these are
subsets, not sequences. Thus, A1 = { x, w, y } = x, y, w } = { w, y, x } = { y, w, x } = { y, x, w }.
In other words, combinations, unlike permutations, the order of the elements is irrelevant.
Problem 2. Let A be any set with n elements and 1 £ r £ n . How many different subsets of A are there, each with r elements ?
We want to count the number of r – element subsets of an n –element set A.
Task 1 : Choose a subset B of A containing r elements.
Task 2 : Choose a particular permutation of B.
We are trying to compute the number of ways to choose B, call this number C. Then task 1 can be done in C ways and task 2 can be done in r! ways. By multiplication principle; C . r! which is also nPr.
C . r ! = nPr. = n! , .
( n – r ) !
therefore C = n !
r ! ( n – r ) !
Theorem 1 : Let A be a set with | A | = n, and let 1 <= r <= n . Then the number of combinations of the elements of A, taken r at a time, that is the number of r-element subsets of A is
n ! .
r ! ( n – r ) !
The number of Combinations of n objects taken r at a time is given by
nC r. = n ! .
r ! ( n – r ) !
Example. 1. Determine the number of distinct five-card hands that can be dealt from a deck of cards.
5 C52. = 52 ! = 52 ! = 2,598,960.
5 ! ( 52 – 5 ) ! 5! 47!
2. Compute ( a ) 7 C 7 ( b ) 9 C 5 ( c ) 15 C 9. ( d ) 8 C 4.
Theorem 2 : Suppose k selections are to be made from n items without regard to order and that repeats are allowed, assuming at least k copies of each of the n items. The number of ways these selections can be made is
( n + k – 1 ) C k
Ex. 3 In how many ways can a prize winner choose three CDs from the Top Ten list if repeats are
allowed ?
Solution. n is 10 and k = 3, by theorem 2 there are ( 10 + 3 – 1 ) C 3 or 12 C 3 ways to make the selections. The prize winner can make the selection in 220 ways
In general, when order matters, we count the number of sequences or permutations; when order does not matter, we count the number of subsets or combinations.
Example 4.
A valid password consists of ten characters, the first of which is a letter chosen from the set
{ Q, R, S, T, U, V, W, X, Y, Z } and the remaining nine characters are letters chosen from the English alphabet or a digit. How many different passwords are possible ?
Solution : A password can be constructed by performing the tasks T1 and T2 in sequence.
T1 : Choosing a starting letter from the set given 10 C 1 = 10
T2 : Choosing a sequence of letter and digits. Repeats are allowed. ( 26 + 10 ) 9 = 101,559,956,668,416
By multiplication principle, there are = 10 . 101,559,956,668,416 = 1,015,599,566,684,160
Example 5. How many different eight-person committee can be formed each containing three women
from an available 15 women and five men from an available set of 20 men ?
T1 : Choose 3 women from the set of 15 women. 15 C 3 = 455
T2 : Choose 5 men from the set of 20 men. 2 0 C 5 = 15 504
By multiplication principle, there are ( 455 )( 15,504 ) = 7 054 320 different committees.
6. Compute each of the following a) n C n – 1 b) n – 1 C n – 2 c) n + 1 C n – 1
7. Show that a) n C r = n C n – r b) n + 1 C r = n C r – 1 + n C r
8. In how many ways can a committee of three faculty members and two students be selected from seven faculty members and eight students ?
9. An urn contains 15 balls, of which eight are red and seven are black. In how many ways can five balls be chosen so that a) two are red and three are black and b) three are red and two are black.
10. Five fair coins are tossed and the results are recorded. ( a ) How many different sequences of heads and tails are possible ? (b ) How many of the sequences in part (a ) have exactly one head recorded? (c ) How many of the sequences in part ( a ) have exactly three heads recorded ?
11. How many ways can you choose three of seven fiction books and two of six non-fiction books to take with you on your vacation ?
12. A gift certificate at a local bookstore allows the recipient to choose six books from the combined list of ten best-selling fiction books and ten best-selling non-fiction books. In how many different ways can the selection of six books be made ?
13. An urn contains 15 balls, of which eight are red and seven are black. In how many ways can 5 balls be chosen so that at least two are red ?
what is the solution for question no. 12?
ReplyDelete