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