How Do Generating Functions Count Subsets?

TL;DR

Generating functions count subsets by translating each include-or-exclude decision into a polynomial factor, with exponents recording subset sums and coefficients recording how many subsets produce each sum. For subsets of the integers from 1 through 2000 whose sums are divisible by 5, this encoding replaces an impossible brute-force search through 2^2000 subsets with algebraic evaluation techniques involving roots of unity and complex numbers.

Transcript

In a moment, I will ask you a puzzle, and it's a pretty hard puzzle, actually, but before I do, I want to lead with a spoiler, which is the fact that the way we're going to solve this involves the use of complex numbers. And once you hear it, you will agree that that seems absurd, given that the puzzle is going to be purely a discrete question. It ... Read More

Key Insights

• The original counting problem is to find how many subsets of {1, 2, ..., 2000} have an element sum divisible by 5, with the empty set included because its sum is defined as zero and zero is treated as a multiple of 5.
• The total number of possible subsets is 2^2000 because each of the 2000 elements creates an independent binary choice: include the element or omit it. This makes direct enumeration infeasible even with extraordinarily large amounts of time and physical computing resources.
• The rough expectation is that approximately one fifth of all subsets should have sums divisible by 5 because subset sums may be expected to spread roughly evenly across residue classes modulo 5. However, this approximation cannot supply the exact integer count or determine its error.
• The smaller set {1, 2, 3, 4, 5} has 32 total subsets and eight qualifying subsets whose sums are divisible by 5. Since one fifth of 32 is 6.4, the exact count in this example is larger than the simple uniform-distribution estimate.
• The generating function for the smaller example is (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)(1 + x^5). Its algebraic expansion mirrors the construction of every subset by offering one inclusion-or-exclusion choice for each available element.
• Each term in the expanded generating function represents one subset, and the exponent of x equals the sum of that subset's elements. Choosing x and x^2, for example, represents selecting {1, 2} and produces x^3 because the subset sum is 3.
• Each coefficient in the collected polynomial counts the number of subsets having the corresponding sum. Multiple selections that yield the same exponent become like terms, so three copies of x^10 combine into a coefficient of three and encode three subsets with sum 10.
• Complex numbers are useful here because evaluation tricks involving roots of unity can filter polynomial information according to divisibility conditions. The lesson presents this as a discrete analogue of studying specially designed complex-valued functions to obtain information about prime numbers.

Questions & Answers

Q: How can generating functions count subsets by their sums?

Construct a product containing one factor 1 + x^k for every available integer k. Choosing 1 from a factor means omitting k, while choosing x^k means including it. Every complete sequence of choices therefore represents exactly one subset. When the selected powers are multiplied, their exponents add, so the resulting exponent records the subset sum. After like terms are combined, each coefficient records how many subsets have that sum.

Q: Why is brute force impractical for subsets of 1 through 2000?

The set has 2000 elements, and every element creates two independent possibilities: it can be included or excluded. Consequently, there are 2^2000 distinct subsets to inspect. A brute-force program would need to construct each subset, calculate its sum, test divisibility by 5, and update a counter when appropriate. The transcript describes this search space as so enormous that even all conceivable time and physical resources would not come close to completing it.

Q: What generating function represents subsets of 1 through 5?

The generating function is (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)(1 + x^5). Each parenthetical expression corresponds to one number in the set. Selecting the constant term means leaving that number out, and selecting its power of x means putting it into the subset. Expanding the full product therefore reproduces all 32 inclusion-or-exclusion choices while automatically organizing them according to their element sums.

Q: What do the exponents mean in a subset generating function?

An exponent represents the sum of the elements chosen for a particular subset. For example, choosing x from the factor associated with 1 and x^2 from the factor associated with 2, while choosing 1 from all remaining factors, produces x^3. That term corresponds to the subset {1, 2}, whose sum is 3. Distinct subsets can produce the same exponent whenever their elements have the same total.

Q: What do the coefficients mean in a subset generating function?

A coefficient counts how many different subsets produce the exponent attached to it. Before like terms are collected, every subset contributes its own power of x. If several subsets have the same sum, they contribute identical powers and are combined algebraically. The transcript gives x^10 as an example: three separate terms become a coefficient of three, indicating that three subsets of {1, 2, 3, 4, 5} have sum 10.

Q: How many subsets of 1 through 5 have sums divisible by 5?

Exactly eight of the 32 subsets of {1, 2, 3, 4, 5} have sums divisible by 5. The count includes the empty set because its sum is defined as zero, and zero is considered a multiple of 5. A simple one-fifth estimate would predict 6.4 subsets, so this small example demonstrates that the exact answer can differ from the approximate expectation of an even distribution across residues modulo 5.

Q: Why is one fifth of all subsets only an approximation?

Divisibility by 5 suggests grouping subset sums into five residue classes, so an approximately even distribution would place about one fifth of all subsets in each class. Nothing in that heuristic proves the classes contain exactly equal numbers, however. For the smaller example, one fifth of 32 is 6.4, which cannot itself be a subset count, while the actual qualifying count is eight. The challenge is therefore to calculate the precise deviation.

Q: Why do complex numbers appear in this discrete counting problem?

Complex numbers enter through evaluation techniques involving roots of unity, which the lesson uses to extract information about sums divisible by 5 from a generating function. This is surprising because the original problem concerns only whole numbers, subsets, and addition. The broader principle is that a specially designed smooth or complex-valued function can encode discrete information, making some questions easier to answer through analysis of the function than through direct inspection of the underlying objects.

Summary & Key Takeaways

• The central problem asks for the exact number of subsets of the integers from 1 through 2000 whose elements have a sum divisible by 5. Although roughly one fifth of all subsets should qualify, that estimate is not an integer and does not determine the precise error, so a more sophisticated counting method is required.

• A smaller example uses subsets of {1, 2, 3, 4, 5}. Among its 32 subsets, including the empty set with sum zero, exactly eight have sums divisible by 5. This illustrates both the counting objective and the fact that the qualifying sums are not distributed perfectly evenly among the five residue classes.

• The generating function multiplies factors of the form 1 + x^k, one for each available integer k. Selecting 1 excludes k, while selecting x^k includes it. After expansion, every term corresponds to a subset, its exponent equals that subset's sum, and its coefficient counts how many subsets produce that sum.