Skip to main content

Section 3.2 General Counting Principles

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{.}\)

In order to "count without counting" we establish the following foundational principle:

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{gather*} \left \{ (k,j): 1 \le k \le |A|, 1 \le j \le |B| \right \} \end{gather*}

onto

\begin{gather*} \left \{ s : 1 \le s \le |A| |B| \right \}. \end{gather*}

Since this second set has |A| |B| elements then the conclusion follows. coordinates.

Let's apply the Multiplication Principle.

Definition 3.2.5 Factorial

For any natural number n,

\begin{gather*} n! = n(n-1)(n-2) ... 3 \cdot 2 \cdot 1 \end{gather*}

and by convention set 0! = 1.

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?

  1. Does the order in which the digits are entered matter?
  2. 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.

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\)

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?