[Written 2000-12-20, typographical corrections 2004-01-05]
In Chapter 3 of his authoritative work generatingfunctionology, Herbert Wilf develops a theory relating the number of graphs composed of specific connected components to the number of such components, and relating the number of permutations composed of specific cycles to the number of such cycles.
He introduces a metaphor of cards, hands and decks, which I have found to be of limited pedagogical use, mainly because the metaphor evokes regular playing cards while the metaphorical uses to which they are put involve repeatedly erasing and rewriting the cards in a manner atypical of real cards.
With thanks then to my godson Daniel West (age 7), his brother Ross (age 2) and my nephew Owen Dahl (age 2), I present what I hope is a clearer metaphor.
A truck is an ordered pair (C, M) of a labelled directed graph C (the (cargo) configuration) and an integer set M (the (cargo) manifest). The (cargo) capacity of a truck is the cardinality of its manifest. A truck is said to have standard cargo if its manifest M is {1,2,3,...,n} for some integer n.
Let (C,M) be a truck and f be an injective integer function. The reloading of (C,M) induced by f is a new reloaded truck (C',M') whose cargo manifest M' is the image of M under f, and whose cargo configuration C' is the graph C with any integer label n replaced by f(n). If n1 < n2 < n3 < ... nk and f(ni):=i then f induces the standard reloading on any truck whose cargo manifest is {ni}.
A convoy is a (finite) set of trucks (Ci,Mi) whose manifests Mi form a partition of {1,2,3,...,n} for some positive integer n. n is called the (total) (cargo) capacity of the convoy.
A (maintenance) subfleet is a finite set of trucks of standard cargo whose cargo capacities are all equal. Note that the cargo configurations of the trucks in a subfleet must be distinct, as the subfleet is a set and not a multiset.
A fleet is a sequence of subfleets S1, S2, S3, ... where the nth subfleet Sn consists of trucks of capacity n.
We will see that there is a simple generatingfunctionological relationship between the number of convoys that can be made from the possibly reloaded trucks in a fleet and the number of trucks in each subfleet in the fleet.
Let F := ( S1, S2, S3, ... ) be a fleet.
Let sn := |Sn|, the size of the nth maintenance subfleet (i.e., the subfleet of trucks of cargo capacity n) for each subfleet sn in F.
Let S(x):=sum(n>0, snxn/n!), the subfleet enumerator for F an exponential generating function for {sn}.
Let c(n,k) be the number of convoys of total cargo capacity n made up of k trucks, each of which is a reloading of a truck in the fleet.
Let C(x,y):=sum(n>0, k>0, c(n,k)xnyk/n!), the convoy enumerator for F, a mixed generating function for c(n,k), exponential in n and ordinary in k.
Let c(n) be the number of convoys with a total cargo capacity of n made up of any number of reloadings of trucks in the fleet.
Let C(x):=sum(n>0, c(n)xn/n!), the exponential generating function for c(n).
Let F' and F" be two fleets and F be their subfleetwise union. If their respective convoy enumerators are C'(x,y), C"(x,y) and C(x,y) then:
C(x,y) = C'(x,y) C"(x,y)
Exercise, or see Wilf.
C(x,y) = ey S(x) and C(x) = eS(x).
(A complete proof is left as an exercise, or can be found in Wilf.) Show that the result is true for a fleet consisting of a single truck. Use induction and Lemma 6 to extend the result to a fleet consisting of any number of trucks all of which belong to the same subfleet. Use induction and Lemma 6 again to extend to a fleet with a finite number of nonempty subfleets. For the general case, compare coefficients on both sides of the equation and by examining any one particular coefficient argue that the finite case suffices.
As promised, we describe the number of permutations of n objects according to how many cycles they have.
Let each subfleet Sn consist of all the trucks of standard cargo whose cargo configuration is a cyclic labelled directed graph on n vertices, with labels {1,2,3,...,n}. Each sn is then (n-1)!, the number of cyclic permutations on n objects, and S(x) = -ln(1-x).
A convoy of k trucks and cargo capacity n then represents a permutation on n objects with exactly k cycles, of which there are c(n,k).
C(x,y) = exp y (-ln (1-x)) = (1-x)-y
and so (after some manipulation)
y(y+1)(y+2)...(y+n-1) = sum(k, c(n,k)yk),
a recursive definition for c(n,k). Alternately,
c(n,k) = [xn/n!] {(1/k!) ln (1/(1-x))k}
Modify the argument in Example 8 to enumerate permutations which consist of an odd number of cycles, all of which are of even length.
Consider a fleet F consisting of all trucks of standard cargo whose cargo configurations are connected labelled undirected graphs with labels {1,2,3,...,n} for any n. (We call a directed graph undirected if for every edge from vertex A to vertex B there is an edge from vertex B to vertex A.) It is easy to show that there are 2choose(n,2) labelled graphs on n vertices, which correspond in this model to convoys of total capacity n. Use Theorem 7 to produce a recursion describing the subfleet enumerator for this fleet and thence the number of connected labelled graphs on n vertices.
Use truck theory to count the partitions of {1,2,3,...,n} into k non-empty subsets.
Extend truck theory to "train theory" by requiring that the order of trucks (railcars) in a convoy (train) be significant. Give an example of an interesting application.