Suppose that \(S\) is a finite set. If \(A \subseteq S\) then the cardinality of \(A\) is the number of elements in \(A\), and is denoted \(\#(A)\). The function \(\#\) on \(\mathscr{P}(S)\) is called counting measure. Counting measure plays a fundamental role in discrete probability structures, and particularly those that involve sampling from a finite set. The set \(S\) is typically very large, hence efficient counting methods are essential. The first combinatorial problem is attributed to the Greek mathematician Xenocrates.
In many cases, a set of objects can be counted by establishing a one-to-one correspondence between the given set and some other set. Naturally, the two sets have the same number of elements, but for some reason, the second set may be easier to count.
The addition rule of combinatorics is simply the additivity axiom of counting measure. If \(\{A_1, S_2, \ldots, A_n\}\) is a collection of disjoint subsets of \(S\) then
\[ \#\left( \bigcup_{i=1}^n A_i \right) = \sum_{i=1}^n \#(A_i) \]
The counting rules in this subsection are simple consequences of the addition rule.
\(\#(A^c) = \#(S) - \#(A)\). This is the complement rule.
\(A\) and \(A^c\) are disjoint and their union is \(S\).
\(\#(B \setminus A) = \#(B) - \#(A \cap B)\). This is the difference rule.
\(A \cap B\) and \(B \setminus A\) are disjoint and their union is \(B\).
If \(A \subseteq B\) then \(\#(B \setminus A) = \#(B) - \#(A)\).
Apply the difference rule and note that \(A \cap B = A\).
If \(A \subseteq B\) then \(\#(A) \le \#(B)\).
Use the result of the last exercise, and note that \(\#(B \setminus A) \ge 0\)
Thus, \(\#\) is an increasing function, relative to the subset partial order \(\subseteq\) on \(\mathscr{P}(S)\), and the ordinary order \(\le\) on \(\N\).
This subsection gives two inequalities that are useful for obtaining bounds on the number of elements in a set. The first is Boole's inequality (named after George Boole) which gives an upper bound on the cardinality of a union.
If \(\{A_1, A_2, \ldots, A_n\}\) is a a finite collection of subsets of \(S\) then
\[ \#\left( \bigcup_{i=1}^n A_i \right) \le \sum_{i=1}^n \#(A_i) \]Define \(B_1 = A_1\) and \(B_i = A_i \setminus (A_1 \cup \cdots A_{i-1})\) for \(i \in \{2, 3, \ldots, n\}\). Note that \(\{B_1, B_2, \ldots, B_n\}\) is a pairwise disjoint collection and has the same union as \(\{A_1, A_2, \ldots, A_n\}\). Now use the addition rule and the increasing property.
Intuitively, Boole's inequality holds because parts of the union have been counted more than once in the expression on the right.
The second inequality is Bonferroni's inequality (named after Carlo Bonferroni), which gives a lower bound on the cardinality of an intersection.
If \(\{A_1, A_2, \ldots, A_n\}\) is a finite collection of subsets of \(S\) then
\[ \#\left( \bigcap_{i=1}^n A_i \right) \ge \#(S) - \sum_{i=1}^n [\#(S) - \#(A_i)] \]Apply Boole's inequality to \(\{A_1^c, A_2^c, \ldots, A_n^c\}\) and use DeMorgan's law.
The inclusion-exclusion formula gives the cardinality of a union of sets in terms of the cardinality of the various intersections of the sets. The formula is useful because intersections are often easier to count. We start with the special cases of two sets and three sets. As usual, we assume that the sets are subsets of a finite universal set \( S \).
If \( A \) and \( B \) are subsets of \( S \) then \(\#(A \cup B) = \#(A) + \#(B) - \#(A \cap B)\).
Note first that \(A \cup B = A \cup (B \setminus A)\) and the latter two sets are disjoint. Now use the addition rule and the difference rule.
If \( A \), \( B \), \( C \) are subsets of \( S \) then \(\#(A \cup B \cup C) = \#(A) + \#(B) + \#(C) - \#(A \cap B) - \#(A \cap C) - \#(B \cap C) + \#(A \cap B \cap C)\).
Use the inclusion-exclusion rule for two sets. You will use this rule three times.
Exercise 7 and Exercise 8 can be generalized to a union of \(n\) sets; the generalization is known as the inclusion-exclusion formula.
Suppose that \(\{A_i: i \in I\}\) is a collection of subsets of \(S\) where \(I\) is an index set with \(\#(I) = n\). Then
\[ \# \left( \bigcup_{i \in I} A_i \right) = \sum_{k = 1}^n (-1)^{k - 1} \sum_{J \subseteq I, \; \#(J) = k} \# \left( \bigcap_{j \in J} A_j \right) \]Use induction on \(n\) and the result for two sets.
The general Bonferroni inequalities, named again for Carlo Bonferroni, state that if sum on the right is truncated after \(k\) terms (\(k \lt n\)), then the truncated sum is an upper bound for the cardinality of the union if \(k\) is odd (so that the last term has a positive sign) and is a lower bound for the cardinality of the union if \(k\) is even (so that the last terms has a negative sign).
The multiplication rule of combinatorics is based on the formulation of a procedure (or algorithm) that generates the objects to be counted. Specifically, suppose that the procedure consists of \(k\) steps, performed sequentially, and that for each \(j\), step \(j\) can be performed in \(n_j\) ways regardless of the choices made on the previous steps. Then the number of ways to perform the entire algorithm (and hence the number of objects) is \(n_1 \, n_2 \, \cdots \, n_k\).
The key to a successful application of the multiplication rule to a counting problem is the clear formulation of an algorithm that generates the objects being counted, so that each object is generated once and only once. That is, we must neither over-count nor under-count.
The first two exercises below give equivalent formulations of the multiplication principle.
Suppose that \(S\) is a set of sequences of length \(k\), and that we denote a generic element of \(S\) by \((x_1, x_2, \ldots, x_n)\). Suppose that for each \(j\), \(x_j\) has \(n_j\) different values, regardless of the values of the previous coordinates. Then \(\#(S) = n_1 \, n_2 \, \cdots \, n_k\)
Suppose that \(T\) is an ordered tree with depth \(k\) and that each vertex at level \(i - 1\) has \(n_i\) children for \(i \in \{1, 2, \ldots, k\}\). Then the number of vertices at level \(k\) is \(n_1 \, n_2 \, \cdots \, n_k\).
If \(S_i\) is a set with \(n_i\) elements for \(i \in \{1, 2, \ldots, k\}\) then
\[ \#(S_1 \times S_2 \times \cdots \times S_k) = n_1 \, n_2 \, \cdots \, n_k \]If \(S\) is a set with \(n\) elements, then \(S^k\) has \(n^k\) elements.
The number of ordered samples of size \(k\) that can be chosen with replacement from a population of \(n\) objects is \(n^k\).
The number of functions from a set \(A\) of \(m\) elements into a set \(B\) of \(n\) elements is \(n^m\).
To construct \(f: A \to B\), there are \(n\) choices for \(f(x)\) for each \(x \in A\).
Recall that the set of functions from a set \(A\) into a set \(B\) (regardless of whether the sets are finite or infinite) is denoted \(B^A\). The result in the previous exercise is motivation for this notation.
Elements of \(\{0, 1\}^n\) are sometimes called bit strings of length \(n\). The number of such strings is \(2^n\).
If \(S\) is a set with \(n\) elements then there are \(2^n\) subsets of \(S\).
To construct \(A \subseteq S\), decide whether \(x \in A\) or \(x \notin A\) for each \(x \in S\).
Suppose that \( \{A_1, A_2, \ldots A_k\} \) is a collection of \(k\) subsets of a set \(S\). There are \(2^{2^k}\) different (in general) sets that can be constructed from the \(k\) given sets, using the operations of union, intersection, and complement. These sets form the algebra generated by the given sets.
First note that there are \(2^k\) pairwise disjoint sets of the form \(B_1 \cap B_2 \cap \cdots \cap B_k\) where \(B_i = A_i\) or \(B_i = A_i^c\) for each \(i\). Next, note that every set that can be constructed from \(\{A_1, A_2, \ldots, A_n\}\) is a union of some (perhaps all, perhaps none) of these intersection sets.
In the Venn diagram applet, observe the diagram of each of the 16 sets that can be constructed from \(A\) and \(B\).
Suppose that \(S\) is a set with \(n\) elements and that \(A\) is a subset of \(S\) with \(k\) elements. The number of subsets of \(S\) that contain \(A\) is \(2^{n - k}\).
A license number consists of two letters (uppercase) followed by five digits. How many different license numbers are there?
Suppose that a Personal Identification Number (PIN) is a four-symbol code word in which each entry is either a letter (uppercase) or a digit. How many PINs are there?
In the board game Clue, Mr. Boddy has been murdered. There are 6 suspects, 6 possible weapons, and 9 possible rooms for the murder.
An experiment consists of rolling a fair die, drawing a card from a standard deck, and tossing a fair coin. How many outcomes are there?
A fair die is rolled 5 times and the sequence of scores recorded. How many outcomes are there?
Suppose that 10 persons are chosen and their birthdays recorded. How many possible outcomes are there?
In the card game Set, each card has 4 properties: number (one, two, or three), shape (diamond, oval, or squiggle), color (red, blue, or green), and shading (solid, open, or stripped). The deck has one card of each (number, shape, color, shading) configuration. A set in the game is defined as a set of three cards which, for each property, the cards are either all the same or all different.
A fair coin is tossed 10 times and the sequence of scores recorded. How many sequences are there?
A string of lights has 20 bulbs, each of which may be good or defective. How many configurations are there?
The die-coin experiment consists of rolling a die and then tossing a coin the number of times shown on the die. The sequence of coin results is recorded.
Run the die-coin experiment 100 times and observe the outcomes.
Suppose that a sandwich at a restaurant consists of bread, meat, cheese, and various toppings. There are 4 different types of bread (select one), 3 different types of meat (select one), 5 different types of cheese (select one), and 10 different toppings (select any). How many sandwiches are there?
Consider a deck of cards as a set \(D\) with 52 elements.
The Galton Board, named after Francis Galton, is a triangular array of pegs. Galton, apparently too modest to name the device after himself, called it a quincunx from the Latin word for five twelfths (go figure). The rows are numbered, from the top down, by \((0, 1, \ldots )\). Row \(n\) has \(n + 1\) pegs that are labeled, from left to right by \((0, 1, \ldots, n)\). Thus, a peg can be uniquely identified by an ordered pair \((n, k)\) where \(n\) is the row number and \(k\) is the peg number in that row.
A ball is dropped onto the top peg \((0, 0)\) of the Galton board. In general, when the ball hits peg \((n, k)\), it either bounces to the left to peg \((n + 1, k)\) or to the right to peg \((n + 1, k + 1)\). The sequence of pegs that the ball hits is a path in the Galton board.
There is a one-to-one correspondence between each pair of the following three collections:
Thus, from the previous exercise, each of these collections has \(2^n\) elements.
Open the Galton board applet.