Definition 1.1.
A partition of a finite set \(A\) is a collection of disjoint nonempty sets \(A_1,\dots, A_k\) whose union is \(A\text{:}\)
\begin{equation*}
A=\cup_{i=1}^k A_i.
\end{equation*}
Section 1.1 Basic Counting Principles
In this course we will focus on combinatorial reasoning and arguments. Often we are interested in the number of elements in a particular set. Enumeration techniques allow us to count efficiently, rather than simply listing out the elements and counting them brute-force. Today we will start by reviewing basic counting principles.
Theorem 1.2. Sum Principle (Counting by cases).
If \(A\) is a finite set, and \(A\) is partitioned into sets \(B_1,\dots,B_k\) then
\begin{equation*}
\left|{A}\right|=\sum_{i=1}^k\left|{B_i}\right|.
\end{equation*}
Theorem 1.3. roduct Principle (Counting by stages).
If elements of \(A\) are formed by a series of \(k\) choices where there are \(n_i\) options for the \(i^{\text{th}}\) choice, regardless of previous choices made, then
\begin{equation*}
\left|{A}\right|=\prod_{i=1}^k n_i.
\end{equation*}
Remark 1.4.
The particular options available at the \(i^{\text{th}}\) choice may depend on previous choices, but the number of options is the same at that step
Example 1.5.
- Cartesian product \(A \times B=\{(a,b)\,:\, a\in A, b\in B\}\)\begin{equation*} \left|{A\times B}\right|=\left|{A}\right|\cdot\left|{B}\right|. \end{equation*}There are \(\left|{A}\right|\) ways to select “\(a\)” and for each choice there are \(\left|{B}\right|\) ways to select “\(b\text{.}\)”
-
A pair of distinguishable dice (say red and blue) is rolled. Let \(S\) be the set of possible outcomes that have the same parity. Find \(|S|\text{.}\) Denote an outcome by \((r,b)\) where \(r\) is the number of red die, \(b\) is the number of blue die.\begin{equation*} \begin{aligned} \left|{S}\right| &= \text{(number of ways } r,b\text{ both even)} + \text{(number of ways } r,b\text{ both odd)}\\ &=3\cdot 3+ 3\cdot 3\\ &=18 \end{aligned} \end{equation*}Above uses sum principle then product principle for each term.Could also use product principle directly:\begin{equation*} \left|{S}\right|=6\cdot 3=18 \end{equation*}since 6 ways to have “\(r\text{,}\)” once \(r\) chosen parity determined and 3 ways to select “\(b\text{.}\)”
A simple but powerful tool is counting two ways. We can prove identities or show that two formulas are equal if we can show that each one counts the size of the same set. Usually the hard part is determining which set each side is counting.
Fact 1.6. Counting Two Ways.
When two formulas count the same set, their values are equal.
Example 1.7.
By counting two ways, show that
\begin{equation*}
\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}.
\end{equation*}
Let \([n]\) denote the set \(\{1,2,3,\ldots, n\}\text{.}\) We will show that each side counts the number of unordered pairs of elements from \([n]\text{.}\)
Solution.
RHS counts using product principle: there are \(n\) choices fro the first element in the pair, and then \(n-1\) choices for the second element. Since we chose elements in order and want an unordered pair, we must divide by 2 to undo overcounting.
LHS counts using sum principle: Partition the pairs according to the largest element in the pair. If \(i+1\) is largest, there are \(i\) choices for the other element.
As a counting technique, we can compute the size of a set \(A\) by establishing a bijection from \(A\) to a set \(B\) whose size is known. Recall that a function \(f: A \rightarrow B\) is a bijection if for every \(b\in B\) there is exactly one \(x\in A\) such that \(f(x)=b\text{.}\)
Theorem 1.8. Bijection Principle.
If there is a bijection from one set to another, then the two sets have the same size.
Example 1.9.
Show that the number of \(0,1\)-lists of length \(n\) equals the number of subsets of \([n]\text{.}\)
Solution.
Define \(f:A\rightarrow B\) as follows:
- Let \(S\in A\) so \(S\) is a subset of \([n]\text{.}\)
-
\(f(S)=s_1s_2\cdots s_n\) where \(s_i=1\) if \(i\in S,s_i=0\) if \(s_i\notin S\) (so \(f(s)\) is theincidence vector of \(S\)).
- Now, given any list \(b_1\cdots b_n\in B\text{,}\) it is the image of the set \(\{i\,:\, b_i=1\}\text{.}\) Any two lists that are identical are from the same set.
So the map \(f\) is a bijection.
Remark 1.10.
Also note \(\left|{A}\right|=\left|{B}\right|=2^n\) (by product principle).
Often the bijection principle or counting two ways is used in a combinatorial proof. The next principle is also a useful tool in many arguments. The idea is that in any set of numbers, there is an element that is at least as large as the average.
Theorem 1.11. Pigeonhole Principle.
If more than \(kn\) objects are placed in \(k\) boxes, then there is some box that contains more than \(n\) objects.
Proof.
Suppose not. If there are at most \(n\) objects per box, then there at most \(kn\) objects.
The Pigeonhole Principle generalizes as follows to classes that have quotas. Let \(p_i\) denote the quota for items in class \(i\text{.}\)
Theorem 1.12. Pigeonhole Principle Generalized.
If \((\sum_{i=1}^kp_i)-k+1\) objects are partitioned into \(k\) classes, with quotas \(\{p_i\}\text{,}\) then some class meets its quota.
Proof.
If not, there are at most \((\sum_{i=1}^kp_i-1)\) objects placed.
Example 1.13.
Show that within any set of at least two people, there are always two people who have the same number of acquaintances.
Solution.
Let \(n\) be the number of people. Assume acquaintance relation is symmetric. The possible number of acquaintances any person can have is in \(\{0,\dots,n-1\}\text{,}\) which has \(n\) elements. Observe that not both of \(0\) and \(n-1\) may be used simultaneously within the same set of people. Thus, there are \(n\) people and \(n-1\) choices of acquaintance numbers (either \(\{0,\dots,n-2\}\) or \(\{1,\dots,n-1\}\)). So by PP, some two people have the same number.
