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 , we denote its cardinality by . 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, and , then the cardinality of their union is . 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, , where each each of the can be “independently” chosen. Independent in this sense means that the choice of some specific object does not impact the set of choices available to where . Moreover, suppose that each choice must be drawn from some set . Then the cardinality of all possible tuples you can form from the respective sets (the Cartesian product) is
As a special case, if , then you have
Permutation rule
Suppose you have some set where 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 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 , where is the item you happened to choose in any given path. Clearly, . By similar reasoning, in general. Then by the product rule, we have
where denotes the set of permutations of and is pronounced ” factorial” (or “-bang”).
By convention, . (How many ways can you distinctly order an empty list?)
The generalization of from the non-negative integers to the complex plane is the Gamma function, .1 While we’ll be using it heavily for AC, it is by no means elementary, so I won’t discuss it further here.
-permutation (falling factorial) rule
Sometimes you are counting the set of -permutations over distinct objects, where . By arguments analogous to the above, you have
where is known as the “falling factorial” and pronounced ” to the 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”:
This is not used often in “basic” counting but still appears in many places.
-combination rule
Now suppose you want to count the size of , the set of “-combinations” drawn from the same set described in the -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 -permutation.
Suppose that you have some element which was drawn from . This is itself a -element “set”, since it was constructed from unique elements. You should be able to convince yourself that (by the permutation rule) there are exactly permutations corresponding to each possible element . Moreover, since every possible -permutation is counted by , we can produce every by turning a given -permutation into a set. In other words, we have a surjection which overrepresents each element in by a factor of which gives us . In other words:
where is called a “binomial coefficient” and is commonly pronounced ” choose ”.
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) and :
- The subset of that is exclusive to . In other words, this is or, equivalently, , where denotes the complement of .
- Symmetrically, the subset of that is exclusive to , equal to .
- The intersection, .
Now consider what happens if you try to naively compute as where the sets have non-empty overlap. Clearly the elements in the exclusive parts of and 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):
We will often want to unify more than two sets though, so we need to genralize this to 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 cannot be visualized in the plane this way. Instead, I will derive the general case algebraically by first expanding the result for and then inductively showing the rule for larger . 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 , as you’ll see). This will be easier to follow if you understand De Morgan’s laws.
From this, you might postulate that
which turns out to be correct in general.
When there is symmetry such that all are equal, all pairwise intersections are equal, and so on, you can succinctly capture the value of each summation with a single term4. You end up with the following:
In the inner intersection, I’ve arbitrarily chosen the first sets as the representatives of all -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 (actually, we’ve shown it up to ).
Assume the (strong) inductive hypothesis up to . Decompose the full union into a two-set union which we know how to handle:
The term adds to the first (single-set) sum and the -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:
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: -way set intersections are added when is odd and subtracted when is even. We are effectively just adding a new term to each previous sum with an intersected. The only “new” term is the last one, which is an -way intersection of all sets. As a sanity check, this new term also checks the expected sign parity: we’re subtracting , which is equivalent to adding , 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 and want to compute the cardinality of its powerset.6
To count this, represent each subset as an ordered tuple of meta-sets, where each entry is either the empty set or a single-element set of some unique element from . Concretely, let each .7 Then form -tuples as in the product rule by selecting an element from at each index . For each meta-set, you have . By the product rule, there are sets in the powerset of .
Footnotes
-
Technically, the Pi function, where , is the factorial analog, but Gamma is much more widely used. ↩
-
We’re adopting the Graham/Knuth/Patashnik notation here so we might as well use their language. ↩
-
An equivalent way to express this is to count the ways to partition the original set into two identifiable subsets. ↩
-
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 (distinct) sets, you are choosing sets to go into your (labeled) intersection-of-sets (and, by symmetry, the set of excluded sets). ↩
-
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. ↩
-
Not the number of items contained therein, but the number of subsets you could make out of the original . 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). ↩
-
The non-empty set corresponds to including in the subset and the empty set corresponds to excluding it. ↩