Count labeled products with exponential series

Try

Give each of four distinct labels either a red role or a blue role. There are sixteen assignments. If exactly k labels are red, there are C(4, k) ways to choose them. A generating function for labeled objects must account for this choice of which labels enter each component, not merely how many do. Exponential generating functions build the binomial factor into multiplication by dividing the nth count by n!.

Predict

Predict why multiplying ordinary counting series would miss information. If each size has one red structure and one blue structure, ordinary convolution gives n+1 size splits. The labeled product has 2^n assignments because each split also chooses a subset of labels. Neither answer is universally wrong; they count different objects. Decide which interpretation applies before choosing the series normalization.

Experiment

For n=3, inspect the label-allocation factors.

Red size k	Red structure count	Blue structure count	Label choices
0	1	1	1
1	1	1	3
2	1	1	3
3	1	1	1

The total is eight. Algebraically exp (z)exp (z)=exp (2z), whose normalized coefficient at degree three is 2³. The raw coefficient is 8/3!, not eight.

Understand

For labeled counts a_n define A(z)=Σa_n z^n/n!. If a product object consists of an A-structure on one subset and a B-structure on its complementary subset, then c_n=Σ_k C(n, k)a_k b_(n−k). Multiplying the two exponential series proves the same rule because n!/(k!(n−k)!) is the label-choice factor. This derivation assumes that transporting a structure along a relabeling preserves its count and that the two roles are distinguishable. If the components are unordered and interchangeable, a further symmetry correction is required; that is the subject of the exponential formula.

Apply

Differentiation shifts the normalized sequence: A′(z)=Σa_(n+1)z^n/n!. Combinatorially this can represent a structure on n ordinary labels together with one additional distinguished label fixed outside the label set. Multiplication by z instead corresponds to choosing and marking one existing label when applied to A′: zA′ has counts n a_n. These two operations differ. For example the EGF of permutations is 1/(1−z), since a_n=n!, while its derivative counts permutations on n+1 labels relative to n ordinary labels. Track the normalization before interpreting a derivative as a marking operation.

A useful diagnostic is to compare coefficients at degree two by hand. If the first component can use either one of two labels and the other uses the remaining label, there are two labeled allocations even when each component has only one internal structure. The factor two comes from label choice, not from ordering identical objects inside a component. EGF multiplication preserves this distinction automatically.

Continue

As a recurrence exercise, a_(n+1)=c a_n with a_0=1 becomes A′=cA and therefore A=exp (cz), counting c independent colors per label when c is a nonnegative integer. More complicated labeled decompositions yield differential equations or products that can be solved coefficientwise. No analytic convergence is required for these formal operations in characteristic zero. When evaluating the resulting series numerically or discussing singularities, state the extra analytic assumptions separately.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with assemble labeled components.