Definition 3.2.1. Cardinality.
Given a set of elements A, the number of elements in the set is known as its cardinality and is denoted |A|. If the set has an infinite number of elements then we set |A| = \(\infty\text{.}\)
Section 3.2 General Counting Principles
In order to "count without counting" we establish the following foundational principle:
Theorem 3.2.2. Multiplication Principle.
Given two successive events A and B, the number of ways to perform A and then B is |A||B|.
Proof.
If either of the events has infinite cardinality, then it is clear that the number of ways to perform A and then B will also be infinite. So, assume that both |A| and |B| are finite. In order to count the successive events, enumerate the elements in each set
\begin{gather*}
A = \left \{ a_1, a_2, a_3, ... , a_{|A|} \right \}\\
B = \left \{ b_1, b_2, b_3, ... , b_{|B|} \right \}
\end{gather*}
and consider the function f(k,j) = (k-1)|B| + j. This function is one-to-one and onto from the set
\begin{equation*}
\left \{ (k,j): 1 \le k \le |A|, 1 \le j \le |B| \right \}
\end{equation*}
onto
\begin{equation*}
\left \{ s : 1 \le s \le |A| |B| \right \}.
\end{equation*}
Since this second set has |A| |B| elements then the conclusion follows.
Checkpoint 3.2.3. WebWork - Multiplications Principle.
A fair \(6\)-sided die is rolled \(7\) times and the resulting sequence of \(7\) numbers is recorded.
How many different sequences are possible?
How many different sequences consist entirely of even numbers?
How many different sequences are possible if the first, third, and fourth numbers must be the same?
Checkpoint 3.2.4. WebWork - Counting without Counting.
Find how many positive integers with exactly four decimal digits, that is, positive integers between 1000 and 9999 inclusive, have the following properties:
(a) are divisible by 5 and by 7.
(b) have distinct digits.
(c) are divisible by 5 or by 7 (inclusive or).
(d) are divisible by 5.
Definition 3.2.5. Factorial.
For any natural number n,
\begin{equation*}
n! = n(n-1)(n-2) ... 3 \cdot 2 \cdot 1
\end{equation*}
and by convention set 0! = 1.
Example 3.2.6. iPad security code.
Consider your ipad’s security. To unlock the screen suppose you need to enter a four digit pass code. How easy is it to guess this pass code?
Using the standard 10 digit keypad, we first have two questions to consider?
- Does the order in which the digits are entered matter?
- Can you reuse a digit more than once?
For the ipad, if the order does matter and you cannot reuse digits, the number of possible codes can be determined by considering each digit as a separate event with four such events in succession providing the right code. By successively applying the multiplication principle, you find that the number of possible codes is the number of remaining available digits at each step. Namely, \(10 \times 9 \times 8 \times 7 = 5040.\)
On the other hand, if you were allowed to reuse the digits then the number of possible outcomes would be more since all 10 digits would be available for each event. Namely, \(10 \times 10 \times 10 \times 10 = 10000.\)
Now, consider how this changes if you can use a 4 or 6 digit passcode. Determine the number of possible passcodes.
Example 3.2.7. iPad security code with greasy fingers.
Reconsider your ipad’s security. In this case, you like to eat chocolate bars and have greasy fingers. When you type in your passcode your fingers leave a residue over the four numbers pressed. If someone now tries to guess your passcode, how many possible attempts are necessary?
Since there are only four numbers to pick from with order important, the number of possible passcodes remaining is \(4 \times 3 \times 2 \times 1 = 24\)
Example 3.2.8. National Treasure.
In the 2004 movie National Treasure, Ben and Riley are attempting to guess Abagail’s password to enter the room with the Declaration. They are able to determine the passphrase to get into the vault room by doing a scan that detects the buttons pushed (not due to chocolate but just due to the natural oils on fingers). They notice that the buttons pushed include the characters AEFGLORVY.
Assuming these characters are used only once each, how many possible passphrases are possible?
In this case, the order of the characters matters but all of the characters are distinct. Since we have 9 characters provided, the we can consider each character as an event with the first event as a choice from the 9, the second event as a choice from the remaining 8, etc. This gives \(9 \times 8 \times ... \times 1 = 362880\) possible passphrases.
Assuming that some of the characters could be used more than once, how many passphrases need to be considered if the total length of passphrase can be at most 12 characters?
Notice, in this case you don’t know which characters might be reused and so the number of possible outcomes will be much larger. What is the answer?
You can break this problem down into distinct cases:
- Using 9 characters: The answer was computed above.
- Using 10 characters: In this case, 1 character can be used twice. To determine the number of possibilities, let’s first pick which character can be doubled. There are 9 options for picking that character. Next, if we consider the two instances of that letter as distinct values then we can just count the number of ways to arrange unique 10 characters which is 10! However, swapping the two characters (which are actually identical) would not give a new passphrase. Since these are counted twice, let’s divide these out to give 10!/2.
- Using 11 characters: In this situation we have two unique options:
-
One character is used three times and the others just once.Continuing as in the previous case, 11!/3!.Two characters are used twice and the others just once.
-
- Using 12 characters
With this large collection of possible outcomes, how are the movie characters able to determine the correct "VALLEYFORGE" passphrase?
