
Discrete Mathematics and Optimization Seminar

Apr. 20, 2009
A ContinuousDiscrete Symbiosis: Counting Matchings with Integrals
Mark Kayll
University of Montana

How many perfect matchings are contained in a given bipartite graph? An
exercise in Godsil’s 1993 Algebraic Combinatorics solicits proof that this ques
tion’s answer is an integral involving a certain rook polynomial. Though not
widely known, this result appears implicitly in Riordan’s 1958 An Introduction
to Combinatorial Analysis. It was stated more explicitly and proved indepen
dently by S.A. Joni and G.C. Rota [JCTA 29 (1980), 59–73] and C.D. Godsil
[Combinatorica 1 (1981), 257–262]. Another generation later, perhaps it’s time
both to simplify the proof and to broaden the formula’s reach. I’ll present a
selfcontained proof and a delightful application. This talk is based on joint
work with Erin Emerson.



