The Multiplication and Division Principles

Recall from The Addition and Subtraction Principles page that the addition principle states that if $A$ is a finite set partitioned by the sets $A_1, A_2, ..., A_n$ then:

(1)

\begin{align} \quad \lvert A \rvert = \sum_{i=1}^{n} \lvert A_i \rvert \end{align}

We also saw that the subtraction principles states that if $A$ is a finite set and $B \subset A$ then:

(2)

\begin{align} \quad \lvert A \setminus B \rvert = \lvert A \rvert - \lvert B \rvert \end{align}

We are now ready to look at two more basic principles known as the multiplication and division principles.

The Multiplication Principle

Recall that if $A$ and $B$ are sets then the the Cartesian product of these two sets is defined to be the set:

(3)

\begin{align} \quad A \times B = \{ (a, b) : x \in A \: \mathrm{and} \: y \in B \} \end{align}

Furthermore, if $A_1, A_2, ..., A_n$ is a collection of sets then the Cartesian product between all of these sets is this prescribed order is defined to be the set:

(4)

\begin{align} \quad A_1 \times A_2 \times ... \times A_n = \{ (x_1, x_2, ..., x_n) : x_i \in A_i \: \mathrm{for \: each \:} i = 1, 2, ..., n \} \end{align}

Let's now look at the multiplication principle.

Definition (The Multiplication Principle): Let $A$ and $B$ be two finite sets. Then the number of ordered pairs $(x, y)$ where $x \in A$ and $y \in B$ is $\lvert A \times B \rvert$ and $\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$.

It should be noted that the multiplication principle is an extension of the addition principle. For example, let $A$ and $B$ be finite sets where $\lvert A \rvert = m$ and $\lvert B \rvert = n$. Since $\lvert A \rvert = m$ we can order the elements of $A$, say we have:

(5)

\begin{align} \quad A = \{ a_1, a_2, ..., a_m \} \end{align}

Now consider the Cartesian product $\lvert A \times B \rvert$ and partition it into the subsets $C_i$ for $i = 1, 2, ..., m$ defined by:

(6)

\begin{align} \quad C_i = \{ (a_i, y) : y \in B \} \end{align}

Clearly $A \times B = \bigcup_{i=1}^{m} C_i$ and it's not hard to see that for $j \neq k$ we have that $C_j \cap C_k = \emptyset$ for each $j, k = 1, 2, ..., m$, and so the collection of subsets $C_1, C_2, ..., C_m \subseteq A \times B$ form a partition of $A \times B$. Furthermore, for each $i = 1, 2, ..., m$ we have that:

(7)

\begin{align} \quad \lvert C_i \rvert = n \end{align}

This can easily be verified since for any $i = 1, 2, ..., m$ we can list the ordered pairs in $C_i$:

(8)

\begin{align} \quad C_i = \{ (a_i, y_1), (a_i, y_2), ..., (a_i, y_n) \} \end{align}

In applying the addition principle we see that:

(9)

\begin{align} \quad \lvert A \times B \rvert = \sum_{i=1}^{m} \lvert C_i \rvert = m \cdot n = \lvert A \rvert \cdot \lvert B \rvert \end{align}

The multiplication principle also extends to Cartesian products of more than one set. If $A_1, A_2, ..., A_p$ are a collection of finite sets with $\lvert A_i \rvert = m_i$ for each $i = 1, 2, ..., p$ then:

(10)

\begin{align} \quad \lvert A_1 \times A_2 \times ... \times A_p \rvert = m_1 \cdot m_2 \cdot ... \cdot m_p = \prod_{i=1}^{p} m_i \end{align}

We are now ready to look at a theorem that utilizes the multiplication principle.

Theorem 1: Let $A = \{ x_1, x_2, ..., x_m \}$ and $B = \{ y_1, y_2, ..., y_n \}$. Let $\mathcal F$ be the set of all functions $f : A \to B$. Then $\lvert \mathcal F \rvert = n^m$.

• Proof: We want to count the number of ways each $x_i \in A$ for $i \in \{1, 2, ..., m \}$ can be assigned to each $y_j \in B$ for $j \in \{1, 2, ..., n \}$.

• For $x_1 \in A$ we can have that $f(x_1)$ can equal one of the $n$ many $y$'s. For $x_2 \in A$, we also have that $f(x_2)$ can equal one of the $n$ many $y$'s, etc… There are $m$ variables $x$ to choose, each with $n$ possible associations so there are $n^m$ functions $f : A \to B$ in $\mathcal F$, that is, $\mid \mathcal F \mid = n^m$. $\blacksquare$

Theorem 2: Let $A = \{ x_1, x_2, ..., x_m \}$ and $B = \{y_1, y_2, ..., y_n \}$. If $m \leq n$ and $\mathcal F$ is the set of all injective functions $f : A \to B$ then $\lvert \mathcal F \rvert = n \cdot (n - 1) \cdot ... \cdot (n - m + 1)$.

The proof of Theorem 2 requires that you know the definition of an injective function. Very briefly, a function $f : A \to B$ is said to be injective if whenever $x \neq y$ we have that $f(x) \neq f(y)$.

• Proof: Let $m \leq n$. For the variable $x_1$ we can assign $f(x_1)$ to be any of the $n$ many $y$'s. For the variable $x_2$ we can assign $f(x_2)$ to be any of the $n - 1$ many $y$'s that remain. We continue this process. For the final variable $x_n$ we can assign $f(x_n)$ to be any of the $n - m + 1$ of the $y$'s that remain. Therefore the total number of injective functions, i.e., the size of $\mid \mathcal F \mid$ is:

(11)

\begin{align} \quad \mid \mathcal F \mid = n \cdot (n - 1) \cdot ... \cdot (n - m + 1) \quad \blacksquare \end{align}

The Division Principle

Definition (The Division Principle): If $A$ is a finite set that is partitioned into the collection of sets $A_1, A_2, ..., A_m \subset A$ where $\lvert A_j \rvert = \lvert A_k \rvert = n$ for each $j, k = 1, 2, ..., m$ then the number of partitions $m$ is given by the formula $m = \frac{\lvert A \rvert}{n}$.

It should be noted that the division principle applies when the sizes of subsets forming the partition of a finite set $A$ are all equal.

For example, consider the set $A = \{ w, x, y, z \}$ and the partitioning $A_1 = \{ w, x \}$ and $A_2 = \{ y, z \}$ of $A$. In this example, we have that the sizes of $A_1$ and $A_2$ are equal since:

(12)

\begin{align} \quad n = \lvert A_1 \rvert = \lvert A_2 \rvert = 2 \end{align}

The size of $A$, $\lvert A \rvert$ is clearly $4$. Thus by the division principle we must have $m = \frac{\lvert A \rvert}{n} = \frac{4}{2} = 2$ partitions, and clearly we do.

We can often deduce an unknown by applying the division principle. As a simple example, suppose that we have $12$ candies to distribute and we distribute them $4$ to each person. Then how many people have we distributed the candies to? The answer should be fairly simple - $3$.