In this section we will learn four basic counting techniques.

The product rule:
If a procedure consists of \(k\) independent tasks \(T_1,T_2,\ldots,T_k\) and \(T_i\) can be done \(n_i\) ways for \(i=1,2,\ldots,k\), then there are total \(n_1n_2\cdots n_k\) ways to do the procedure.

Remark. The product rule can be rephrased in terms of sets as follows: For \(n\) nonempty finite sets \(S_1,S_2,\ldots,S_n\), \[|S_1\times S_2 \times \cdots \times S_n|=|S_1|\cdot |S_2|\cdots |S_n|. \]

Example. How may different three-letter initials can people have?

Solution. Each of 3 letters can be chosen 26 ways. By the product rule, there are total \(26\cdot 26\cdot 26=17576\) different 3-letter initials.

Example. How many license plates can be made using either 2 or 3 uppercase letters followed by either 2 or 3 digits?

Solution. The total number of places for letters and digits is 6. The first place can be empty or assigned one of 26 uppercase letters. The second and third places can be assigned one of 26 uppercase letters. The fourth and fifth places can be assigned one of 10 digits. The fifth place can be empty or assigned one of 10 digits. By the product rule, there are total \(27\cdot26\cdot 26\cdot 10\cdot 10\cdot 11=20,077,200\) different license plates.

Example. Find the number of possible phone numbers under the North American Numbering Plan: \[NXX-NXX-XXXX\] where \(0\leq X\leq 9\) and \(2\leq N\leq 9\).

Solution. There are 8 choices of numbers for \(N\) and 10 choices of numbers for \(X\). By the product rule, the number of possible NANP numbers is \[8\cdot10\cdot 10\cdot 8\cdot 10\cdot 10\cdot 10\cdot 10\cdot 10\cdot 10=6,400,000,000.\] Example. Let \(S\) be a set. If \(|S|=n\), then \(|\mathcal P(S)|=2^n\).

Solution. Let \(S=\{x_1,x_2,\ldots,x_n\}\). A subset \(T\) of \(S\) corresponds to bit string \((a_1,a_2,\ldots,a_n)\) such that \(a_i=1\) when \(x_i\in T\) and \(a_i=0\) when \(x_i\notin T\). For example, \((0,1,1,0,\ldots,0)\) corresponds to \(\{x_2,x_3\}\). Because of this one-to-one correspondence between subsets of \(S\) and bit strings of length \(n\), \[\begin{eqnarray*} |\mathcal P(S)|&=&|\{(a_1,a_2,\ldots,a_n)\;|\;a_i\in \{0,1\}\}|\\ &=&|\{0,1\}\times \{0,1\} \times\cdots\times \{0,1\}|\\ &=&|\{0,1\}|^n \; (\text{by the product rule})\\ &=&2^n. \end{eqnarray*}\]

The sum rule:
If a task can be done in \(n_1\) ways or \(n_2\) ways where each of \(n_1\) ways is different from each of \(n_2\) ways, then there are total \(n_1+n_2\) ways to do the task.

Remark. The sum rule can be rephrased in terms of sets as follows: For two disjoint finite sets \(S_1\) and \(S_2\), \[|S_1\cup S_2|=|S_1|+|S_2|.\] More generally, if \(S_1,S_2,\ldots, S_n\) are pairwise disjoint finite sets (i.e., \(S_i\cap S_j\neq \varnothing\) for \(i\neq j\)), then \[|S_1\cup S_2\cup\ldots\cup S_n|=|S_1|+|S_2|+\cdots+|S_n|.\] Example. Suppose that a password must have at least 8 but not more than 10 characters where each character is either a lowercase letter, an uppercase letter, a digit or one of 5 characters \(!,@,\#,\&,*\). Find the number of possible passwords.

Solution. By the sum rule, the number of ways of choosing a character is \[26+26+10+5=67.\] By the product rule, the number of 8-character passwords is \(67^8\). Similarly the numbers of 9-character and 10-character passwords are \(67^9\) and \(67^{10}\) respectively. By the sum rule, the number of possible passwords is \[67^8+67^9+67^{10}=1,850,450,406,625,613,037.\]

The subtraction rule or the principle of inclusion-exclusion:
If a task can be done in \(n_1\) ways or \(n_2\) ways, then the ways to do the task is \(n_1+n_2\) minus the number of common ways to do the task.

Remark. The sum rule can be rephrased in terms of sets as follows: For two finite sets \(S_1\) and \(S_2\), \[|S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2|.\] More generally, if \(S_1,S_2,\ldots, S_n\) are finite sets, then \[\left|\bigcup_{i=1}^n S_i\right| = \sum_{i=1}^n |S_i| - \sum_{1 \leqslant i < j \leqslant n} |S_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |S_i \cap S_j\cap S_k| - \cdots + (-1)^{n-1} \left|S_1\cap\cdots\cap S_n\right|.\] Example. Find the number of positive integers less than 1,000 that are divisible by 6 or 9.

Solution. Let \[A=\{x\in \mathbb Z^+\;|\; x\leq 999 \text{ and } x \text{ is divisible by } 6\} \text{ and}\] \[B=\{x\in \mathbb Z^+\;|\; x\leq 999 \text{ and } x \text{ is divisible by } 9\}.\] Then the answer is \(|A\cup B|=|A|+|B|-|A\cap B|\). If \(x\in A\), then \(x=6d\) for some integer \(d\) such that \(0 < 6d \leq 999\), i.e., \(0 < d \leq \frac{999}{6}\). So the largest possible \(d\) is \(\lfloor \frac{999}{6} \rfloor\) and consequently \[|A|=\left\lfloor \frac{999}{6} \right\rfloor=166.\] Similarly \(|B|=\left\lfloor \frac{999}{9} \right\rfloor=111\). Now \[\begin{eqnarray*} A\cap B &=& \{x\in \mathbb Z^+\;|\; x\leq 999 \text{ and } x \text{ is divisible by } 6 \text{ and } 9\}\\ &=& \{x\in \mathbb Z^+\;|\; x\leq 999 \text{ and } x \text{ is divisible by } \operatorname{lcm}(6,9)=18\}. \end{eqnarray*}\] Then \(|A\cap B|=\left\lfloor \frac{999}{18} \right\rfloor=55\). Thus the answer is \[|A\cup B|=|A|+|B|-|A\cap B|=166+111-55=222.\]

The division rule:
There are \(\frac{n}{d}\) ways to do a task if it can be done using a procedure that can be carried out in \(n\) ways (not distinct) and for each way \(w\), exactly \(d\) of the \(n\) ways correspond to the way \(w\).

Remark. The division rule is about ignoring "unimportant" differences when counting things. It can be rephrased in terms of sets as follows: If a finite set \(S\) is the union of some pairwise disjoint subsets of \(S\) each with \(d\) elements, then the number of such subsets is \(\frac{|S|}{d}\).

Example. How many different ways can four people seat around a circular table where two seatings are the same when each person has the same left and right neighbors?

Solution. There are \(4\cdot 3\cdot 2\cdot 1=4!\) ways two seat four people by the product rule. For each of \(4!\) seatings, there are exactly \(4\) seatings correspond to the same seating arrangement (in which each person has the same left and right neighbors). Thus by the division rule, the number of different seating arrangements is \[\frac{4!}{4}=6.\]

Last edited