AP Statistics Curriculum 2007 Prob Count
Contents
General Advance-Placement (AP) Statistics Curriculum - Counting Principles in Probability Theory
Counting Principles in Probability Theory
There are many useful counting principles to compute the number of ways that certain arrangements of objects can be formed. Examples of such problems are counting combinations or permutations of objects. For a given collection of objects {\(a_i\)}, counting methods help us describe protocols for computing numbers of arrangements of these objects when taken n at a time. For instance the number of different possible orderings of a deck of n cards is \(1\times 2\times 3 \times 4 \times \cdots \times n = n!\).
Permutations
Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. For example, with the numbers {1, 2, 3, 4, 5, 6}, each possible ordering consists of a complete list of the numerals, without repetitions. There are 6!=720 total number of permutations of these numerals, one of which is: {6, 5, 4, 3, 2, 1}.
Permutations with repetitions
When the ordering of objects matters, and an object can be chosen more than once, the number of permutations is \(n^r\), where n is the number of objects from which you can choose and r is the number of objects we can choose (repetitions allowed). For example, if you have the letters A, B, C, and D and you wish to discover the number of ways to arrange them in three letter patterns, then there are \(4^3\) or 64 arrangements. Note that in this case:
- order matters (e.g., A-B is different from B-A, both are included as possibilities);
- an object can be chosen more than once (A-A possible).
This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.
Permutations without repetitions
When the order matters and each object can be chosen only once, then the number of permutations is \(n\times (n-1)\times (n-2) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!}\), where n is the number of objects from which you can choose, r is the number to be chosen and \(k! = 1\times 2\times 3 \times \cdots \times k\) is the factorial notation. For example, if we have 5 people and we choose 3 out of the 5, we have 5!/(5 − 3)! = 60 permutations.
- If n = r (meaning the number of chosen elements is equal to the number of elements to choose from; we pick all 5 people) then the number of permutation becomes \(\frac{n!}{(n-n)!} = \frac{n!}{0!} = n!\), with 0! = 1 (by definition).
- If we have 5 people and want to arrange them all, the number of possible arrangements (permutations) will be 5! or 5 × 4 × 3 × 2 × 1 = 120 ways. The reason for this is that you can choose from 5 for the initial slot, then you are left with only 4 to choose from for the second slot etc. Multiplying them together gives the total of 120.
Combinations
An ordered collection of objects is a permutation. A combination is an un-ordered collection of unique objects. Given S, the set of all possible unique elements, a combination is a subset of the elements of S. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears uniquely once); i.e., we sample without replacement/repetition. Combinations are defined by the elements contained in them, thus the set {1,1,2} is the same as {2,1,1}. For example, from a 52-card deck any 5 cards can form a valid combination (a hand). The order of the cards doesn't matter and there can be no repetition of cards.
Combinations without repetitions
When the order does not matter and each object can be chosen only once, the number of combinations is the binomial coefficient\[{n\choose k} = {{n!} \over {k!(n - k)!}}\], where n is the number of objects from which you can choose and k is the number of chosen objects. For example, if you have ten numbers and wish to choose 5 you would have 10!/(5!(10 − 5)!) = 252 ways to choose. The binomial coefficient is also used to calculate the number of permutations in a lottery, as the order of the lottary numbers is irrelevant.
Combinations with repetitions
When the order does not matter and an object can be chosen more than once, then the number of combinations is \({{(n + k - 1)!} \over {k!(n - 1)!}} = {{n + k - 1} \choose {k}} = {{n + k - 1} \choose {n - 1}}\), where n is the number of objects from which you can choose and k is the number to be chosen. For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose.
References
- SOCR Home page: http://www.socr.ucla.edu
Translate this page:
