Riddell's formula for unlabeled graphs is a generating function transformation $$1 + B(x) = \exp \sum_{k=1}^\infty \frac{A(x^k)}{k}$$ which gives the number of graphs whose connected components have a property P in terms of the number of connected graphs with property P. From a modern perspective it is "just" the application of Pólya's enumeration theorem to the natural action of the symmetric groups.

Pólya published in 1937 (ten years after Redfield, but attracting much more attention); the theorem as I understand it is given in terms of subgroups of the symmetric groups, and $S_n$ is arguably the most obvious subgroup, and one of the most useful, of $S_n$.

Riddell's name is attached to the formula in consequence of his 1951 doctoral dissertation in physics, and Harary gives to understand in a 1955 paper1 that Riddell had priority; curiously he describes the formula as "a well known identity" but states that "Riddell's combinatorial derivation ... is not readily available in the literature" (presumably because doctoral dissertations didn't have as wide circulation as journals).

I find it surprising that it should have taken so long for the enumeration theorem to be applied to the full $S_n$, and Harary's paper hints at the result being known more widely than is easily accounted for if Riddell truly had priority. Is there more to the story than this? Was the formula circulating as folklore but unpublished for up to 14 years?

1 The Number of Linear, Directed, Rooted, and Connected Graphs, Frank Harary, Transactions of the American Mathematical Society 78.2 (1955)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.