Assemble labeled components

Try

A partition of four labeled people into teams is an unordered collection of nonempty labeled blocks. We can first order the teams, count that easier construction, and then remove the artificial order. For a fixed number k of teams, every partition has exactly k! orderings because its blocks are distinct sets of labels. This equal-fiber argument is the core of the exponential formula.

Predict

Predict why empty components must be excluded. If empty blocks were allowed, arbitrarily many could be inserted without consuming labels, and dividing by k! would no longer describe a finite set of objects of each size. The formal condition C(0)=0 ensures that only finitely many component counts contribute to any fixed coefficient. It is both a combinatorial restriction and an algebraic well-definedness condition.

Experiment

Classify partitions of four labels by block-size pattern.

Block sizes	Number
4	1
3+1	4
2+2	3
2+1+1	6
1+1+1+1	1

Their sum is fifteen. Explain the factor three for two pairs: choose a first pair in six ways, then divide by two because swapping the pair roles leaves the partition unchanged.

Understand

Let c_j count allowed connected components on j labels, with j≥1, and let C(z)=Σc_j z^j/j!. An ordered k-tuple of components on disjoint label blocks has EGF C(z)^k by repeated labeled multiplication. Forgetting the component order divides by k!, since nonempty disjoint label sets distinguish the components even when their internal shapes coincide. Summing over k≥0 gives A(z)=exp (C(z)). More explicitly, for multiplicities m_j with Σj m_j=n, the count is n! product over j of (c_j/j!)^(m_j)/m_j!. This expression allocates labels, constructs each component, and removes permutations of equal-sized component slots.

Apply

For ordinary set partitions, c_j=1, so C(z)=exp (z)−1 and A(z)=exp (exp (z)−1). For permutations, the connected components are cycles, with c_j=(j−1)!, giving C(z)=Σz^j/j=−log (1−z) and A(z)=1/(1−z). These examples have different component structures but the same assembly mechanism. Restricting allowed block or cycle sizes changes C while preserving the exponential construction. Introducing a marker u per component gives exp (uC (z)); its coefficient of u^k records objects with exactly k components.

For involutions, every permutation cycle has size one or two, so the EGF is exp (z+z²/2). Choosing the role of label n gives the independent recurrence a_n=a_(n−1)+(n−1)a_(n−2): it is fixed, or paired with one of the other labels. With a_0=a_1=1, the counts begin 1, 1, 2, 4, 10. The recurrence verifies the component formula without repeating its algebra.

Continue

The formula concerns labeled objects with a unique decomposition into disjoint components. It is not valid for every collection of unlabeled shapes, where automorphisms change the counting. Check uniqueness of decomposition before exponentiating a series. As a transfer task, model partitions into blocks of size one or two with exp (z+z²/2), then derive its coefficient recurrence by choosing the partner of a distinguished label. This independent recurrence is a useful check that the generating expression counts the intended objects.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with count constrained paths and recursive trees.