The material on this page makes a lot of use of the factorial function. If you're not familiar with it, you might want to review first.
The basic flow of the probability pages goes like this:
In this section we'll learn how to calculate the ways of arranging n-items of a group and of selecting subgroups from a group. The former are called permutations and the latter are combinations.
As an example of what we mean by permutations, or ways of arranging things, consider the letters A, B & C. There are six possible permutations of that string. They are:
It turns out that the number of permutations in a case like this is
$$3! = 3 \cdot 2 \cdot 1 = 6,$$
where the ! indicates the factorial function. But we'll have more to say about that below.
Notice that when we're working with permutations, it's the order of the set members that matter. If order wasn't important, ABC is as good as BCA, and so on. Sometimes order will matter in our counting examples, and sometimes it won't, depending on the situation.
In the counting part of probability, combination refers to the number of subgroups that can be made from a set of things. Consider the group of four letters, A, B, C & D. Lets ask how many four, three, two and one-member groups we can form from such a group:
Because this set contains only four members, we can only form that one four-member set, {A, B, C, D}. In this case we'll decide that order of the members doesn't matter, but it might; all we'd have to do is change the rules.
There are four three-member subsets. They are
Here again, order doesn't matter, so we assume, for example, that {ABC} is the same as {BCA}. There are x two member sets. They are
Finally, there are four one-member subsets, {1}, {2}, {3} and {4}.
Permutations and combinations are very important components of work in probability. They are the denominator in many probability or odds calculations, as we shall see.
A permutation is one of the ways of ordering n objects. There are n! permutations of n unique objects.
A combination is one of the ways of selecting a subgroup of m objects from a larger group of n objects, where n ≥ m.
We must specify whether order of combinations matter, because that can change the number of possible combinations.
A permutation of a group of things – like outcomes of a probability experiment – is a particular way of ordering of those things. For example, imagine that we can draw the letters A, B or C from a bag (think Scrabble™) containing just those three letters. In what possible orders or permutations could draw them?
$$ \begin{matrix} ABC && ACB && BAC \\ BCA && CAB && CBA \end{matrix}$$
Here is a tree diagram to go with those permutations. Notice that once the first two letters have been chosen, the third is automatically set.
So there are six possible ways to arrange (or permutations of) the letters A, B and C. Now imagine that we want to find all permutations (or even just count the permutations) of this set of nine letters {A, B, C, D, E, F, G, H, J}. We could start that process like this:
$$ \begin{matrix} ABCDEFGHJ \\ ABCDEFGJH \\ ABCDEFHGJ \\ ABCDEFHJG \end{matrix}$$
... but you can see that this is going to take a long time. There has to be a beter way, and there is. Let's go back to our three-letter example and count choices. For the first letter, we have three choices, A, B or C. For the second letter drawn, because one is gone, there are only two choices. For the last, there's only one choice, and the total number of ways to choose letters is 3·2·1 = 6, which is the number of permutations we got by hand.
Now for our nine letter example, it's a similar situation: For the first letter drawn, there are nine possibilities: A, B, C, D, E, F, G, J. For the second letter, because we've already taken one away, there are eight possibilities. For the third, there are seven, and so on, down to the last one. The total number of permutations is
$$ \begin{align} 9! &= 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 \\[5pt] &= 362,880 \end{align}$$
Wow! Over a third of a million permutations. We definitely would not have wanted to written all of those down.
Here we have invoked the factorial function,
$$f(x) = x \cdot (x-1) \cdot (x-2) \cdot \: \dots \: \cdot 3 \cdot 2 \cdot 1 = x!$$
The factorial function grows very rapidly. Take a look:
x | x! |
---|---|
1 | 1 |
2 | 2 |
3 | 6 |
4 | 24 |
5 | 120 |
6 | 720 |
$\vdots$ | $\vdots$ |
10 | 3,628,800 |
The number of ways of arranging n unique objects is
$$N = n!$$
There are $n!$ permutations of n objects.
Notice that in our definition of permutations above, we said "permutations of n unique objects." What about non-unique objects?
As an obvious example, take the set of letters
Obviously, there is only one unique way to order this set, {AAA}. Any permutation is the same. So the number of permutations of this set just can't be 3!. In fact, the way we'd calculate it is
$$N = \frac{3!}{3!} = 1.$$
Now let's do a couple of examples to see why this is.
How many unique permutations (N) can we form from the letters in the word PARACHUTE?
$$N = \frac{9!}{2!} = \frac{362,880}{2} = 181,440$$
While it might not immediately be clear why we divided by the factorial of 2 there (2! = 2), it is clear that any permutation of our nine letters will have an identical partner, obtained by swapping the positions of the A's, thus we need to reduce our number to half of $n!.%
How many unique permutations (N) can we form from the letters in the word TENNESSEE?
$$N = \frac{9!}{3! \cdot 2! \cdot 2!} = \frac{362,880}{6 \cdot 2 \cdot 2} = 15,120$$
Here the number of permutations of nine unique letters (if they were unique) has been reduced to ⅓ because there are three E's, by half again because there are two N's and by half again because there are two S's.
Now let's turn to the odds of a typical kind of random lottery drawing. We draw six numbered balls from a pool of 40 balls labeled with integers, without replacing each drawn ball. There are 40 ways to choose the first number, but only 39 to choose the second (because we didn't replace the first number), 38 choices for the third, and so on, so the number of possible draws is
$$N = 40 \cdot 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 = 2,763,633,600$$
But in this game, it doesn't matter which order the balls were drawn. There are 6! ways to arrange those six balls (6! permutations), so we have to reduce our number of draws by that number by dividing:
$$N = \frac{40 \cdot 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35}{6!} = 3,838,380$$
Obviously, the fact that order is unimportant here significantly reduced the number of possibilities, and thus increased the probability of winning (small as it is – good luck!).
Let's round out by going back to our first example, the number of ways of rearranging the set {AAA}. We treated it just like any other set of three, noting that the number of permutations is $N = 3!$ But we also divided by 3! to remove the redundancies, resulting in only one real way to arrange the set.
Here's a general rule for permutations of n objects, with k sets of identical members, each of those with m members. For example, the letters in the word MISSISSIPPI form a set of N = 11 letters, with k = 3 sets of duplicates (the letters I, S and P). Subset k1 (the I's) has m = 4 members. Subset k2 (the S's) has m = 4 members, and subset k3 (the P's) has two members. The Number of permutations is:
$$N = \frac{n!}{m_1! \cdot m_2! \cdot m_3!}$$
In the general case for any k, we have
$$N = \frac{n!}{m_1! \cdot m_2! \cdot \dots \cdot m_k!}$$
Another way to write this, using the product symbol Π is:
$$N = \frac{n!}{\prod_{i=1}^k m_i!}$$
A combination is a way of selecting a subset of elements from a larger set. In each subset, we could decide that the order of set elements matters or does not; that's situation-dependent. For example, take the set
$$\{A, B, C, D, E\}.$$
Now let's consider the number of ways we can select two items from this set of five elements. Later, by the way, we'll start to use language like "five-choose-two" for such a situation. Here are the ways if order of the subsets doesn't matter, that is, if $\{A, B \} = \{B, A\},$ and so on:
$$\{A, B\}, \{A, C\}, \{A, D\}, \{A, E\}, \{B, C\}, \\[5pt] \{B, D\}, \{B, E\}, \{C, D\}, \{C, E\}, \{D, E\}.$$
To determine our number of sets mathematically, we'll note that there are five possibilities for choosing the first set element, A, B, C, D or E. With that one gone ("without replacement"), there are now four possibilities for choosing the second subset element, for a total number of possibilities,
$$N = 5 \cdot 4 = 20.$$
Now there's a discrepancy here. In our list of subsets above we counted $\{A, B\}$ but not $\{B, A\}.$ That is, we've already said that order doesn't matter in our subsets. In that case, we have to divide by two, which is the number of permutations of the two elements in each subset.
We can write a general formula for the number of ways that we can arrange subsets of k objects chosen from a set of n. To do so, we'll want to use the same factorial notation we did for permutations above. This will require a bit of shift of perspective. We'll start with
$$N = \frac{n!}{(n - k)!}$$
The n! in the numerator of our example problem is $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1.$ That's got more factors than our original numerator, $5 \cdot 4,$ so we divide those out using the term in the denominator, $(n - k)! = (5 - 2)! = 3 \cdot 2 \cdot 1.$ So our general formula for choosing subsets of k set members from a set of n members is
$$ \require{cancel} N = \frac{5 \cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 20 $$
But, this formula gives all possible combinations, including that {A, B} is the same as {B, A}. If we don't want order to matter, we need to divide by the number of ways of arranging k objects, k!. Here's a modified formula for when order of the subsets doesn't matter:
$$N = \frac{n!}{k!(n - k)!}$$
The
$$ \require{cancel} N = \frac{5 \cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{2! \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 10 $$
It turns out that the expression
$$N = \frac{n!}{(n - k)!}$$
has another use in mathematics. It's how we calculate the constant multipliers of the terms in a binomial expansion like $(x + y)^2$ or $(x + y)^n$. In counting we write them like this:
$$\binom{n}{k} = \frac{n!}{(n - k)!},$$
and we read these as "n choose k," meaning, "the number of ways of choosing k elements from a set of n." In this case, order matters and the number of subsets is its largest. If we want the order of the k elements in each subset not to matter, we need to divide by k!
$$\binom{n}{k} = \frac{n!}{k!(n - k)!}.$$
In our ABCD example, we're taking three objects at a time from a group of three objects $\{A, B, C\}$ total objects, so $k = 1$ and $n = 4,$ and the number of combinations is:
$$_4 P_1 = \frac{4!}{(3 - 3)!} = \frac{6}{1} = 6$$
Here we have to remember an important property of the factorial function, that $0! = 1.$ Let's also apply our rule to the last row of the table above, for which $k = 10$ and $n = 10:$
$$ \begin{align} _{10} P_1 = \frac{10!}{(10 - 10)!} &= \frac{3,628,800}{1} \\[5pt] &= 3,628,800 \end{align}$$
Let's do one more example. Let's say that this time we want to know all possible ways of rearranging four items taken from a pool of 10 distinct things, so $k = 4$ and $n = 10.$
$$ \begin{align} _{10} P_1 &= \frac{10!}{(10 - 4)!} = \frac{10!}{6!} \\[5pt] &= \frac{3,628,800}{720} = 5,040 \: \text{ways} \end{align}$$
We can think of combinations as permutations for which order doesn't matter. That is, ABC, CBA, BCA, and so on, would be considered the same if we're only worried about combinations. One example of this is lottery numbers. We don't care about whether we get the numbers (say six chosen from a pool of 40) in the correct order, just that we get the numbers right.
In the last example above, we took four objects from a set of ten and asked how many permutations – unique, order-dependent groups – we can make. If the order of those didn't matter, we'd have to reduce that number by the number of ways that four objects can be permuted, or 4!. It would look like this:
$$ \begin{align} _n C_k &= \frac{10!}{4!(10 - 4)!} = \frac{_{10} P_4}{4!} \\[5pt] &= \frac{3,628,800}{(24)(720)} = 210 \end{align}$$
Notice that the number of combinations is just the number of permutations divided by the number of permutations of the subset drawn ( k! ). The general formula for combinations is
$$_n C_k = \frac{n!}{k!(n - k)!} = \frac{_n P_k}{k!}$$
Very often, this is written using the binomial coefficient, $\binom{n}{k},$ like this:
$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$
The binomial coefficient, $\binom{n}{k},$ is often pronounced "n choose k."
The number of possible six-number lottery draws from a pool of 40 numbers, where the order of the drawn numbers doesn't matter (a combination) is
$$ \begin{align} \binom{40}{6} &= \frac{40!}{6!(40 - 6)!} \\[5pt] &= \frac{8.159 \times 10^{47}}{(720)(2.952 \times 10^{38})} \\[5pt] &= 3,838,380 \end{align} $$
That is, the odds of getting the correct six numbers is 1 out of 3.84 million. Good luck! (Compare this lottery solution to the way we got it in the permutations section above.
A permutation is the number of ways of arranging n distinct elements of a set. The number of permutations of n things is $n!$
A combination is a collection of k elements of a set taken from a larger set of n elements. The number of combinations of k elements of a set of n is
$$_n C_k = \binom{n}{k} = \frac{n!}{k!(n - k)!}$$
If the order of each subset matters, that is if {A, B} means something different from {B, A}, then that number is
$$k! _n C_k = k!\binom{n}{k} = \frac{n!}{(n - k)!}$$
1. |
Consider the set A = {-7, -6, -5, 1, 2, 3, 4, 5, 6}. How many ways are the to choose a negative or an even number from A? SolutionThe problem says "an negative or an even number," which we could interpret as meaning either a negative or an even or both — or not both. Let's work out the probabilities for each. First, let P(E) be the probability of getting an even number and P(–) be the probability of getting a negative. It's easy to see that given our set of 9 elements, $$P(E) = \frac{4}{9} \phantom{00} \text{and} \phantom{00} P(-) = \frac{3}{9}$$ If we mean either or both, the probability is $$P(E \cup -) = \frac{4}{9} + \frac{3}{9} = \frac{7}{9} = 0.78$$ If we want the probability of obtaining an even or a negative, but not both, we have to subtract from the first result the probability of obtaining both: $$ \begin{align} P &= P(E \cup -) - P(E \cap -) \\[5pt] &= \frac{7}{9} - \frac{3}{9} \cdot \frac{4}{9} \\[5pt] &= \frac{7}{9} - \frac{12}{81} \\[5pt] &= \frac{51}{81} = 0.63 \end{align}$$ Here is a Venn diagram of this scenario. |
||||||||
2. |
How many ways are there to pick a red king or a club from a standard 52-card deck? SolutionThe figure shows the 52 unique possibilities for card types in a 52-card deck. The black boxes outline our two outcomes, spades and red kings. These sets don't overlap, so the probability of drawing from either of these sets is just $$\begin{align} \frac{13}{52} + \frac{2}{52} &= \frac{15}{52} \\[5pt] &\approx 29 \% \end{align}$$ |
||||||||
3. |
How many outcomes are possible for tossing two fair coins and a 6-sided die at the same time? SolutionThe table shows that there are 24 total outcomes. On the left are the four outcomes for two coins, {HH, HT, TH, TT}, and above are the six outcomes for rolling a six-sided die. Numerically, the result is $n = n_c \cdot n_c \cdot n_d,$ where $n_c$ and $n_d$ are the number of possible results for the coin flip and die roll, respectively. So: $$ \begin{align} n &= n_c^2 \cdot n_d = 2^2 \cdot 6 \\[5pt] &= 24 \end{align}$$ |
||||||||
4. |
In how many unique ways can the letters of the word "MISSISSIPPI" be arranged? SolutionThere are 11 letters in the word and there are 11! ways of arranging 11 unique letters. These letters are not unique, however, so we have to divide by 2! for the number of P's, 4! for the number of ways of rearranging the S's and 4! again for the number of ways of rearranging the four I's. $$n = \frac{11!}{2! \cdot 4! \cdot 4!} = 34,650$$ So there are 34,650 unique combinations of the letters in the name MISSISSIPPI. |
||||||||
5. |
In how many unique ways can the letters of the word "JUGGERNAUT" be arranged? SolutionThis problem is similar to #4 above. There are two G's and two U's in this word, so in any configuration of the 10-letter string, these could be swapped and we wouldn't know it. The number of unique rearrangements is $$n = \frac{10!}{2! \cdot 2!} = 907,200$$ So there are 907,200 unique arrangements of those ten letters. That's amazing. |
||||||||
6. |
A skateboard shop stocks 12 different decks, 3 types of trucks and 8 types of wheels. How many different skateboards (Deck + trucks + wheels) can be constructed from these parts? SolutionThe choices of decks, trucks and wheels are all independent, so the number of boards is just $$ \begin{align} n &= n_d \cdot n_t \cdot n_w \\[5pt] &= 12 \cdot 3 \cdot 8 = 288 \end{align}$$ |
||||||||
7. |
This is a classic problem in probability. How many people must gather together in a room to make the probability that two of them will share the same birthday 50% ? SolutionOne reason to study a problem like this is that it reminds us that it's sometimes easier to solve the converse problem and then convert at the end. That is, if we're asked for P(B), sometimes it's easier to calculate P(!B), and then recognize that P(B) = 1 - P(!B). So let's start with a single person in our room and ask what the probability is that he doesn't share a birthday with anyone else in the room. Well, of course that's the easy one. There are 365 out of 365 chances. The chance of him sharing a birthday is $$P(B) = 1 - \left( \frac{365}{365} \right) = 0.$$ If we add a second person, the first person takes up one possible birthday, so the chances that they don't share a birthday are 364/365. Overall, the probability of sharing a birthday is then $$P(B) = 1 - \left( \frac{365}{365} \right) \left( \frac{364}{365} \right) = 0.0027$$ Adding the third person reveals a pattern, $$ \begin{align} P(B) &= 1 - \left( \frac{365}{365} \right) \left( \frac{364}{365} \right) \left( \frac{363}{365} \right) \\[5pt] &= 0.0082 \end{align}$$ Now we want this to be greater than or equal to 0.5, and the pattern should be fairly obvious. We can write $$1 - \left( \frac{365}{365} \right) \left( \frac{364}{365} \right) \dots \left( \frac{365-n+1}{365} \right),$$ where $n$ is the number of people in the room. Now this formula can be expanded using a spreadsheet, calculating probabilities for each $n.$ If you do this (it's easy), you'll find that once the number of people gets to 23 you're past the 50% probability mark. The numbers from such a spreadsheet for $n$ up to about 70 are graphed below. Notice that by 70 people or so, it is almost certain that at least two people will share the same birthday. One way to think about why this is so is to distinguish between asking what's the probability that two people will share some pre-specified birthday, like July 30, and that they'll simply share some unspecified birthday of the 365 days available. Those are different problems. |
||||||||
8. |
Winning a lottery consists of picking six numbers from a pool of 40 {1, 2, 3, ..., 40} drawn without replacement. The order of the six number doesn't matter. Calculate the odds of winning the lottery. SolutionThe number of possibilities for the first number is 40. With that number gone (no replacement), the number of possibilities for the second number is 39. If we carry out this line of reasoning, we get 40·39·38·37·36·35 possibilities. But, we have to reduce this by the number of ways of arranging those numbers, which is 6!, so we have $$ \begin{align} n &= \frac{40 \cdot 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35}{6!} \\[5pt] &= 3,838,380. \end{align}$$ So the odds of winning this lottery are 1 in 3,838,380. |
||||||||
9. |
A mission to Mars will include 4 astronauts from a pool of 16 candidates. Five of the candidates are trained in soil science. If the mission requires at least two trained soil scientists, how many different crews can be selected? SolutionWe can write our pool set like this: $$ \begin{align} P = \{&A, A, A, A, A, A, A, A \\[5pt] &A, A, A, S, S, S, S, S\}, \end{align}$$ where A is a generic astronaut and S stand for soil specialist. For the soil specialists, we have 5 choices for the first and four for the second (no replacement), for 20 choices. For the other astronauts, we pick two from a field of ten, so the number of groups is 10·9 = 90. So the number of choices is 90·20 = 1800. But we have to account for the fact that some of these teams contain the same people, just arranged in a different order, and that shouldn't matter. So the number of teams is $$n = \frac{5 \cdot 4 \cdot 10 \cdot 9}{2! \cdot 2!} = 450.$$ |
||||||||
10. |
How many of the numbers {100, 101, 102, ... , 999} have three different digits in increasing order or in decreasing order? SolutionTo solve this one, I began with the quick little python program shown here. It simply counts all of the possibilities. For the ascending numbers, the smallest is 123 and the largest is 789, with 84 total possibilities that meet the ascending requirement. That's just the binomial $\binom{10}{3}$ which gives only one way of rearranging the numbers. That is, 789 is allowed but 798, 879, 897, 987 and 987 are not. $$ \begin{align} \binom{9}{3} &= \frac{n!}{k!(n-k)!} \\[5pt] &= \frac{9!}{3!(9-3)!} \\[5pt] &= 84 \end{align}$$ For the descending numbers, we can use zero. The largest is 987 and the smallest is 210. We have: $$ \begin{align} \binom{10}{3} &= \frac{n!}{k!(n-k)!} \\[5pt] &= \frac{10!}{3!(10-3)!} \\[5pt] &= 120 \end{align}$$ These are just the solutions we get from the python code.
The results from the code are: Ascending = 84, Descending = 120 |
||||||||
11. |
1275 marbles are placed in a box. Before being placed, one marble is labeled "1", two are labeled "2", three are labeled "3", and so on, until the final 50 marbles are labeled with "50." If marbles are drawn from the box without replacement, what is the minimum number of marbles that need to be drawn to guarantee at least ten marbles with the same label? SolutionNotice that this problem is asking for a guarantee that we'll draw ten of one number, so we have to be thorough. Drawing marbles labeled 1-9 doesn't make any difference because there aren't ten of any of those. The number of those is 1 + 2 + 3 + ... + 9 = 45 marbles. We add those to our list. Now from the remaining marbles, if we draw nine of each kind, that's is 41·9 = 369 marbles. Now if one more marble is drawn, it has to match up with one of the other groups of nine. So our minimum number is $$45 + 369 + 1 = 415$$ |
||||||||
12. |
The RedSox play the Yankees in a three-game series. The Yankees probability of winning any game is not zero, is independent of other games, and is 1.6 times as large as their probability of winning the series. Calculate the probability that the Yankees will win the series. SolutionLet P(Y) be the probability that the Yankees win a game, then 1-P(Y) is the probability that the RedSox win (which would, of course, be expected). Then we can list all of the possible series outcomes in a table:
If the Yankees win two in a row, a third game is not required. Now if we sum these probabilities, we'll have the probability that the Yankees win the series: $$P^2(1 - P) + P^2(1 - P) + P^2 = \frac{P}{1.6},$$ where P is an abbreviation for P(Y) just to make things easier, and the right side reflects that P(win series)·1.6 = P. Now we can solve this equation with a little bit of algebra: $$ \begin{align} 2P^2(1 - P) + P^2 &= \frac{P}{1.6} \\[5pt] 2P^2 - 2P^3 + P^2 &= \frac{P}{1.6} \\[5pt] 3P^2 - 2P^3 &= \frac{P}{1.6} \\[5pt] 3P - 2P^2 &= \frac{1}{1.6} \\[5pt] -2P^2 + 3P &= \frac{1}{1.6} \\[5pt] P^2 - \frac{3}{2}P &= -\frac{1}{3.2} \\[5pt] \end{align}$$ $$ \begin{align} P^2 - \frac{3}{2}P + \left( \frac{3}{4} \right)^2 &= \frac{9}{16} - \frac{1}{3.2} \tag{1} \\[5pt] &= \frac{18}{32} - \frac{10}{32} \\[5pt] &= \frac{1}{4} \\[5pt] \left( P - \frac{3}{4} \right)^2 &= \frac{1}{4} \tag{2} \\[5pt] P &= \frac{3}{4} ± \frac{1}{2} \\[5pt] &= 0, \frac{5}{4}, \frac{1}{4} \tag{3} \end{align}$$ Here steps 1, 2 and 3 are the process of completing the square. In step (3) we realized that by dividing everything through by P above, we dropped a root, P = 0. Now of these three solutions, we know that 5/4 is not a probability and that P(Y) ≠ 0, so the Yankees have a probability of winning the series of ¼. |
xaktly.com by Dr. Jeff Cruzan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. © 2022, Jeff Cruzan. All text and images on this website not specifically attributed to another source were created by me and I reserve all rights as to their use. Any opinions expressed on this website are entirely mine, and do not necessarily reflect the views of any of my employers. Please feel free to send any questions or comments to jeff.cruzan@verizon.net.