General post

Basic classical constructions

Originally posted 2025-03-10

Last updated 2025-03-10

The constructions shown on this page are largely uninteresting or well known, but are widely required prerequisites for analytical techniques, so I wanted to collect them here. I’ve also used this as an opportunity to define some notation that I’ve adopted (where there is not a de facto standard). Whenever sets are referred to, the assumption is that they have a well-defined, discrete size.

Set cardinality

If you have a set $A$, we denote its cardinality by $|A|$. This is a simple count of the number of items in the set (unique by construction). I’m only bothering to call this out because set cardinality is typically the one thing we care about while counting.

Disjoint set (sum) rule

If you have two sets, $A$ and $B$, then the cardinality of their union is $|A \cup B| = |A| + |B|$. This mirrors the disjoint union rule for generating functions in AC (where we always construct the classes to be disjoint).

The more general technique for when the sets are not disjoint is the principle of inclusion/exclusion, described below.

Product rule

Suppose you are counting logical “tuples” of items, $(a_1, a_2, \dots, a_n)$, where each each of the $a_i$ can be “independently” chosen. Independent in this sense means that the choice of some specific object $a_i$ does not impact the set of choices available to $a_j$ where $i \neq j$. Moreover, suppose that each choice $a_i$ must be drawn from some set $A_i$. Then the cardinality of all possible tuples you can form from the respective sets (the Cartesian product) is

$$|A_1 \times A_2 \times \cdots \times A_n| = \prod_{k=1}^n |A_k|$$

As a special case, if $|A_1| = |A_2| = \cdots = |A_n| = |A|$, then you have

$$j |A_1 \times A_2 \times \cdots \times A_n| = |A|^n$$

Permutation rule

Suppose you have some set $A$ where $|A| = n$ and want to count the number of distinct ordered lists you can form from this set where each item appears in the list exactly once. To follow this constraint, you have $n$ choices for the first item in the logical tuple. However, you now have to exclude this from the set of items available at the next position. That is, you are now drawing from $A_2 = A \setminus \{a_1\}$, where $a_1$ is the item you happened to choose in any given path. Clearly, $|A_2| = n - 1$. By similar reasoning, $|A_k| = n - (k-1)$ in general. Then by the product rule, we have

$$|P| = n (n - 1) (n - 2) \cdots 1 = n!,$$

where $P$ denotes the set of permutations of $A$ and $n!$ is pronounced ”$n$ factorial” (or “$n$-bang”).

By convention, $0! = 1$. (How many ways can you distinctly order an empty list?)

The generalization of $n!$ from the non-negative integers to the complex plane is the Gamma function, $\Gamma(z)$.¹ While we’ll be using it heavily for AC, it is by no means elementary, so I won’t discuss it further here.

$k$-permutation (falling factorial) rule

Sometimes you are counting the set of $k$-permutations over $n$ distinct objects, where $0 \leq k \leq n$. By arguments analogous to the above, you have

$$\begin{aligned} |P_k| &= \underbrace{n (n - 1) \cdots (n - (k - 1))}_{k\ \text{factors}} \\ &= \frac{n!}{(n-k)!} \\ &= n^{\underline{k}}, \end{aligned}$$

where $n^{\underline{k}}$ is known as the “falling factorial” and pronounced ”$n$ to the $k$ falling”.² Note that the rational factorial expression follows from the first product and the definition of the factorial; the falling factorial is a definition.

Rising factorial

We adopt the analogous notation for the “rising factorial”:

$$n^{\overline{k}} = \underbrace{n (n + 1) \cdots (n + (k - 1))}_{k\ \text{factors}}$$

This is not used often in “basic” counting but still appears in many places.

$k$-combination rule

Now suppose you want to count the size of $C_k$, the set of “$k$-combinations” drawn from the same set $A$ described in the $k$-permutation rule. However, instead of counting all ordered tuples of items (without replacement), you only want to count tuples by their membership.³ In other words, you do not care about the order of the items within a given $k$-permutation.

Suppose that you have some element $c$ which was drawn from $C_k$. This is itself a $k$-element “set”, since it was constructed from unique elements. You should be able to convince yourself that (by the permutation rule) there are exactly $k!$ permutations corresponding to each possible element $c$. Moreover, since every possible $k$-permutation is counted by $n^{\underline{k}}$, we can produce every $c \in C_k$ by turning a given $k$-permutation into a set. In other words, we have a surjection $P_k \mapsto C_k$ which overrepresents each element in $C_k$ by a factor of $k!$ which gives us $|P_k| = k! |C_k|$. In other words:

$$\begin{aligned} |C_k| &= \frac{|P_k|}{k!} = \frac{n^{\underline{k}}}{k!} = \frac{n!}{(n-k)!k!} \\ &= \binom{n}{k}, \end{aligned}$$

where $\binom{n}{k}$ is called a “binomial coefficient” and is commonly pronounced ”$n$ choose $k$”.

There are many other uses and interesting properties of such binomial coefficients, some of which I will cover in a dedicated post.

Inclusion/exclusion rule (PIE)

I mentioned earlier that the disjoint set rule does not apply in general. The name gives it away: what if your sets overlap? It’s helpful to visualize the possible subsets you end up with (to come: a basic Venn diagram). For now, let’s think about this algebraically. You have the following partitions of the union of two (arbitrary) $A$ and $B$:

• The subset of $A$ that is exclusive to $A$. In other words, this is $A \setminus B$ or, equivalently, $A \cap B^c$, where $B^c$ denotes the complement of $B$.
• Symmetrically, the subset of $B$ that is exclusive to $B$, equal to $B \setminus A$.
• The intersection, $A \cap B$.

Now consider what happens if you try to naively compute $A \cup B$ as $|A| + |B|$ where the sets have non-empty overlap. Clearly the elements in the exclusive parts of $A$ and $B$ are correctly counted. However, you’re counting the intersection twice. To correct for that, you just need to subtract the intersection from the naive sum. This gives us the basic two-set “principle of inclusion/exclusion” (PIE):

$$|A \cup B| = |A| + |B| - |A \cap B|$$

We will often want to unify more than two sets though, so we need to genralize this to $n$ sets. As above, it’s helpful to look at a simple Venn diagram for 3 sets to understand how they might intersect, but unfortunately, the general case for large $n$ cannot be visualized in the plane this way. Instead, I will derive the general case algebraically by first expanding the result for $n = 3$ and then inductively showing the rule for larger $n$. I’ve tried to make the steps below reasonably explicit without going overboard, but there are just a lot of possible intersections (exponentially many in $n$, as you’ll see). This will be easier to follow if you understand De Morgan’s laws.

$$\begin{aligned} |A \cup B \cup C| &= |(A \cup B) \cup C| \\ &= |A \cup B| + |C| - |(A \cup B) \cap C| \\ &= |A| + |B| - |A \cap B| + |C| - |(A \cap C) \cup (B \cap C)| \\ &= |A| + |B| + |C| - |A \cap B| - (|A \cap C| + |B \cap C| - |(A \cap C) \cap (B \cap C)|) \\ &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{aligned}$$

From this, you might postulate that

$$\begin{aligned} \left| \bigcup_{i=1}^n A_i \right| = &\phantom{+}\sum_{i} |A_i| \\ &- \sum_{i_1 \lt i_2} |A_1 \cap A_2| \\ &+ \cdots \\ &+ (-1)^{n-1} \sum_{i_1 \lt i_2 \lt \cdots \lt i_{n-1}} \left|\bigcap_{j=1}^{n-1} A_{i_{j}}\right| \\ &+ (-1)^n |A_1 \cap A_2 \cap \cdots \cap A_n| \end{aligned}$$

which turns out to be correct in general.

When there is symmetry such that all $|A_i|$ are equal, all pairwise intersections $|A_i \cap A_j|$ are equal, and so on, you can succinctly capture the value of each summation with a single term⁴. You end up with the following:

$$\begin{aligned} \left| \bigcup_{k=1}^n A_k \right| = &\phantom{+}\sum_{k=1}^n \binom{n}{k} \left| \bigcap_{i=1}^k |A_i| \right| \\ \end{aligned}$$

In the inner intersection, I’ve arbitrarily chosen the first $k$ sets as the representatives of all $k$-wise set intersections. This is permissible thanks to the symmetries noted above. This is case is surprisingly common, so you will see it often.⁵

Inductive proof of general PIE

This is not necessarily enlightening, but it may give you confidence that the result is correct if you aren’t certain about the generalization. We already know this holds for $n = 2$ (actually, we’ve shown it up to $n = 3$).

Assume the (strong) inductive hypothesis up to $n - 1$. Decompose the full union into a two-set union which we know how to handle:

$$\begin{aligned} \left| \bigcup_{k=1}^n A_k \right| &= \left| \left(\bigcup_{k=1}^{n-1} A_k \right) \cup A_n \right| \\ &= \left|\bigcup_{k=1}^{n-1} A_k \right| + |A_n| - \left|\left(\bigcup_{k=1}^{n-1} A_k \right) \cap A_n \right| \end{aligned}$$

The $|A_n|$ term adds to the first (single-set) sum and the $(n-1)$-wise union holds the form we know by the inductive hypothesis. The trickier part is dealing with the new intersection on the right, which we need to distribute:

$$\begin{aligned} \left|\left(\bigcup_{k=1}^{n-1} A_k \right) \cap A_n \right| = &\phantom{+} \left|\bigcup_{k=1}^{n-1} (A_k \cap A_n) \right| \\ = &\phantom{+} \sum_{k=1}^{n-1} |(A_k \cap A_n)| \\ &- \sum_{k_1 \lt k_2} |A_{k_1} \cap A_{k_2} \cap A_n| \\ &+ \cdots \\ &+ (-1)^{n-2} \sum_{k_1 \lt \cdots \lt k_{n-2}} |A_{k_1} \cap \cdots \cap A_{k_{n-2}} \cap A_n | \\ &+ (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n | \end{aligned}$$

We invoked the inductive hypothesis again to get the size of the distributed union. Recall that this entire last expression is subtracted from the earlier (known) terms, so the sign parity matches the inductive hypothesis: $k$-way set intersections are added when $k$ is odd and subtracted when $k$ is even. We are effectively just adding a new term to each previous sum with an $A_n$ intersected. The only “new” term is the last one, which is an $n$-way intersection of all sets. As a sanity check, this new term also checks the expected sign parity: we’re subtracting $(-n)^{n-1}$, which is equivalent to adding $(-1)^n$, as desired. And we’re done.

Powerset rule

Finally, the powerset is something we will come across often. The powerset of a given set is the set of all possible subsets of the original set. Suppose that you start with some set $A$ and want to compute the cardinality of its powerset.⁶

To count this, represent each subset as an ordered tuple of $n$ meta-sets, where each entry is either the empty set or a single-element set of some unique element from $A$. Concretely, let each $A_i = \{ \{ a_i \}, \emptyset \}$.⁷ Then form $n$-tuples as in the product rule by selecting an element from $A_i$ at each index $i$. For each meta-set, you have $|A_i| = 2$. By the product rule, there are $2^n$ sets in the powerset of $A$.

Footnotes

1. Technically, the Pi function, where $\Pi(z) = \Gamma(z + 1)$, is the factorial analog, but Gamma is much more widely used. ↩

2. We’re adopting the Graham/Knuth/Patashnik notation here so we might as well use their language. ↩

3. An equivalent way to express this is to count the ways to partition the original set $A$ into two identifiable subsets. ↩

4. I didn’t fully explain binomial coefficients previously, but if you saw the footnote about identifiable partitions, that’s exactly what we’re counting here. In particular, for any set of exactly $k$ (distinct) sets, you are choosing $k$ sets to go into your (labeled) intersection-of-sets (and, by symmetry, the set of excluded sets). ↩

5. There’s obviously sample bias here because we don’t typically attempt to count the intractable problems. In those cases, numerical techniques (via simulation, MCMC, etc.) or asymptotics (via the analytic method) often provide very practically useful results. ↩

6. Not the number of items contained therein, but the number of subsets you could make out of the original $A$. Note that this is different from the analytic powerset construction, which marks the size of contained items (but generally has much more structure than a simple count anyway). ↩

7. The non-empty set corresponds to including $a_i$ in the subset and the empty set corresponds to excluding it. ↩