APPLICATIONS OF A TECHNIQUE FOR LABELLED ENUMERATION
Brendan D. McKay · 1983
A technique involving summation over roots of unity was used by Liskovec in 1971 to count labelled regular tournaments. The same method is used here to count regular tournaments to 21 vertices, Eulerian digraphs to 16 vertices, Eulerian oriented graphs to 15 vertices, regular graphs to 21 vertices, regular bipartite graphs to 40 vertices, and Eulerian circuits in com-plete graphs with up to 17 vertices. The last calculation was performed jointly with R. W. Robinson. All the objects counted are vertex-labelled. 1. Coefficient extraction for generating functions Consider a multivariate generating function f(x,..., x) = is a complex number. Lemma 1.1 Let m.> 0 and k. be integers for 1 < j 2 n. Define J 1 u+ = e271i'mj (1 < j < n). Then where the sum on the right is over all cl,..., c such that n m.Ic.- k. for 1 Â ¥ j in.