Questions: Exponential Generating Functions and Labeled Structures

Question 1

A student wants to count labeled structures by partitioning n labeled elements between type A and type B, and decides to use ordinary generating functions (OGFs) because she already knows them. The fundamental problem with this approach is:

• A. OGFs cannot represent sequences at all — only EGFs can encode combinatorial sequences
• B. OGF multiplication does not automatically produce the binomial coefficient C(n,k) needed to count all ways of choosing which k labeled elements go to type A; the n! denominator in EGFs is what makes this combinatorial factor emerge naturally from the product
• C. OGFs work correctly for labeled structures as long as the labels are consecutive integers
• D. The problem is only with type B structures — OGFs handle type A structures correctly in this setting

Answer: (B)

When you multiply two EGFs F(x)·G(x), the n! denominators interact so that the coefficient of xⁿ in the product naturally incorporates C(n,k) — the number of ways to choose which k elements go to structure A. OGF multiplication gives Σ aₖ·b_{n-k}, missing this combinatorial weight entirely. The n! denominator is not an accident; it is precisely what makes EGFs the right tool for labeled enumeration.

Question 2

The EGF for the sequence aₙ = n! (the number of permutations of n elements) is:

• A. e^x, since all EGF sequences normalize to 1 when divided by n!
• B. 1/(1−x), because the coefficient of xⁿ in the EGF is aₙ/n! = n!/n! = 1, and the series Σ xⁿ = 1/(1−x)
• C. n!·e^x, since the factorial multiplies the entire series
• D. e^(n·x), where n represents the permutation size

Answer: (B)

In an EGF, the coefficient of xⁿ is aₙ/n!. If aₙ = n!, then aₙ/n! = 1 for all n, and Σ 1·xⁿ = 1/(1-x). This is a useful sanity check: 1/(1-x) is the EGF for permutations, and e^x is the EGF for the sequence aₙ = 1 (one labeled structure of each size, like a set).

Question 3

Multiplying two EGFs F(x) and G(x) gives an EGF whose coefficient of xⁿ counts the number of structures formed by placing most n labeled elements into either type A or type B (choosing one type for most elements).

• T. True
• F. False

Answer: False

EGF multiplication does the opposite: F(x)·G(x) counts structures formed by *partitioning* the n labeled elements — sending k to type A and the remaining n-k to type B — and summing over all k from 0 to n. The C(n,k) factor for choosing the partition emerges automatically from the n! denominators. It is not a binary choice of which type to use; it is a counted distribution across both.

Question 4

The EGF e^x encodes the sequence aₙ = 1 for all n, representing exactly one labeled structure of each size — such as a set of n labeled elements with no internal structure.

• T. True
• F. False

Answer: True

In the EGF, the coefficient of xⁿ is aₙ/n!. For e^x = Σ xⁿ/n!, the coefficient of xⁿ is 1/n!, so aₙ = 1. This means there is exactly one labeled structure of size n — a set. The EGF e^x plays the same fundamental role for labeled structures that the constant sequence 1 plays for unlabeled structures in OGFs.

Question 5

Why is dividing by n! in an EGF the structural feature that makes it appropriate for counting labeled structures, while ordinary generating functions are not? Explain in terms of what the product of two EGFs computes.

Model answer: In an EGF, the coefficient of xⁿ is aₙ/n!. When you multiply F(x)·G(x) and extract the coefficient of xⁿ, you get Σ_{k=0}^{n} (aₖ/k!)(b_{n-k}/(n-k)!). Multiplying by n! to recover the count gives Σ C(n,k) aₖ b_{n-k} — a sum over all ways to choose k labeled elements for type A (C(n,k) ways), build an A-structure on them (aₖ ways), and a B-structure on the rest (b_{n-k} ways). The n! denominator is what makes the binomial coefficient appear automatically. OGF multiplication gives Σ aₖ b_{n-k}, missing C(n,k) entirely — correct for unlabeled structures but wrong for labeled ones where the choice of which specific elements go where must be counted.

This is why labeled and unlabeled combinatorial problems use different generating function types. The n! is not a normalization convenience — it is the algebraic encoding of the label-assignment counting that makes EGF multiplication combinatorially meaningful for labeled partitioning.