[A, SfS] Chapter 2: Probability: 2.2: Counting Methods
Counting Methods
In this lesson you will learn how to compute:
- The number of permutations of #n# objects.
- The number of permutations of #k# objects selected from #n# objects.
- The number of combinations of #k# objects selected from #n# objects.
- The number of ways of allocating #n# objects among #r# groups consisting of #k_1,k_2,\ldots,k_r# objects.
#\text{}#
The Fundamental Principle of Counting
Suppose some experiment can result in #n_1# possible outcomes, and for each of those outcomes a second experiment can result in #n_2# possible outcomes, and for each of those outcomes a third experiment can result in #n_3# possible outcomes, and so on, until the #k#th experiment, which can result in #n_k# possible outcomes.
Then the number of different sequences of outcomes that can occur when the #k# experiments are performed is: \[n_1 \cdot n_2 \cdot \ldots \cdot n_k\] This is called the Fundamental Principle of Counting.
Example 1: If you flip a coin five times, how many different sequences of outcomes are possible?
For each flip there are two outcomes possible, so there are
\[2\cdot 2\cdot 2\cdot 2\cdot 2 = 2^5 = 32\] possible sequences of outcomes (such as #HHTHT#, #THTTT#, #HTHHT#, etc.).
Example 2: Suppose you are choosing #4# people (one at a time) from among #10# people to be on your basketball team. How many possible teams can you choose?
For the first choice there are #10# possible outcomes, then for the second choice there are #9# possible outcomes, then for the third choice there are #8# possible outcomes, and for the last choice there are #7# possible outcomes.
So the number of possible sequences for the selection of #4# team members is:
\[10\cdot 9\cdot 8\cdot 7 = 5040\]
But note that this is not the number of possible teams, because you can get the same #4# team members in #4\cdot 3 \cdot 2 \cdot 1 = 24# different sequences out of the #5040# possible sequences.
So there are #\cfrac{5040}{24} = 210# possible teams.
#\text{}#
If you have #n# distinct objects that you want to place in some order, and you want to know how many ways you can do so, the Fundamental Principle of Counting can be used.
There are #n# possible choices for the first position, after which there are #n - 1# possible choices for the second position, and so on, with only one possible choice remaining for the last position.
Thus there are
\[n(n-1)(n-2)\cdots (3)(2)(1) = n!\]
(that is, “#n# factorial”) ways to do this.
Permutation
Putting distinct objects into some order is called a permutation.
Calculating the number of permutations
There are #n!# ways to form a permutation of #n# distinct objects.
For example, a playlist consists of #12# songs. If the media player is set on shuffle mode, in how many different sequences can the #12# songs be played?
The answer is #12! = 479001600# different permutations.
#\text{}#
Now suppose you will select #k# objects from among #n# objects and then place those #k# objects in order. You need to count how many different choices of #k# objects are possible, and, for each of those choices, into how many distinct sequences the #k# chosen objects can be placed.
There are #n# choices for the first position in the sequence, #n-1# choices for the second position, #n-2# choices for the third position, and so on, until #n - (k-1) = n-k+1# choices remain for the #k#th position.
So there are #n(n-1)(n-2)\cdot\cdot\cdot(n-k+1)# possible permutations of #k# objects selected from #n# objects. This formula is not very nice to look at or easy to remember. Luckily, the formula can be rewritten into a much simpler form.
Selecting k from n objects
There are \[\cfrac{n!}{(n-k)!}\] possible permutations of #k# objects selected from #n# objects.
For example, a playlist consists of #12# songs. If the media player is set on shuffle mode, and you will only listen to the first #5# songs, in how many different sequences can the #5# songs be selected from among the #12# songs and played?
The answer is:
\[\cfrac{12!}{(12-5)!} = \cfrac{12!}{7!} = \cfrac{479001600}{5040} = 95040\]
#\text{}#
Next, suppose you will select #k# objects from among #n# objects, but the order of the selected objects is not relevant. You just want to know how many distinct subsets of #k# objects are possible when selected from #n# objects.
We actually already covered this idea when we were discussing the selection of team members for a basketball team. We divided the number of ways to select and order #4# players from among #10# candidates (i.e., the number of permutations) by the number of ways to order the #4# selected players (i.e., #4! = 24#). That is the general procedure.
Combination
When the order of the selected objects is not relevant, we do not call the selection a permutation, but rather a combination.
Calculating the number of combinations
The number of combinations of #k# objects selected from among #n# objects is:
\[\cfrac{\cfrac{n!}{(n-k)!}}{k!} = \cfrac{n!}{k!(n-k)!}\]
There is a special notation for this formula, which is #\binom{n}{k}#, which we pronounce “#n# choose #k#”.
So the number of combinations of #k# objects selected from among #n# objects is:
\[\binom{n}{k}=\cfrac{n!}{k!(n-k)!}\]
For example, a deck of poker cards consists of #52# distinct cards. A poker hand typically consists of #5# cards. How many different poker hands are possible?
The order of the cards is not relevant, so there are "#52# choose #5#" different poker hands possible, i.e.,
\[\binom{52}{5} = \cfrac{52!}{5!(52-5)!} = 2598960\] possible hands.
#\text{}#
Finally, suppose there are #n# objects which must be allocated among #r# distinct groups, with #k_1# in the first group, #k_2# in the second group, and so on, and #k_r# in the #r#th group. Thus #n=k_1+k_2+...+k_r#. The order of the selected objects in each group is not relevant. In how many ways can this be done?
Going group by group, there are
\[\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdot\cdot\cdot\binom{n-k_1-k_2-\cdot\cdot\cdot-k_{r-1}}{k_r}\] ways to do this.
Fortunately, this simplifies into a nice formula that is easier to remember.
Allocating objects among groups
There are
\[\cfrac{n!}{k_1!k_2!\cdots k_r!}\] ways to allocate #n# objects among #r# distinct groups, with #k_1# in the first group, #k_2# in the second group, and so on, and #k_r# in the #r#th group.
For example, the senior tutor must allocate #30# new students among #6# available tutors, with #3# of the tutors having space for #7# new tutees each and #3# of the tutors having space for only #3# tutees each. In how many ways can the senior tutor do this?
He can do so in
\[\cfrac{30!}{7!7!7!3!3!3!} = 9.5921 \cdot 10^{18} \] distinct ways.
#\text{}#
Once you have developed counting methods, you can use them to facilitate probability computations. If you have equally-likely permutations or combinations in the sample space, then the probability of an event #E# is the ratio of the number of permutations or combinations comprising event #E# to the number of permutations or combinations in the sample space.
Example 1: Suppose a password must consist of #6# symbols, where the available symbols are the #26# letters of the English alphabet and the #10# digits of the base-#10# numerical system (thus #36# symbols available).
If each symbol can be used more than once in the password, then this means that for each of the #6# positions in the password there are #36# options, and therefore there are
\[36^6 = 2176782336\] possible passwords.
But if a password cannot use any symbol more than once, then we have the situation in which we are selecting and ordering #6# symbols from among #36# symbols, i.e., there are
\[\cfrac{36!}{(36-6)!} = 1402410240\] possible permutations of #6# symbols chosen from #36# symbols.
If we then want to know the probability that a randomly generated password will not use any symbol more than once, we compute:
\[\cfrac{1402410240}{2176782336} \approx 0.644\]
Example 2: In the game of poker a player receives #5# cards (a “hand”) selected from among #52# cards. The #52# cards are divided evenly among four “suits”: hearts, spades, diamonds & clubs. The #13# cards in each suit are labeled #Ace, 2,3,4,5,6,7,8,9,10,Jack,Queen,King#.
These labels are called denominations. So a poker hand could consist of the #7# of hearts, the Jack of clubs, the #3# of clubs, the #Ace# of diamonds, and the #3# of spades.
There are
\[\binom{52}{5} = 2598960\] different possible hands. In how many ways can a player have a hand consisting of exactly three cards of the same denomination?
First, we have to choose the denomination. There are
\[\binom{13}{1} = 13\] ways to do this.
Then, within the denomination, we have to choose #3# of the #4# suits. There are
\[\binom{4}{3} = 4\] ways to do this.
Then the remaining #2# cards in the hand must not be from this denomination, so must be chosen from among the other #48# cards. There are
\[\binom{48}{2} = 1128\] ways to do this.
So there are
\[(13)(4)(1128) = 58656\] ways to have a hand consisting of exactly three cards of the same denomination.
So what is the probability that a randomly-generated hand of cards would have exactly #3# cards from the same denomination? The probability would be:
\[\cfrac{58656}{2598960} \approx 0.023\]
#\text{}#
Using R
Computing a factorial
To compute #n!# using #\mathrm{R}#, use the #\mathtt{factorial()}# function.
For example, to compute #8!# use:
> factorial(8)
Computing a permutation
The number of permutations of #5# objects selected from #13# objects can be computed using:
> factorial(13)/factorial(13-5)
Computing a combination
The number of combinations of #5# objects selected from #13# objects can be computed using:
> factorial(13)/factorial(5)/factorial(13-5)
However, this last procedure can be performed more efficiently using the #\mathtt{choose()}# function, as:
> choose(13,5)
Generating a random permutation
If you have a vector consisting of #n# elements, you can generate a random permutation of the elements using the #\mathtt{sample()}# function.
If the name of the vector is #X#, then you would use:
> sample(X)
This will produce a vector consisting of all #n# elements, but in a different order.
Generating a random selection of elements
If you want to select #k# of those #n# elements, whether you care about the order of the selection (a permutation) or not (a combination), use:
> sample(X,k)
This will produce a vector of #k# elements randomly selected from the #n# elements of #X#, in a random order.
If you have a vector consisting of the names or identification codes for a population of elements, and you want to select a random sample of size #k# from that population, this would be one useful way of doing so.
Or visit omptest.org if jou are taking an OMPT exam.
