The labelled product

An object of 𝒜 of size k, an object of ℬ of size m, and the C(n,k) objects of 𝒜 ⋆ ℬ they produce, n = k+m.

object α ∈ 𝒜

size k

object β ∈ ℬ

size m

the rule

The pair (α, β) does not have labels 1,…,n; it has 1,…,k twice. The labelled product fixes this by choosing which k of the labels 1,…,n go to α and relabelling each object in increasing order, so that the relative order inside α and inside β is kept. One choice of subset, one object of 𝒜 ⋆ ℬ.

summing over k: the binomial convolution

Now let 𝒜 and ℬ be whole classes. Every object of 𝒜 ⋆ ℬ of size n comes from exactly one triple (k-subset, α of size k, β of size n−k), so c_n = Σ_k C(n,k) a_k b_n−k, which is c_n/n! = Σ_k (a_k/k!)(b_n−k/(n−k)!): the Cauchy product of the exponential generating functions. The table uses the classes chosen above (sequences: k!, cycles: (k−1)!, sets: 1, rooted trees: k^k−1).