# 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)We also saw that the subtraction principles states that if $A$ is a finite set and $B \subset A$ then:

(2)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)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)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)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)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)This can easily be verified since for any $i = 1, 2, ..., m$ we can list the ordered pairs in $C_i$:

(8)In applying the addition principle we see that:

(9)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)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:

## 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)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$.