Permutations and Combinations
Permutation : finding the number of ways to arrange a specified number of distinct elements of a set of a particular size, where the order of these elements matters.
Combination : finding the number of ways to select a particular number of elements from a set of a particular size, where the order of the elements selected does not matter.
A permutation of a set of distinct objects is an ordered arrangement of these objects.
If "n" is a positive integer and "r" is an integer with 1 ≤ r ≤ n, then there are P(n, r) = n(n − 1)(n − 2) ···(n − r + 1) r-permutations of a set with "n" distinct elements.
An r-combination of elements of a set is an un-ordered selection of "r" elements from the set. Thus, an r-combination is simply a subset of the set with "r" elements.
Q. In how many ways can we select three students from a group of five students to stand in line for a picture? In how many ways can we arrange all five of these students in a line for a picture?
First, note that the order in which we select the students matters. There are five ways to select the first student to stand at the start of the line. Once this student has been selected, there are four ways to select the second student in the line.
After the first and second students have been selected, there are three ways to select the third student in the line. By the product rule, there are 5 · 4 · 3 = 60 ways to select three students from a group of five students to stand in line for a picture.
To arrange all five students in a line for a picture, we select the first student in five ways, the second in four ways, the third in three ways, the fourth in two ways, and the fifth in one way. Consequently, there are 5 · 4 · 3 · 2 · 1 = 120 ways to arrange all five students in a line for a picture.
Permutation Formula :
If n and r are integers with 0 ≤ r ≤ n, then P(n, r) = n! / (n − r)!
Q. How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest?
Because it matters which person wins which prize, the number of ways to pick the three prize winners is the number of ordered selections of three elements from a set of 100 elements, that is, the number of 3-permutations of a set of 100 elements.
Consequently, the answer is
P(100, 3) = 100 · 99 · 98 = 970,200
Q. Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award these medals, if all possible outcomes of the race can occur and there are no ties?
The number of different ways to award the medals is the number of 3-permutations of a set with eight elements. Hence, there are P(8, 3) = 8 · 7 · 6 = 336 possible ways to award the medals.
Q. Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities?
The number of possible paths between the cities is the number of permutations of seven elements, because the first city is determined, but the remaining seven can be ordered arbitrarily.
Consequently, there are 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman to choose her tour. If, for instance, the saleswoman wishes to find the path between the cities with minimum distance, and she computes the total distance for each possible path, she must consider a total of 5040 paths!
Q. How many permutations of the letters ABCDEFGH contain the string ABC ?
Because the letters ABC must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block ABC and the individual letters D, E, F, G, and H.
Because these six objects can occur in any order, there are 6! = 720 permutations of the letters ABCDEFGH in which ABC occurs as a block
Combinations
The number of r-combinations of a set with n elements, where n is a nonnegative integer and r is an integer with 0 ≤ r ≤ n, equals C(n, r) = n! / r! (n − r)!
Q. How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also, how many ways are there to select 47 cards from a standard deck of 52 cards?
Because the order in which the five cards are dealt from a deck of 52 cards does not matter, there are C(52, 5) = 52! / 5!47! different hands of five cards that can be dealt.
Q. How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?
The answer is given by the number of 5-combinations of a set with 10 elements.
C(10, 5) = 10! / 5! * 5! = 252.
Q. A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many ways are there to select a crew of six people to go on this mission (assuming that all crew members have the same job)?
The number of ways to select a crew of six from the pool of 30 people is the number of 6-combinations of a set with 30 elements, because the order in which these people are chosen does not matter
C(30, 6) = 30! / 6! 24! = (30 · 29 · 28 · 27 · 26 · 25)/(6 · 5 · 4 · 3 · 2 · 1) = 593,775.
Q. How many bit strings of length n contain exactly "r" 1s?
The positions of "r" 1s in a bit string of length "n" form an r-combination of the set {1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of length "n" that contain exactly "r" 1s.
Q. Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?
By the product rule, the answer is the product of the number of 3-combinations of a set with nine elements and the number of 4-combinations of a set with 11 elements.
C(9, 3) · C(11, 4) = [9! / 3!6!] * [11! / 4!7!] = 84 · 330 = 27,720.
The Binomial Theorem
(x + y)n = nC0xny0 + nC1xn-1y1 + nC2xn-2y2 + .... + nCnx0yn
Q. What is the expansion of (x + y)4?
(x + y)4 = 4C0x4y0 + 4C1x3y1 + 4C2x2y2 + 4C3x1y3+ 4C4x0y4
(x + y)4 = x4 + 4x3y1 + 6x2y2 + 4xy3+ y4
Q. What is the coefficient of x12y13 in the expansion of (x + y)25 ?
From the binomial theorem it follows that this coefficient is
25C13 = 25! / (13! * 12!) = 5,200,300
Q. What is the coefficient of x12y13 in the expansion of (2x - 3y)25 ?
(2x - 3y)25 = (2x + (- 3)y)25
The coefficient is 25C13 * 212 * (-3)13
Q. How many strings of length "r" can be formed from the uppercase letters of the English alphabet?
By the product rule, because there are 26 uppercase English letters, and because each letter can be used repeatedly, we see that there are 26r strings of uppercase English letters of length "r".
Q. Suppose that a cookie shop has four different kinds of cookies. How many different ways can six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or the order in which they are chosen, matters.
The number of ways to choose six cookies is the number of 6-combinations of a set with four elements. From Theorem 2 this equals C(4 + 6 − 1, 6) = C(9, 6). Because
C(9, 6) = C(9, 3) = = 84,
Combinations and Permutations With and Without Repetition: Formulae
Permutations with Indistinguishable Objects
The number of different permutations of n objects, where there are n1 indistinguishable objects of type 1, n1 indistinguishable objects of type 2,...,and nk is indistinguishable objects of type k, is
FORMULA : n! / (n1! * n2! .. nk!)
Q. How many different strings can be made by reordering the letters of the word SUCCESS?
Because some of the letters of SUCCESS are the same, the answer is not given by the number of permutations of seven letters. This word contains three Ss, two Cs, one U, and one E.
The three Ss can be placed among the seven positions in C(7, 3) different ways
The two Cs can be placed in C(4, 2) ways, leaving two free positions. The U can be placed in C(2, 1) ways, leaving just one position free. Hence E can be placed in C(1, 1) way. Consequently, from the product rule, the number of different strings that can be made is
C(7, 3) * C(4, 2) * C(2, 1) * C(1, 1) = 420
Distributing Objects into Boxes
The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i, i = 1, 2,...,k, equals
FORMULA : n! / (n1! * n2! .. nk!)
Q. How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?
The first player can be dealt 5 cards in C(52, 5) ways.
The second player can be dealt 5 cards in C(47, 5) ways, because only 47 cards are left.
The third player can be dealt 5 cards in C(42, 5) ways. Finally, the fourth player can be dealt 5 cards in C(37, 5) ways. Hence, the total number of ways to deal four players 5 cards each is
= C(52, 5) * C(47, 5) * C(42, 5) * C(37, 5)