Section 9.4 Ordered samples
With some basic counting principles now in our repertoire, we may count the number of samples taken from a universe where the order of the objects in the sample matters. These samples may allow objects to be repeated or they may not.
Example 9.4.1.
A 6-digit PIN (personal identification number) is to be made from the digits 0-9. How many PINs are possible?
Observe that we are sampling from the universe \(\{0,1,2,3,4,5,6,7,8,9\}\text{.}\) Such a sample consists of six objects in order. Because \(111111\) is a possible, albeit unwise, passcode the objects may be repeated.
We may use the multiplication principle. We must choose one of 10 digits. Then, we must choose another of ten digits. Then another, etc., until we have chosen six numbers. The multiplication principle says there are
possible PINs.
Let us generalize. We would like to sample \(r\) objects from a universe \(\Omega\) where \(|\Omega|=n\text{.}\) The samples are ordered and objects may be repeated. How many samples are possible?
You may just say \(n^r\) because of the above example, and you'd be right. Let's make sure we understand why, though. We must choose \(r\) objects, and at each step we have \(n\) objects to choose from. The multiplication principle says there are
possible samples.
Theorem 9.4.2. Ordered samples with replacement.
The number of ordered samples with replacement of size \(r\) from a universe of size \(n\) is \(n^r\text{.}\)Some types of samples, like ordered samples with replacement, come with a convenient “prototypical object” that they count. This is not a rigorously defined concept, but we will consider a “prototype” counted by a counting formula to be a contextless mathematical object that is easy to compare counting problems in a variety of contexts to. In other words, suppose we are trying to count some kind of sample but we aren't sure how. However, we do notice that for each of our mysterious objects, there is exactly one prototype and vice-versa. Then, by the correspondence principle there are as many of the unknown object as there are of the prototype object.
Example 9.4.3.
The prototype object for ordered samples with replacement is a finite sequence of length \(r\) from a universe \(\Omega\) with size \(n\text{.}\) For each of the \(r\) places in the sequence you must choose one of \(n\) objects, so, there are \(n^r\) such finite sequences.
To relate this to the prior example, a passcode of length 6 is a finite sequence of length 6 from the universe \(\{0,1,2,3,4,5,6,7,8,9\}\text{,}\) eg. \(128976 = (1,2,8,9,7,6)\text{.}\) Thus there exactly the same number of each object.
Example 9.4.4.
Let the set \(A\) have \(a\) elements and the set \(B\) have \(b\) elements. How many functions are there from \(A\) to \(B\text{?}\)
Recall that a function assigns every element of \(A\) exactly one partner in \(B\text{.}\) Suppose \(A=\{1,2,3\}\) and \(B=\{a,b,c,d\}\text{,}\) and that \(f(1)=b\text{,}\) \(f(2)=c\text{,}\) and \(f(3)=c\text{.}\) Observe that this function may be identified with the sequence \((b,c,c)\text{.}\) In fact, any function between finite sets can be identified with a finite sequence by ordering the elements of the domain and then writing down the output elements in that order!
Therefore, the number of functions between \(A\) and \(B\) is the same as the number of sequences of length \(|A|\) whose entries are in \(B\text{,}\) i.e., \(b^a\text{.}\)
We now turn our attention to ordered samples without replacement.
Example 9.4.5.
Suppose too many people use \(111111\) as their passcode, and the manufacturer of the phone makes it so that passcodes can no longer allow repeated characters. How many 6-digit passcodes from \(\{0,1,2,3,4,5,6,7,8,9\}\) are allowed now?
For the first character of the passcode, we are allowed to choose any of the ten digits. However, once we have chosen a digit is no longer allowed to be used; therefore there are nine choices for the next digit.
Does this invalidate the multiplication principle? No. The multiplication principle says that the first choice must not affect the number of options for the second choice. Regardless of which first digit we choose, there are still nine possibilities for the next digit.
Then we may choose eight digits, etc., so the total number of passcodes is
Hopefully this process, of multiplying successively smaller integers, reminds you of something.
There is another way to solve this problem. At first it will seem unpleasant, but it will provide some very useful insight. Let's make a 6-digit passcode with no repetitions. We can do so by shuffling the ten allowable digits, for example:
We only want the first six digits to be in our passcode, so let's draw a divider.
Only the order of the first six digits is relevant. For example, this would give us the same passcode as the shuffle
Therefore, the number of six-digit passcodes with no repetitions is the same as the number of ways to shuffle the universe of digits divided by the number of ways to shuffle the unused digits.
Why is this useful? Well, it turns out we can express the number of ways to shuffle a set of \(n\) objects as a convenient formula that works well with division. Returning to our ten digits, the number of ways to shuffle all of them is
We have seen this number before! Recall that \(n\) factorial is
Therefore, the number of ways to shuffle 10 objects is \(10!\text{.}\) Similarly, the number of ways to shuffle the unused digits is
And sure enough, by cancelling the 4, 3, 2, and 1, we see that
Okay--why go all the trouble to set that up? Well, to start, we now have a simple formula for calculating these sorts of samples (called permutations). Additionally, the insight that we can take samples by shuffling the entire universe and dividing it into two pieces (which themselves may or may not be shuffled) is a useful one.
Theorem 9.4.6. Ordered samples without replacement.
The number of ordered samples without replacement of size \(r\) from a universe of size \(n\) is \(n!/(n-r)!\text{.}\) This number, denoted \(P(n,r)\) (“\(n\) permute \(r\)”), is sometimes called the number of \(r\)-permutations of a set of \(n\) elements.The number of \(n\)-permutations of a set of \(n\) elements had better be \(n!\text{,}\) right? Sure enough:
Corollary 9.4.7.
\(P(n,n)=n!\)There is not really a convenient prototype object for ordered samples without replacement. Oh well.
Example 9.4.8.
Some organizers are planning a contest with fifteen participants. They have not decided how many people will win awards yet; regardless, awards will be different depending on position. How many ways can the organizers award at most three awards? (They will not give zero awards.)
The key here is to observe that “at most three” (and not zero) means “one, two, or three.” So this is an “or” type event. The events are disjoint, meaning they have empty intersections, because it is not possible to award both exactly two awards and exactly three awards.
If \(k\) awards are given, then we are chosing \(k\) participants in order from the 15 contestants. So the formula for the number of ways to dole out \(k\) awards is
For instance, suppose the organizers choose to award \(k=2\) participants. Then, there will be
ways to allocate the two awards.
The number \(k\) may take on the values 1, 2, or 3. Adding each number of possibilities together gives us
possible ways to give at most three awards.