Basic counting theory introduces students to the idea of the multiplicative principle.
Theorem2.0.1.Multiplicative Principle.
Suppose there are some number \(k\) of finite sets \(A_1, A_2, \dotsc, A_k\) such that for each \(j\in\set{1,2,\dotsc,k}\) the cardinality of \(A_j\) is \(\abs{A_j} = \alpha_j\text{.}\) Let the Cartesian product of the sets \(A_1, A_2, \dotsc, A_k\) be
\begin{equation*}
A_1\times A_2\times \cdots \times A_k = \set{(a_1,a_2,\dotsc,a_k):a_j\in A_j\text{ for each }j\in\set{1,\dotsc,k}}\text{,}
\end{equation*}
which is the set of ordered pairs whose jth coordinate is a member of \(A_j\text{.}\) Then
An immediate application of this is to consider a problem of counting the number of orderings of a finite set: while the choice of a first element alters the possibilities for choosing a second element in the ordering, it does not change the number of such choices. Hence the multiplicative principle can be used to count orderings. This only leaves a fundamental question: what is an ordering of a set?
