411 Mathematical Statistics: Part 1
Table of Contents
1. Methods of Enumeration
1.1. Multiplication Principle
Suppose you have a multistep experiment made up of several trials. The number of possible outcomes for the composite experiment is the product of the number of outcomes for each trial.
The best way to visualize this is to think of a tree diagram, which makes the veracity intuitively clear.
Two options for the first trial * 3 options for the second trial = 6 possible outcomes.
1.2. Permutations
The permutations of n objects is the number of ways to arrange them (for instance, in a row). A good prototype is to think of putting 5 different people in a line.
If you think of this using the multiplication principle, there are 5 trials:
- Trial 1: Select person in 1st spot (5 options)
- Trial 2: Select person in 2nd spot (4 options)
- Trial 3: Select person in 3rd spot (3 options)
- Trial 4: Select person in 4th spot (2 options)
- Trial 5: Select person in 5th spot (1 option)
\(5 * 4 * 3 * 2 * 1 = 5! = 120\)
Note, a permutation is an ordered arrangement. If you have people \(P_1, P_2, P_3\) put in a line, \((P_1, P_2, P_3) \neq (P_3, P_2, P_1)\). I.e. if you're \(P_1\), being first in line is not the same as being last in line.
1.2.1. Generalizing to R positions
In the above example, the number of positions is equal to the number of objects. In general, we can arrange n distinct objects among r slots through the same strategy. I.e. the application of the multiplication principle.
For instance, the above example with r=3 (How many different lines of 3 people can you make from a group of 5?) looks like:
\(5 * 4 * 3 = \frac{5!}{2!} = 60\)
In general the number of permutations of n objects among r positions, \(_nP_r = \frac{n!}{(n-r)!}\)
1.2.2. Illustrative Example (Using "blocks")
You have 11 different books: 5 on Stat, 4 on Calc and 2 on Algebra.
a.) If you want every book of the same type to be next to each other, how many different ways can you arrange these books?
b.) How many ways can you arrange the books if only the Stat books must stay together?
- Solution for part A:
The trick to this problem is to imagine grouping each book of the same subject together to make a block. This gives us three blocks: [Stat], [Calc], [Algebra], of which there are 3! = 6 permutations. Then, within each block, we can arrange the books.
- Num. Permutations of Stat books within Stat block: 5!
- Num. Permutations of Calc books within Calc block: 4!
- Num. Permutations of Algebra books within Algebra block: 2!
\(3! * 5! * 4! * 2! = 34560\)
- Solution for Part B:
Similar to last time, we will consider this as a "block" problem. The Calc and Algebra books, which can be by themselves, can be thought of as "1 book blocks". That is, we now have 7 blocks, 1 representing all the stat books, 4 representing each calc book, and 2 representing each algebra book.
- Num. Permutations of 7 blocks: \(7!\)
- Num. Permutations of Stat books within Stat block: \(5!\)
\(7! * 5! = 604800\)
As you may well expect, the number of permutations is much more than it was in Part A, which was more restrictive. Even this is fairly restrictive though when compared to the total number of permutations of 11 books:
\(11! = 39916800\)
1.3. Combinations
Unlike a permutation, a combination is an unordered set representing the arrangements of \(r\) objects drawn from a set of n objects.
A combination is denoted \(_nC_r\) or \(\binom{n}{r}\), pronounced "n choose r". A prototype for combinations would be being dealt a hand of cards. That is, holding \(\{A, K, Q, J, 10\}\) is equivalent to holding \(\{10, J, Q, K, A\}\).
\(\binom{n}{r}\) = \(\frac{n!}{r!(n-r)!}\), which will be explored in the next example.
1.3.1. Ex. Poker cards + Understanding the derivation
In poker, you are dealt a hand of 5 cards from a deck of 52:
- \(n = 52\)
- \(r = 5\)
To derive the number of combinations, we start with the total number of ordered subsets:
\(\frac{n!}{(n-r)!}\)
Consider a specific ordered subset composed of Ace, King, Queen, Jack, and 10 of spades:
\((A, K, Q, J, 10)\)
As we are only considering the unordered subsets, this set will be considered equivalent to any permutations of it. The permutations of \((A, K, Q, J, 10)\) is the number of ways we can arrange \(r\) elements, or \(r!\).
You can think of this as a sort of tree diagram. The parents here are unordered sets, and the children are permutations of them.
As you can see, for every unordered set there is \(r!\) = \(5!\) ordered sets. We know the number of all ordered sets, so to get back to the number of unordered sets we can just do the multiplication rule in reverse: i.e. divide the total number of ordered sets by \(r!\) = \(5!\).
Therefore:
\(\binom{n}{r}\) = \(\frac{n!}{r!(n-r)!}\)
So the number of poker hands is:
The # Ordered sets / The # of ordered sets per unordered set =
\(\frac{52!}{47!} * \frac{1}{5!} = 2598960\).