Proposition 1.1. Addition Principle.
Let \(A,B\) be disjoint finite sets. We have
\begin{equation}
|A\cup B| = |A| + |B|.\tag{1.1}
\end{equation}
Section 1 Sets and Counting
Counting refers to a set of techniques for determining relationships between the sizes of sets. Formally, we say that sets \(S,T\) have the same size, or cardinality, if there exists a one-to-one correspondence \(S\leftrightarrow T\text{.}\) We write \(|S|\) to denote the number of elements in a finite set \(S\text{.}\)
Subsection 1.1 Addition Principle(s)
Recall that two sets are disjoint if their intersection is empty. The most basic counting principle is the following.
A collection of sets is called pairwise disjoint if every pair of distinct sets in the collection is disjoint. Recall that a partition of a set \(S\) is a collection of pairwise disjoint nonempty subsets of \(S\) whose union is all of \(S\text{.}\) Partitions are a natural context for the following generalization of the Addition Principle.
Proposition 1.2. Addition Principle for Partitions.
Let \(S\) be a finite set, and let \(\mathcal{A}\) be a partition of \(S\text{.}\) We have
\begin{equation}
|S| = \sum_{A\in \mathcal{A}} |A|.\tag{1.2}
\end{equation}
Subsection 1.2 Multiplication Principle(s)
Multiplication principles are based on the following bit of common sense. Suppose your job is to count the chairs in a large dining room. Suppose you see right away that the chairs are set around tables, and each table has \(m\) chairs. Do you now count all the chairs individually? Of course not. You count the tables: let’s say there are \(n\) of them. Now you know the number of chairs is \(mn\text{,}\) without having counted the chairs one by one. Here is the mathematical version of this idea.
Proposition 1.4. Multiplication Principle for Partitions.
Suppose a finite set \(S\) is partitioned into \(n\) subsets, each of which has the same size \(m\text{.}\) Then
\begin{equation*}
|S|=mn.
\end{equation*}
Checkpoint 1.5.
Use the addition principle for partitions to prove the multiplication rule for partitions.
Proposition 1.4 provides a way to count the elements in a set using a sequence of decisions, or choices. If a set \(S\) is partitioned into subsets of equal size, we can choose an element of \(S\) as follows.
-
First, choose one of the partition subsets.
-
Second, choose an element from that subset.
Since there are \(n\) ways to make the first choice, and then, having made the first choice, there are \(m\) ways to make the second choice, then we conclude that \(|S|=mn\text{.}\) This thinking generalizes to longer choice sequences, as follows.
Proposition 1.6. Multiplication Principle for a Sequence of Decisions.
Suppose that every element of a finite set \(S\) is uniquely specified by a sequence of \(t\) choices, such that there are \(m_1\) ways to make the first choice; then, having made the first choice, there are \(m_2\) ways to make the second choice (no matter how the first choice was made); and so on; finally, having made the \((t-1)\)-st choice, there are \(m_t\) ways to make the \(t\)-th choice (no matter how the previous choices were made). Then we have
\begin{equation}
|S|=m_1m_2\cdots m_t.\tag{1.3}
\end{equation}
Checkpoint 1.7.
Use the multiplication principle to show that \(|S\times T| = |S|\cdot |T|\) for finite sets \(S,T\text{.}\)
As an application of the Multiplication Principle, we count the number of orderings of a finite set. Recall that a bijection is a function that is one-to-one and onto. An ordering or permutation of a finite set \(A\) of size \(|A|=n\) is given by a bijection \(f\colon \{1,2,\ldots,n\}\to A\text{.}\) We say the first element of \(A\) is \(f(1)\text{,}\) the second element is \(f(2)\text{,}\) and so on. We can specify an ordering of \(A\) by making the following sequence of choices.
-
First, choose a value for \(f(1)\text{.}\) There are \(n\) ways to make this choice.
-
Second, choose a value for \(f(2)\text{.}\) There are \(n-1\) ways to make this choice from the elements in \(A\) that were not chosen in step 1.
-
And so on, for \(f(3),f(4),\ldots,f(n-1),f(n)\text{,}\) for which there are \(n-2,n-3,\ldots,2,1\) ways to make each of these choices, repsectively.
From this sequence of \(n\) choices, we conclude that the number of orderings of \(A\) is \(n!= n(n-1)(n-2)\ldots 3\cdot 2\cdot
1\text{.}\) We record this result as a proposition.
Proposition 1.8. Permutations of a finite set.
Let \(A\) be a finite set. The number of permutations (or orderings) of the elements of \(A\) is \(|A|!\text{.}\)
Subsection 1.3 Sequences and Permutations
Let \(S\) be a set. A function \(f\colon \{1,2,\ldots,r\}\to
S\) is called a sequence in \(S\) of length \(r\text{.}\) A sequence is denoted by an ordered list \((s_1,s_2,\ldots,s_r)\) of elements in \(S\text{,}\) where \(s_k=f(k)\) for \(1\leq k\leq r\text{.}\) The set of all possible sequences in \(S\) of length \(r\) is denoted \(S^r\text{,}\) and is also called the \(r\)-fold Cartesian product of \(S\) with itself.
\begin{equation}
S^r = \underbrace{S\times S \times \cdots \times S}_{r \text{
factors}}=\{(s_1,s_2,\ldots,s_r)\colon s_k\in S\text{ for } 1\leq
k\leq r\}\tag{1.4}
\end{equation}
Elements of \(S^r\) are also called ordered \(r\)-tuples. It is convenient to have a name for the subset of sequences \(f\colon \{1,2,\ldots,r\}\to
S\) that are one-to-one, which is the same as the set of \(n\)-tuples \((s_1,s_2,\ldots,s_r)\) that have no repeated values, that is, for which \(s_i\neq s_j\) for \(i\neq j\text{.}\) These sequences are called permutations of \(r\) elements of \(S\). We write \(P_r(S)\) to denote the set of sequences of length \(r\) in \(S\) that are one-to-one (the letter \(P\) is for permutations).
\begin{equation}
P_r(S) =\{(s_1,s_2,\ldots,s_r)\in S^r\colon s_i\neq
s_j\text{ for }i\neq j\}\tag{1.5}
\end{equation}
Checkpoint 1.9.
Let \(S=\{x,y\}\text{.}\)
-
Write out the elements of the set \(S^3\text{.}\)
-
Write out the elements of the set \(P_2(S)\text{.}\)
-
Write out the elements of the set \(P_3(S)\text{.}\)
-
Write out the elements of the set \(\mathcal{P}(S)\text{.}\)
-
Write out the elements of the set \(\mathcal{P}(P_2(S))\text{.}\)
The following sequence counting formulas come from applications of the Multiplication Principle.
Proposition 1.10. Counting sequences.
Let \(S\) be a finite set. We have the following.
\begin{gather}
|S^r| = |S|^r\tag{1.6}\\
|P_r(S)| = |S|(|S|-1)(|S|-2)\cdots (|S|-r+1)=\frac{|S|!}{(|S|-r)!}\tag{1.7}
\end{gather}
The standard notation for the number of permutations of \(r\) elements from a set of size \(n\) is \(P(n,r)\text{.}\) The number \(P(n,r)\) is also called the number of permutations of \(n\) items chosen \(r\) at a time. In this notation, the formulas in Proposition 1.8 and Equation (1.7), respectively, have the following forms.
\begin{align}
P(n,n) \amp = n!\tag{1.8}\\
P(n,r)\amp = n(n-1)(n-2)\cdots (n-r+1)=\frac{n!}{(n-r)!}\tag{1.9}
\end{align}
Subsection 1.4 Subsets and Combinations
Let \(S\) be a finite set, and let \(r\) be an integer in the range \(0\leq r\leq |S|\text{.}\) We will write \(C_r(S)\) to denote the set of all subsets of \(S\) of size \(r\text{.}\) The sets \(C_r(S)\) and \(P_r(S)\) are related: An element of \(P_r(S)\) is specified by the following sequence of decisions.
-
First, choose an element \(A\) of \(C_r(S)\text{.}\)
-
Second, choose an ordering of \(A\text{.}\)
The sequence-of-choices version of the multiplication principle applies, and we have
\begin{equation}
|C_r(S)| \cdot r! = |P_r(S)|.\tag{1.10}
\end{equation}
Putting this together with results in the previous subsections, we have the following.
\begin{equation}
|C_r(S)| =\frac{|S|!}{r! \;(|S|-r)!}.\tag{1.11}
\end{equation}
The number of subsets of size \(r\) in a set of size \(n\) is denoted \(C(n,r)\text{,}\) and is also called the number of combinations of \(n\) items chosen \(r\) at a time. The usual mathematical notation for the \(C(n,r)\) is \({n \choose r}\text{.}\) Using this notation, (1.10) and (1.11), respectively, have the following forms.
\begin{align}
C(n,r) \cdot P(r,r) \amp = P(n,r)\tag{1.12}\\
C(n,r) \amp = {n\choose r} =
\frac{n!}{r!(n-r)!}\tag{1.13}
\end{align}
Checkpoint 1.12.
The binomial formula is the algebraic identity
\begin{equation}
(x+y)^n = \sum_{k=0}^n {n\choose k} x^ky^{n-k}.\tag{1.14}
\end{equation}
Use counting principles to explain why this is true.
Subsection 1.5 Infinite sets and sequences
Recall that a function \(f\colon \{1,2,3,\ldots\}\to S\) from the natural numbers \(\N=\{1,2,3,\ldots\}\) to a set \(S\) is called a sequence in the set \(S\text{.}\) A set \(S\) is called countably infinite if there exists a sequence in \(S\) that is one-to-one and onto. An infinite set \(S\) is called uncountably infinite if \(S\) is not countably infinite.
Checkpoint 1.13.
-
Give an example of a function \(\N\to\N\) that is one-to-one and onto, and that is not the identity function.
-
Give an example of a function \(\N\to\N\) that is one-to-one but not onto.
-
Give an example of a function \(\N\to\N\) that is onto but not one-to-one.
-
Give an example of a function \(\N\to\N\) that is neither one-to-one nor onto, and that is not a constant function.
-
Let \(S\) be the set of all sequences in \(\{0,1\}\text{.}\) Suppose that \(f\colon \N\to S\) is one-to-one and onto. Define an element \(s\) of \(S\) by\begin{equation*} s(n)=\begin{cases} 0 \amp \text{ if } (f(n))(n)=1\\ 1 \amp \text{ if } (f(n))(n)=0 \end{cases}\text{.} \end{equation*}Is it possible that \(s\) is in the image of \(f\text{?}\) What do you conclude about \(S\text{?}\)
Exercises 1.6 Sets and Counting Exercises
1.
Work the “Sets and Counting” exercise set posted on Canvas.
