Many problems in probability can be phrased in the language of "how many ways can we pick r objects out of a group of N objects." We now calculate the answer to this question.
If the order of the r objects is important, than the "number of ways to pick r objects out of a group of N objects" is called: the number of permutations of N objects taken r at a time, and denoted by the symbol NPr. What is the numerical value of NPr? For the 1st choice we can choose any one of N objects. For the 2nd choice we can choose any one of the remaining N-1 objects. For the 3rd choice we can choose any one of the remaining N-2 objects, and so on down until for the rth choice we can pick any one of the remaining N-r+1 objects. We therefore find
NPr = N x (N-1) x (N-2) x .... x (N-r+1)
Note that in this counting, the order in which objects are picked is important. Assume the original objects are numbered 1, 2, 3, ..., N, and we are picking any three. In computing NPr the sequence 5, 3, 7, is counted separately from the sequence 3, 5, 7, which is counted separately from the sequence 3, 7, 5, which is counted separately from the sequence 5, 7, 3, and so on.
Often we do not wish to distinguish between sequences
which have the same objects in them, but in which the objects are ordered
differently. If the ordering is not important, then the number of unique
ways to pick r objects out of a group of N objects is called: the number
of combinations of N objects taken r at a time, and is denoted by
the symbol NCr,
or also by the symbol 
. To
compute the numerical value of NCr,
note that it is just equal to the number of permutations NPr
divided by the number of ways to order the r objects chosen. To order the
r numbers chosen, we have r choices for the 1st object, r-1 choices for
the 2nd object, r-2 choices for the 3rd object, and so on down until there
is only 1 choice left for the last rth object. What we have described is
just the number of permutations of r objects taken r at a time, and is
equal to
rPr = r x (r-1) x (r-2) x ... x 2 x 1
This combination occurs so often, that it is given a special name and times
rPr = r x (r-1) x (r-2) x ... x 2 x 1 = r!
and called "r factorial". For example, 2! = 2 x 1 = 1, 3! = 3 x 2 x 1 = 6,
4! = 4 x 3 x 2 x 1 = 24, and so on. We define 1! = 1 and also 0! = 1.
Thus we conclude that the number of combinations of N objects taken r at a time is
NCr
= = 
Now note that we can use the definition of NPr and factorial to write
NPr x (N-r)! = [N x (N-1) x .... x (N-r+1)] x [r x (r-1) x ... x 2 x 1] = N!
or equivalently, NPr= N!/(N-r)!. We can then write NCr as,
NCr
= = 
Note from this result that
= 
since N-(N-r) = r. This
result follows intuitively by noting that when we choose r objects from
a group of N objects, we leave N-r objects behind. If we regard these N-r
objects left behind as the "chosen" objects, we see that the number of
combinations of N objects taken r at a time is exactly equal to the number
of combinations of N objects taken N-r at a time.
To see how to use combinations in the context of probability problems, consider the example we did earlier. If we flip four coins, how many of the possible outcomes will have exactly two heads?
From the four coins, we want to choose two of them to be heads - the remaining two must therefore be tails. The number of ways to choose two heads for four coins is just:
Thus there are six outcomes with exactly two heads. This is the same answer we found earlier.
More generally, if one flips N coins, the number
of possible outcomes with exactly r heads will be, NCr
= = .
Since the number of all possible outcomes in N flips is 2N,
we have that the probability to flip exactly r heads in N flips is NCr/2N.
Another example: If we roll four dice, how many outcomes will have at least one "6" on top?
The possibilities consistent with at least one "6" are: one "6", two "6"s, three "6"s, or four "6"s.
The number of ways to choose one "6" from four dice is:
The remaining three dice can each land in one of five possible ways, so the total number of outcomes with exactly one "6" is 4x 5x 5x 5 = 500.
The number of ways to choose two "6"s from four dice
is: 
The remaining two dice can each land in one of five possible ways, so the total number of outcomes with exactly two "6"s is 6x 5x 5 = 150.
The number of ways to choose three "6"s from four
dice is: 
The remaining one die can each land in one of five possible ways, so the total number of outcomes with exactly three "6"s is 4x 5 = 20.
The number of ways to choose four "6"s from four dice is:
There are no remaining dice. So the total number of outcomes with exactly four "6"s is 1.
Adding all together, there are 500 + 150 + 20 + 1 = 671 possible outcomes with at least one "6" showing. Since the number of all possible outcomes is 64 = 1296, the probability to role at least one 6 is then 671/1296.
This is the same answer that we found earlier by the indirect method:
(prob at least one 6) = 1 - (prob no 6) = 1 - (5/6)4 = 1 - (625/1296) = 671/1296.
Example from Text
5) Six balls numbered 1,2,3,4,5,6 are in a jar. Two are chosen at random.
a) How many possible outcomes are there if the order of the picking does not matter?
This is just the number of ways to choose 2 balls
from 6, where order does not matter, or 6C2
= 
b) Think of the choice of the two balls as if it were a lottery. Before the selection of the two balls, you independently guessed two different numbers from 1 to 6.
i) What is the probability that you guessed both balls correctly?
Of the 15 possible outcomes of the lottery, there is only one which matches the two numbers you have guessed, so the probability to have guessed both correctly is just 1/15.
ii) What is the probability that you guessed one of the balls correctly but not the other?
We will solve this two ways. To help us think about this, let us suppose that you have guessed the numbers #1 and #4.
Method one: Of the 15 possible outcomes of the lottery, the number of outcomes which include the #1 but not the #4 is 4, since one of the balls must be #1, and the second can be either #2, #3, #5, or #6 (i.e. it may not be #4). Similarly, the number of outcomes which include the #4 but not the #1 is also 4, since one ball must be #4, and the second can be #2, #3, #5, or #6 (i.e. it may not be #1). So the total number of outcomes in which one ball has been guessed correctly but not the other is 4 + 4 = 8.
The total number of outcomes is 15, so the probability to guess only one ball correctly is 8/15.
Method two: Again assuming that we have guessed #1 and #4, then the probability that the first ball picked in the lottery is either #1 or #4 is 2/6; the probability that the second ball picked will not be one we have guessed is then 4/5, since only 4 of the remaining 5 balls are different from the number we guessed. So the probability that we guess the first ball correctly but not the second is (2/6)x(4/5)=4/15. But we also have to consider the case where it is the second ball that we guess correctly but not the first. The probability that the first ball is different from either number we have guessed is 4/6; the probability that the second ball is then equal to one of the numbers we have guessed is then 2/5, since 2 of the remaining 5 balls agree with the numbers we have guessed. So the probability that we guess correctly the second ball but not the first is (4/6)x(2/5)=4/15. So the probability that we guess only one ball correctly but not the other, is the sum of the probability that we guessed the first but not the second, plus the probability that we guessed the second but not the first, i.e.
(4/15) + (4/15) = 8/15.
iii) What is the probability that we have guessed neither ball correctly?
The number of outcomes of the lottery that will have
no number in common with the two numbers we have guessed is just 
.
That is, the balls chosen in the lottery must be any two from the four balls which are not the ones we guessed. The number of ways to do this is just 4C2. So the probability to guess neither ball correctly is 6/15.
c) You can check that the probabilities of (i), (ii), and (iii) in part (b) add up to unity, since these three cases cover all possible outcomes.
1/15 + 8/15 + 6/15 = 15/15 = 1
Example This problem is just like the last, but with the numbers adjusted to reflect a situation closer to a real state lottery.
A jar is filled with 40 numbered balls, each with a different number between 1 and 40. Six balls are randomly drawn out of the jar, as in the lottery, i.e. we do not care about the order in which the balls are drawn.
a) How many possible outcomes for the chosen 6 numbers are there?
This is asking how many ways can we choose 6 balls out of 40, with the order of selection being ignored. The answer is given in terms of combinations:
40C6
= 
= N
b) If you win the lottery by guessing all the six numbers which are randomly drawn, how likely is it that you will win with one ticket?
If we guess 6 numbers on our lottery ticket, there is only one of the N possible outcomes of the lottery that will match all our 6 numbers. The probability this happens is therefore:
c) If a million people play, all choosing their numbers independently of one another, how likely is it that at least one person will win the lottery?
The (prob at least one wins) = 1 - (prob no one wins) ,
since these are mutually exclusive outcomes that cover all possibilities, i.e. either no one wins, or at least one person wins.
The probability that one person loses the lottery in one play is, 1-p, i.e. one minus the probability to win. The probability two people lose in two independent plays is therefore (1-p)x(1-p)=(1-p)2. This is by our basic rule #2: the probability that two independent events occur is the product of their probabilities. The probability that three people lose in three independent plays is therefore (1-p)x(1-p)x(1-p)=(1-p)3, and so on, so that the probability that one million people all lose in one million plays is: (1-p)1,000,000. So the probability that at least one person wins in one million plays is:
1 - (1-p)1,000,000 = 1 - (1 - 0.00000026)1,000,000 = 1 - 0.77 = 0.23
So there is a 23% chance that some one will win.
Note that this is a different answer from the one we would get if all million players coordinated their plays so that no two people chose the same set of six numbers. Then, since each play is a mutually exclusive outcome from all the other plays, the probability that at least one person wins is the sum of probabilities that any one choice of numbers wins, i.e. 1,000,000xp = 0.26. This is slightly larger than what we found if all players chose their numbers independently. The difference is because when the players choose numbers independently, there is always some chance that two players will choose exactly the same set of 6 numbers. By coordinating their efforts to choose different sets of numbers, the million players can be sure to cover more possible outcomes.
d) If you get a lesser prize for choosing 5 of the 6 numbers correctly, what is your probability of winning?
Suppose you pick your 6 numbers on your lottery ticket. Let's compute the number of possible outcomes of the lottery that will have 5 numbers agreeing with numbers you chose, but with one number disagreeing.
Suppose that it is your first 5 numbers that agree and it is the last 6th number that disagrees. The number of outcomes consistent with this is just the number of ways the lottery can choose a ball that does not match this last 6th number - this is 34, because it can only be one of the 34 numbers you did not guess. Now suppose that it is your last 5 numbers that agree and it is the first number that disagrees. Again, the number of outcomes consistent with this is 34. Similarly, it might be the 2nd, 3rd, 4th, or 5th of your numbers which is the one that disagrees with the lottery result. In each case there are 34 outcomes of the lottery which will agree with your five other numbers. So the total number of lottery outcomes which will give you five and only five numbers guessed correctly is:
34x6=204
where 34 is the number outcomes that match a particular group of 5 out of your 6 numbers, and 6 is the number of ways to choose the number which is not guessed correctly. The probability to guess exactly 5 numbers correctly is therefore
q = 
The probability to win the lottery by guessing at least 5 numbers, i.e. by guessing either only 5 or by guessing all 6 is therefore,
q + p = 0.00005326
Let us find q by a second method. Imagine looking at your lottery card with your 6 guessed numbers, as the lottery balls are being drawn. The probability that the 1st ball drawn is one of your numbers is 6/40. The probability the 2nd ball drawn is one of your remaining 5 numbers is 5/39, since only 39 balls are left. The probability that the 3rd ball drawn is one of your remaining 4 numbers is 4/38, and so on. So the probability that the first 5 balls selected in the lottery agree with 5 of your numbers, but the 6th does not is:
where the last factor is 34/35 because if the last ball is not one of your 6 numbers, it must be one of the 34 other numbers, and there are now only 35 balls left to choose from.
This does not cover all the possibilities however. It may be that the first ball drawn in the lottery is the one that does not agree with any of your numbers, but the next 5 balls drawn will. The probability for this to happen is:
Or it may be that the second ball drawn in the lottery is the one that does not agree with any of your numbers, but the first and the last four balls drawn do. The probability for this to happen is:
You can check, by multiplying the numerators and denominators together, that all three terms above give exactly the same value:
= 
Similarly, you can check that if it is the 3rd ball, or the 4th ball, or the 5th ball drawn in the lottery that is the one that does not agree with any of our guessed numbers, the probability is again 34/N.
Since there are 6 ways to choose which ball drawn
in the lottery will not agree with any of your guessed numbers, and the
probability in each case is 34/N, the total probability that you guess
exactly 5 numbers correctly is 6x34/N = 204/3,838,380, which is the same
answer as we got by the first method.
e) Suppose it costs $1 to pay the lottery, and you play each week for the nest 40 years for a total of 2000 times. Assume that if you have at least 5 of the 6 numbers drawn in any given lottery you will win more than the $2000 it will cost to play these games. What is the probability that you come out winning more than you have spent?
This is the probability to win at least once in 2000 plays, where by "win" we mean to guess 5 or more numbers correctly. This is similar to the question in part (c).
(prob to win at least once) = 1 - (prob never win)
The probability not to win in one play is 1-(p+q)
The probability not to win in two plays is [1-(p+q)]2
The probability not to win in 2000 plays is [1-(p+q)]2000
So the probability to win at least once is
1-[1-(p+q)]2000 = 1-[1-0.00005326]2000 = 1-0.999946742000 = 1-0.899 = 0.101
So you have only a 10% chance to win in 2000 plays.
This is larger than you may have thought, but still very few people would
bet $2000 with only a 10% chance to win.