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 AA, we denote its cardinality by A|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, AA and BB, then the cardinality of their union is AB=A+B|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, (a1,a2,,an)(a_1, a_2, \dots, a_n), where each each of the aia_i can be “independently” chosen. Independent in this sense means that the choice of some specific object aia_i does not impact the set of choices available to aja_j where iji \neq j. Moreover, suppose that each choice aia_i must be drawn from some set AiA_i. Then the cardinality of all possible tuples you can form from the respective sets (the Cartesian product) is

A1×A2××An=k=1nAk|A_1 \times A_2 \times \cdots \times A_n| = \prod_{k=1}^n |A_k|

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

jA1×A2××An=Anj |A_1 \times A_2 \times \cdots \times A_n| = |A|^n

Permutation rule

Suppose you have some set AA where A=n|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 nn 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 A2=A{a1}A_2 = A \setminus \{a_1\}, where a1a_1 is the item you happened to choose in any given path. Clearly, A2=n1|A_2| = n - 1. By similar reasoning, Ak=n(k1)|A_k| = n - (k-1) in general. Then by the product rule, we have

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

where PP denotes the set of permutations of AA and n!n! is pronounced ”nn factorial” (or “nn-bang”).

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

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

kk-permutation (falling factorial) rule

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

Pk=n(n1)(n(k1))k factors=n!(nk)!=nk,\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 nkn^{\underline{k}} is known as the “falling factorial” and pronounced ”nn to the kk falling”.2 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”:

nk=n(n+1)(n+(k1))k factorsn^{\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.

kk-combination rule

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

Suppose that you have some element cc which was drawn from CkC_k. This is itself a kk-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!k! permutations corresponding to each possible element cc. Moreover, since every possible kk-permutation is counted by nkn^{\underline{k}}, we can produce every cCkc \in C_k by turning a given kk-permutation into a set. In other words, we have a surjection PkCkP_k \mapsto C_k which overrepresents each element in CkC_k by a factor of k!k! which gives us Pk=k!Ck|P_k| = k! |C_k|. In other words:

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

where (nk)\binom{n}{k} is called a “binomial coefficient” and is commonly pronounced ”nn choose kk”.

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) AA and BB:

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

Now consider what happens if you try to naively compute ABA \cup B as A+B|A| + |B| where the sets have non-empty overlap. Clearly the elements in the exclusive parts of AA and BB 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):

AB=A+BAB|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 nn 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 nn cannot be visualized in the plane this way. Instead, I will derive the general case algebraically by first expanding the result for n=3n = 3 and then inductively showing the rule for larger nn. 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 nn, as you’ll see). This will be easier to follow if you understand De Morgan’s laws.

ABC=(AB)C=AB+C(AB)C=A+BAB+C(AC)(BC)=A+B+CAB(AC+BC(AC)(BC))=A+B+CABACBC+ABC\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

i=1nAi=+iAii1<i2A1A2++(1)n1i1<i2<<in1j=1n1Aij+(1)nA1A2An\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 Ai|A_i| are equal, all pairwise intersections AiAj|A_i \cap A_j| are equal, and so on, you can succinctly capture the value of each summation with a single term4. You end up with the following:

k=1nAk=+k=1n(nk)i=1kAi\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 kk sets as the representatives of all kk-wise set intersections. This is permissible thanks to the symmetries noted above. This is case is surprisingly common, so you will see it often.5

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=2n = 2 (actually, we’ve shown it up to n=3n = 3).

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

k=1nAk=(k=1n1Ak)An=k=1n1Ak+An(k=1n1Ak)An\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 An|A_n| term adds to the first (single-set) sum and the (n1)(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:

(k=1n1Ak)An=+k=1n1(AkAn)=+k=1n1(AkAn)k1<k2Ak1Ak2An++(1)n2k1<<kn2Ak1Akn2An+(1)n1A1A2An\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: kk-way set intersections are added when kk is odd and subtracted when kk is even. We are effectively just adding a new term to each previous sum with an AnA_n intersected. The only “new” term is the last one, which is an nn-way intersection of all sets. As a sanity check, this new term also checks the expected sign parity: we’re subtracting (n)n1(-n)^{n-1}, which is equivalent to adding (1)n(-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 AA and want to compute the cardinality of its powerset.6

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

Footnotes

  1. Technically, the Pi function, where Π(z)=Γ(z+1)\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 AA 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 kk (distinct) sets, you are choosing kk 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 AA. 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 aia_i in the subset and the empty set corresponds to excluding it.