The University of Montana
Department of Mathematical Sciences

Technical report #26/2009

Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings

Erin E. Emerson*
Ann Arbor MI 48104, USA
erinbeth@umich.edu

P. Mark Kayll†
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
mark.kayll@umontana.edu


Abstract

How many perfect matchings are contained in a given bipartite graph? An exercise in Godsil’s 1993 Algebraic Combinatorics solicits proof that this question’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 independently 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 revisit the theorem and to broaden the formula’s reach.

Keywords: perfect matching, rook polynomial, bipartite complement, inclusion-exclusion

AMS Subject Classification: Primary 05A15 Secondary 05C70 33B15

Download Technical Report: Pdf (97 KB)
_________________________________________________________
*based on work done while attending University of Montana
†contact author