The Algebra of Set Functions II :

An Enumerative Analogue of Hall’s Theorem for Bipartite Graphs

Bodo Lass

Université de Lyon ; Université Lyon 1 ; INSA de Lyon, F-69621 ; Ecole Centrale de Lyon ; CNRS, UMR5208, Institut Camille Jordan, 43 blvd du 11 novembre 1918, F-69622 Villeurbanne-Cedex, France

                               lass @ math.univ-lyon1.fr

Dedicated to Eberhard Triesch

Abstract

Triesch [25] conjectured that Hall’s classical theorem on matchings in bipartite graphs is a special case of a phenomenon of monotonicity for the number of matchings in such graphs. We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit monotonic formula counting matchings in bipartite graphs.

This formula follows from a general duality theory which we develop for counting matchings. Moreover, we make use of generating functions for set functions as introduced in [20], and we show how they are useful for counting matchings in bipartite graphs in many different ways.

1 Introduction

The bipartite graphs studied in this paper are described as triples

G = (X, Y; E),  E ⊆ X × Y,  (1.1)

where X and Y are the two vertex sets, and E is the edge set. It is always assumed that X, called the first vertex set, is finite and |X| = n. The second vertex set Y is also finite, but variable. As the edge set E is a subset of X × Y, all the graphs are simple : they have no loops, and no multiple edges. For each nonempty subset X′ of X define the set of neighbours of X′ by

Γ_{G}(X′) := {y ∈ Y | ∃ x ∈ X′ such that (x, y) ∈ E}.  (1.2)

Thus, Γ_{G}(X′) is the set of all vertices y ∈ Y which are related to at least one vertex in X′ by an edge of G. Also, let

d_{G}^{+}(X′) := |Γ_{G}(X′)|.  (1.3)

As will be seen, the integral-valued function d_{G}^{+} : 2^{X} \ ∅ → ℤ, further called set function, determines G up to a permutation of the vertices of Y.

An injective mapping i : X′ → Y such that (x, i(x)) ∈ E for every x ∈ X′ is called a matching of X′ into Y and the pairs (x, i(x)) (x ∈ X′) are the edges of the matching. Let m_{G}^{−}(X′) be the number of such injective mappings (or matchings). The mapping m_{G}^{−} : 2^{X} \ ∅ → ℤ is then another set function. We show that it also determines G up to a permutation of the vertices of Y, and we prove an easy formula allowing to calculate the set function m_{G}^{−} with the help of the set function d_{G}^{+}. Moreover, d_{G}^{+} can be calculated with the help of m_{G}^{−}.

Hall’s classical theorem on matchings in bipartite graphs asserts that G has a matching of X into Y if and only if d_{G}^{+}(X′) ≥ |X′| for all ∅ ⊂ X′ ⊆ X. The existence of a matching trivially implies d_{G}^{+}(X′) ≥ |X′| for all ∅ ⊂ X′ ⊆ X. Therefore, the interesting part of Hall’s theorem can be formulated as follows :

If d_{G}^{+}(X′) ≥ |X′| ∀ ∅ ⊂ X′ ⊆ X, then m_{G}^{−}(X) ≥ 1.  (1.4)

Let Y′ be a set disjoint from X and Y with |Y′| = |X| = n, and let b : X → Y′ be a bijection. Next, define the bipartite graph G′ = (X, Y′; E′) by letting E′ be the family of all pairs (x, b(x)) with x ∈ X, so that G′ has just n independent edges. This implies d_{G′}^{+}(X′) = |X′| for all ∅ ⊂ X′ ⊆ X and m_{G′}^{−}(X) = 1. We can then reformulate the interesting part of Hall’s theorem as follows:

If d_{G}^{+}(X′) ≥ d_{G′}^{+}(X′) ∀ ∅ ⊂ X′ ⊆ X, then m_{G}^{−}(X) ≥ m_{G′}^{−}(X).  (1.5)

This inspired Triesch [25] to conjecture that for arbitrary mutually disjoint finite vertex sets X, Y, Y′ and for arbitrary bipartite graphs G = (X, Y; E), G′ = (X, Y′; E′) sharing the vertex set X the following implication holds:

If d_{G}^{+}(X′) ≥ d_{G′}^{+}(X′) ∀ ∅ ⊂ X′ ⊆ X, then m_{G}^{−}(X) ≥ m_{G′}^{−}(X).  (1.6)

One purpose of this paper is to prove this conjecture for all graphs with sufficiently many edges by deriving an explicit monotonic formula counting matchings in bipartite graphs. If n = 1 and X = {1}, then it is evident that

m_{G}^{−}({1}) = d_{G}^{+}({1}),  (1.7)

and this identity implies the conjectured monotonicity immediately. If n = 2 and X = {1, 2}, then we prove the formula

m_{G}^{−}({1, 2}) = (d_{G}^{+}({1}) − 1) (d_{G}^{+}({2}) − 1) + (d_{G}^{+}({1, 2}) − 1)  (1.8)

implying the monotonicity easily. For n = 3 and X = {1, 2, 3}, we get

m_{G}^{−}({1, 2, 3}) = (d_{G}^{+}({1}) − 2) (d_{G}^{+}({2}) − 2) (d_{G}^{+}({3}) − 2)
+ (d_{G}^{+}({1, 2}) − 2) (d_{G}^{+}({3}) − 2)
+ (d_{G}^{+}({1, 3}) − 2) (d_{G}^{+}({2}) − 2)
+ (d_{G}^{+}({2, 3}) − 2) (d_{G}^{+}({1}) − 2)
+2 (d_{G}^{+}({1, 2, 3}) − 2) ,  (1.9)

and for n = 4 and X = {1, 2, 3, 4}, our formula reads

m_{G}^{−}({1, 2, 3, 4}) = (d_{G}^{+}({1}) − 3) (d_{G}^{+}({2}) − 3) (d_{G}^{+}({3}) − 3) (d_{G}^{+}({4}) − 3)
+ (d_{G}^{+}({1, 2}) − 3) (d_{G}^{+}({3}) − 3) (d_{G}^{+}({4}) − 3)
+ (d_{G}^{+}({1, 3}) − 3) (d_{G}^{+}({2}) − 3) (d_{G}^{+}({4}) − 3)
+ (d_{G}^{+}({1, 4}) − 3) (d_{G}^{+}({2}) − 3) (d_{G}^{+}({3}) − 3)
+ (d_{G}^{+}({2, 3}) − 3) (d_{G}^{+}({1}) − 3) (d_{G}^{+}({4}) − 3)
+ (d_{G}^{+}({2, 4}) − 3) (d_{G}^{+}({1}) − 3) (d_{G}^{+}({3}) − 3)
+ (d_{G}^{+}({3, 4}) − 3) (d_{G}^{+}({1}) − 3) (d_{G}^{+}({2}) − 3)
+ (d_{G}^{+}({1, 2}) − 3) (d_{G}^{+}({3, 4}) − 3)
+ (d_{G}^{+}({1, 3}) − 3) (d_{G}^{+}({2, 4}) − 3)
+ (d_{G}^{+}({1, 4}) − 3) (d_{G}^{+}({2, 3}) − 3)
+2 (d_{G}^{+}({1, 2, 3}) − 3) (d_{G}^{+}({4}) − 3)
+2 (d_{G}^{+}({1, 2, 4}) − 3) (d_{G}^{+}({3}) − 3)
+2 (d_{G}^{+}({1, 3, 4}) − 3) (d_{G}^{+}({2}) − 3)
+2 (d_{G}^{+}({2, 3, 4}) − 3) (d_{G}^{+}({1}) − 3)
+6 (d_{G}^{+}({1, 2, 3, 4}) − 3) .  (1.10)

For general X = {1, 2, 3, …, n}, we prove the following new formula.

Theorem 1. We have

m_{G}^{−}(X) = ∑_{k=1}^{n} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)! (d_{G}^{+}(B_{i}) − n + 1) ,  (1.11)

where the sum is over all partitions of X into k nonempty blocks B_{1},…,B_{k} (⊎ denotes disjoint union).

This theorem implies immediately that m_{G}^{−}(X) depends monotonically on the numbers d_{G}^{+}(X′), ∅ ⊂ X′ ⊆ X, if d_{G}^{+}(X′) ≥ n − 1 for every ∅ ⊂ X′ ⊆ X. For usual graphs, this condition is satisfied as soon as the degree d_{G}^{+}(x) is at least n − 1 for every vertex x ∈ X. In other words, if G = (X, Y; E) and G′ = (X, Y′; E′) are bipartite graphs such that d_{G′}^{+}(x) ≥ n − 1 for every x ∈ X and d_{G}^{+}(X′) ≥ d_{G′}^{+}(X′) for all ∅ ⊂ X′ ⊆ X, then our formula implies m_{G}^{−}(X) ≥ m_{G′}^{−}(X). Therefore, it proves the conjecture imagined by Triesch as soon as d_{G′}^{+}(x) ≥ n − 1 for every x ∈ X. On the other hand, this conjecture follows from Hall’s theorem if d_{G′}^{+}(x) ≤ 1 for every x ∈ X. But of course, some cases of the conjecture remain open between those extreme situations where G′ has few or many edges.

For every ∅ ⊂ X′ ⊆ X, we have introduced d_{G}^{+}(X′) as the number of vertices y ∈ Y which are related to at least one vertex in X′ by an edge of G. In an analogous way, we define d_{G}^{−}(X′) as the number of vertices y ∈ Y which are related to every vertex in X′ by an edge of G, and we prove that the integral-valued set function d_{G}^{−} : 2^{X} \ ∅ → ℤ also determines G up to a permutation of the vertices of Y. More precisely, we prove the formulae

d_{G}^{−}(X′) = ∑_{X′′⊆X′}(−1)^{|X′′|−1}d_{G}^{+}(X′′),  (1.12)
d_{G}^{+}(X′) = ∑_{X′′⊆X′}(−1)^{|X′′|−1}d_{G}^{−}(X′′),  (1.13)

by studying linear transformations between the set functions d_{G}^{−}, d_{G}^{+} and another set function x_{G}. These considerations of linear algebra for set functions will be explained in Section 2.

In order to go beyond those results, however, linear algebra is not sufficient, and we need the algebra of set functions. A comprehensive introduction to this algebraic tool explaining, in particular, the basic product theorem can be found in the preceding article [20] (for other applications of set functions, see [16, 17, 18, 19]). In Section 3, we make use of this product theorem as well as of the linear algebra explained in Section 2, in order to count matchings in bipartite graphs. In particular, we prove the following formulae :

m_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{n−k} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)!d_{G}^{−}(B_{i}),  (1.14)

d_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{n−k} \frac{(k − 1)!}{(n − 1)!} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} m_{G}^{−}(B_{i}).  (1.15)

We still introduce one more set function m_{G}^{+} and we show how the algebra of set functions allows us to prove easily lots of relations between all those set functions.

Identity (1.11) of the preceding theorem, however, cannot be proved in this way, because the “local” factors (d_{G}^{+}(B_{i}) − n + 1) contain the “global” parameter n = |X|. Therefore, Section 4 is devoted to a general “global” duality theory for the enumeration of matchings in bipartite graphs, which follows from a still more general duality theory for the enumeration of functions. We have explained this theory in the preceding article [20]. With the help of this “global” duality, we finally get a short and surprising proof of our formula (1.11).

In Section 5, devoted to Rook Theory (see [5]), we show that by means of the duality theory several results related to [19] can be proved, which generalize works by Chung and Graham [7], Chow and Gessel [6], Joni, Rota and Zeilberger [15], as well as several articles on Laguerre polynomials by Askey, Gasper, Ismail, Koornwinder, Even, Gillis, Foata, Zeilberger, Godsil, Jackson, de Sainte-Catherine and Viennot [2, 3, 4, 8, 10, 11, 12, 14, 23, 26].

2 Bipartite Graphs as Set Functions

Let X be a fixed finite set of vertices, n = |X|. We are interested in bipartite graphs G = (X, Y; E), E ⊆ X × Y, where the second finite vertex set Y is considered to be variable.

Let X′ be an arbitrary nonempty subset of X, ∅ ⊂ X′ ⊆ X. Let x_{G}(X′) denote the number of vertices y ∈ Y for which (x, y) ∈ E if and only if x ∈ X′, that is, the number of y ∈ Y for which Γ_{G}(y) = X′, where Γ_{G}(y) is the set of neighbours of y. In other words, x_{G}(X′) counts the number of vertices of Y which are joint by an edge of G to every vertex of X′ and to no vertex of X \ X′. The following lemma is evident.

Lemma 1. The bipartite graph G = (X, Y; E) is determined up to isomorphism by the set function x_{G} : 2^{X} \ ∅ → ℤ. Here, x_{G} determines a usual bipartite graph if and only if x_{G}(X′) ≥ 0 for all ∅ ⊂ X′ ⊆ X.

Moreover, let d_{G}^{−}(X′), ∅ ⊂ X′ ⊆ X, denote the number of vertices of Y which are joint by an edge of G to every vertex of X′ and possibly to some vertices of X \ X′ :

d_{G}^{−} : 2^{X} \ ∅ → ℤ,  d_{G}^{−}(X′) = ∑_{X′⊆X′′} x_{G}(X′′)  ∀ ∅ ⊂ X′ ⊆ X.  (2.1)

The set function d_{G}^{+} already mentioned in the introduction and the set function x_{G} are related as follows :

d_{G}^{+} : 2^{X} \ ∅ → ℤ,  d_{G}^{+}(X′) = ∑_{X′∩X′′≠∅} x_{G}(X′′) = |Γ_{G}(X′)|  ∀ ∅ ⊂ X′ ⊆ X.  (2.2)

We can consider x_{G}, d_{G}^{−} and d_{G}^{+} as vectors with 2^{|X|} − 1 = 2^{n} − 1 components, and we want to study the linear transformations between them. Let [X′ ⊆ X′′] denote a square matrix with 2^{n} −1 rows and 2^{n} −1 columns indexed by the nonempty subsets of X. More precisely, if a row is indexed by X′ and a column is indexed by X′′, then the coefficient corresponding to this row and column equals 1 if X′ ⊆ X′′ and 0 otherwise. Similarly, for the matrix [X′ ⊆ X′′](−1)^{|X′′\X′|}, the coefficient corresponding to a row indexed by X′ and a column indexed by X′′ equals (−1)^{|X′′\X′|} if X′ ⊆ X′′ and 0 otherwise. The coefficients of the matrix [X′ ∩ X′′ ≠ ∅] are all 0 or 1. The coefficient corresponding to a row indexed by X′ and a column indexed by X′′ is 1 if and only if X′ and X′′ have a nonempty intersection. The matrices −[X′ ∪ X′′ = X](−1)^{|X′∩X′′|} and −[X′ ⊇ X′′](−1)^{|X′′|} are defined in the same way. They allow us to formulate the following theorem.

Theorem 2. The linear transformations between the vectors x_{G}, d_{G}^{−} and d_{G}^{+} are described by the matrices already introduced. More precisely, we have for all ∅ ⊂ X′ ⊆ X :

d_{G}^{−}(X′) = [X′ ⊆ X′′] · x_{G}(X′′),  (2.3)
x_{G}(X′) = [X′ ⊆ X′′](−1)^{|X′′\X′|} · d_{G}^{−}(X′′),  (2.4)
d_{G}^{+}(X′) = [X′ ∩ X′′ ≠ ∅] · x_{G}(X′′),  (2.5)
x_{G}(X′) = −[X′ ∪ X′′ = X](−1)^{|X′∩X′′|} · d_{G}^{+}(X′′),  (2.6)
d_{G}^{−}(X′) = −[X′ ⊇ X′′](−1)^{|X′′|} · d_{G}^{+}(X′′),  (2.7)
d_{G}^{+}(X′) = −[X′ ⊇ X′′](−1)^{|X′′|} · d_{G}^{−}(X′′).  (2.8)

Proof. First of all, equations (2.3) and (2.5) are immediately equivalent to our definitions of the vectors d_{G}^{−} and d_{G}^{+}. In order to prove (2.4), we have to show that the matrices [X′ ⊆ X′′] and [X′ ⊆ X′′](−1)^{|X′′\X′|} are inverse of each other. This is a direct consequence of the inclusionexclusion principle :

[X′ ⊆ X^{∗}] · [X^{∗} ⊆ X′′](−1)^{|X′′\X^{∗}|} = [X′ = X′′],  (2.9)

where [X′ = X′′] is the identity matrix; in order to find a coefficient of a product of two matrices, one has to calculate a scalar product, which corresponds to a sum over X^{∗} for fixed X′ and X′′ in the preceding equation. In the same way, we can calculate :

−[X′ ∩ X^{∗} ≠ ∅] · [X^{∗} ∪ X′′ = X](−1)^{|X^{∗}∩X′′|} =
+[X′ ∩ X^{∗} = ∅] · [X^{∗} ∪ X′′ = X](−1)^{|X^{∗}∩X′′|} = [X′ = X′′],  (2.10)

which proves our formula (2.6). The matrix −[X′ ⊇ X′′](−1)^{|X′′|} is inverse of itself :

[X′ ⊇ X^{∗}] · [X^{∗} ⊇ X′′](−1)^{|X^{∗}|+|X′′|} = [X′ = X′′],  (2.11)

which shows the equivalence of (2.7) and (2.8). Therefore, it remains to deduce (2.7) :

d_{G}^{−}(X′) = [X′ ⊆ X^{∗}] · x_{G}(X^{∗})
= −[X′ ⊆ X^{∗}] · [X^{∗} ∪ X′′ = X](−1)^{|X^{∗}∩X′′|} · d_{G}^{+}(X′′)
= −[X′ ⊇ X′′](−1)^{|X′′|} · d_{G}^{+}(X′′).  (2.12)

Example. For n = 3 and X = {1, 2, 3}, we use shorthand notations of type d_{13}^{−} = d_{G}^{−}({1, 3}). Then our formulae read as follows.

d_{1}^{−} = x_{1} + x_{12} + x_{13} + x_{123},  (2.13)
d_{12}^{−} = x_{12} + x_{123},  (2.14)
d_{123}^{−} = x_{123};  (2.15)
x_{1} = d_{1}^{−} − d_{12}^{−} − d_{13}^{−} + d_{123}^{−},  (2.16)
x_{12} = d_{12}^{−} − d_{123}^{−},  (2.17)
x_{123} = d_{123}^{−};  (2.18)
d_{1}^{+} = x_{1} + x_{12} + x_{13} + x_{123},  (2.19)
d_{12}^{+} = x_{1} + x_{2} + x_{12} + x_{13} + x_{23} + x_{123},  (2.20)
d_{123}^{+} = x_{1} + x_{2} + x_{3} + x_{12} + x_{13} + x_{23} + x_{123};  (2.21)
x_{1} = −d_{23}^{+} + d_{123}^{+}  (2.22)
x_{12} = −d_{3}^{+} + d_{13}^{+} + d_{23}^{+} − d_{123}^{+}  (2.23)
x_{123} = d_{1}^{+} + d_{2}^{+} + d_{3}^{+} − d_{12}^{+} − d_{13}^{+} − d_{23}^{+} + d_{123}^{+};  (2.24)
d_{1}^{−} = d_{1}^{+},  (2.25)
d_{12}^{−} = d_{1}^{+} + d_{2}^{+} − d_{12}^{+},  (2.26)
d_{123}^{−} = d_{1}^{+} + d_{2}^{+} + d_{3}^{+} − d_{12}^{+} − d_{13}^{+} − d_{23}^{+} + d_{123}^{+};  (2.27)
d_{1}^{+} = d_{1}^{−},  (2.28)
d_{12}^{+} = d_{1}^{−} + d_{2}^{−} − d_{12}^{−},  (2.29)
d_{123}^{+} = d_{1}^{−} + d_{2}^{−} + d_{3}^{−} − d_{12}^{−} − d_{13}^{−} − d_{23}^{−} + d_{123}^{−}.  (2.30)

The following corollaries are immediate consequences of the preceding theorem.

Corollary 1. The bipartite graph G = (X, Y; E) is determined up to a permutation of the vertices of Y by the set function d_{G}^{−} : 2^{X} \ ∅ → ℤ. Here d_{G}^{−} determines a bipartite graph if and only if

x_{G}(X′) = ∑_{X′⊆X′′}(−1)^{|X′′\X′|} · d_{G}^{−}(X′′) ≥ 0  ∀ ∅ ⊂ X′ ⊆ X.  (2.31)

Corollary 2. The bipartite graph G = (X, Y; E) is determined up to a permutation of the vertices of Y by the set function d_{G}^{+} : 2^{X} \ ∅ → ℤ. Here d_{G}^{+} determines a bipartite graph if and only if

x_{G}(X′) = ∑_{X′∪X′′=X} −(−1)^{|X′∩X′′|} · d_{G}^{+}(X′′) ≥ 0  ∀ ∅ ⊂ X′ ⊆ X.  (2.32)

Corollary 3. For

D_{G}^{−}(χ) := ∑_{∅⊂X′⊆X} d_{G}^{−}(X′) · χ^{X′}  and  D_{G}^{+}(χ) := ∑_{∅⊂X′⊆X} d_{G}^{+}(X′) · χ^{X′}  (2.33)

we have

D_{G}^{+}(χ) = −D_{G}^{−}(−χ) · exp(X)  and  D_{G}^{−}(χ) = −D_{G}^{+}(−χ) · exp(X).  (2.34)

3 Matchings in Bipartite Graphs

Now our purpose is to calculate the set function m_{G}^{−} : 2^{X} \ ∅ → ℤ defined in the introduction. To this end, we define

M_{G}^{−}(χ) := ∑_{∅⊂X′⊆X} m_{G}^{−}(X′) · χ^{X′}.  (3.1)

The product theorem of [20] implies the following lemma.

Lemma 2. Let

X′ = ∑_{x∈X′} χ^{{x}}.  (3.2)

Then

1 + M_{G}^{−}(χ) = ∏_{∅⊂X′⊆X}(1 + X′)^{x_{G}(X′)}  (3.3)

= ∏_{∅⊂X′⊆X} ∑_{k=0}^{|X′|} x_{G}(X′)\underline{k} · \frac{X′^{k}}{k!} ,  (3.4)

where x_{G}(X′)\underline{k} = x_{G}(X′)(x_{G}(X′) − 1)(x_{G}(X′) − 2) ⋯ (x_{G}(X′) − k + 1) by definition.

Proof. For every ∅ ⊂ X′ ⊆ X we have

(1 + X′)^{x_{G}(X′)} = ∑_{k=0}^{|X′|} \binom{x_{G}(X′)}{k}X′^{k} = ∑_{k=0}^{|X′|} x_{G}(X′)\underline{k} · \frac{X′^{k}}{k!} .  (3.5)

We next calculate the logarithm of the product displayed in (3.3) :

log (1 + M_{G}^{−}(χ)) = ∑_{∅⊂X′⊆X} x_{G}(X′) · log (1 + X′)
= ∑_{∅⊂X′⊆X}(−1)^{|X′|−1}(|X′| − 1)! · d_{G}^{−}(X′) · χ^{X′}.  (3.6)

We can now define

D_{G}^{−}!(χ) := ∑_{∅⊂X′⊆X}(|X′| − 1)! · d_{G}^{−}(X′) · χ^{X′}  (3.7)

and immediately get the following theorem.

Theorem 3. We have the identities :

1 + M_{G}^{−}(χ) = exp (−D_{G}^{−}!(−χ)) ,  (3.8)
log (1 + M_{G}^{−}(χ)) = −D_{G}^{−}!(−χ),  (3.9)
∂^{x}M_{G}^{−}(χ) = − (1 + M_{G}^{−}(χ)) · ∂^{x}D_{G}^{−}!(−χ) ∀ x ∈ X, (3.10)
∂M_{G}^{−}(χ) = − (1 + M_{G}^{−}(χ)) · ∂D_{G}^{−}!(−χ).  (3.11)

Corollary 4. We have

m_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{n−k} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)!d_{G}^{−}(B_{i}),  (3.12)

d_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{n−k} \frac{(k − 1)!}{(n − 1)!} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} m_{G}^{−}(B_{i}).  (3.13)

In particular, the bipartite graph G = (X, Y; E) is determined up to a permutation of the vertices of Y by the set function m_{G}^{−} : 2^{X} \ ∅ → ℤ.

Example. For n = 3 and X = {1, 2, 3}, we use shorthand notations of type m_{13}^{−} = m_{G}^{−}({1, 3}). Then our formulae read as follows.

m_{1}^{−} = d_{1}^{−},  (3.14)
m_{12}^{−} = d_{1}^{−}d_{2}^{−} − d_{12}^{−},  (3.15)
m_{123}^{−} = d_{1}^{−}d_{2}^{−}d_{3}^{−} − d_{12}^{−}d_{3}^{−} − d_{13}^{−}d_{2}^{−} − d_{23}^{−}d_{1}^{−} + 2d_{123}^{−};  (3.16)
d_{1}^{−} = m_{1}^{−},  (3.17)
d_{12}^{−} = m_{1}^{−}m_{2}^{−} − m_{12}^{−},  (3.18)
d_{123}^{−} = m_{1}^{−}m_{2}^{−}m_{3}^{−} − \frac{1}{2}m_{12}^{−}m_{3}^{−} − \frac{1}{2}m_{13}^{−}m_{2}^{−} − \frac{1}{2}m_{23}^{−}m_{1}^{−} + \frac{1}{2}m_{123}^{−}.  (3.19)

Remark. With our method of set functions, it is possible to study most questions for matchings in bipartite graphs also for permanents of matrices. It seems that the only result known along those lines (without using set functions) is the analogue of formula (3.12); see [21].

Our preceding formula (3.12) implies, in particular, that m_{G}^{−}(X) is a polynomial in the variables d_{G}^{−}(X′), ∅ ⊂ X′ ⊆ X. Moreover, m_{G}^{−}(X) is also a polynomial in the variables d_{G}^{+}(X′), ∅ ⊂ X′ ⊆ X, as well as in the variables x_{G}(X′), ∅ ⊂ X′ ⊆ X. This can be seen easily if we replace the variables d_{G}^{−}(X′) using formulae (2.7) or (2.3). In particular, everything is well defined for negative integers x_{G}(X′), ∅ ⊂ X′ ⊆ X (more generally, x_{G}(X′) ∈ A for an arbitrary commutative ring A with 1 is sufficient). We can give the following traditional combinatorial interpretation for this situation.

We can consider X as a set of persons and to every subset X′ ⊆ X associate a job for which all the persons of the subset X′ are qualified, and nobody else (the qualification of a person x ∈ X for a job y ∈ Y is indicated by an edge (x, y) ∈ E in our bipartite graph G = (X, Y; E)). This job has the usual capacity x_{G}(X′), which means that at most x_{G}(X′) persons can work there. More precisely, if k persons want to work there, then this is possible in x_{G}(X′)\underline{k} = x_{G}(X′)(x_{G}(X′) − 1)(x_{G}(X′) − 2) ⋯ (x_{G}(X′) − k + 1) different ways, that is, every person taking the job reduces its capacity by 1. In this way, m_{G}^{−}(X) counts the number of possibilities to find jobs for everybody, as reflected by our formula (3.4) of the preceding lemma.

This combinatorial interpretation motivates us to study the following slight modification. We continue to consider X as a set of persons and with every subset X′ ⊆ X to associate a job for which all the persons from X′ are qualified, and nobody else. But we give this job the alternative capacity x_{G}(X′), which means that if k persons want to work there, then this is possible in x_{G}(X′)\overline{k} = x_{G}(X′)(x_{G}(X′) + 1)(x_{G}(X′) + 2) ⋯ (x_{G}(X′) + k − 1) different ways, that is, every person taking the job increases its capacity by 1. (This is completely analogous to the problem of choosing k elements among x_{G}(X′) ones : if repetitions are not allowed, then the number of different ways is x_{G}(X′)\underline{k}/k! ; if they are allowed, then we have x_{G}(X′)\overline{k}/k! different choices.) If we work with those alternative capacities, then we denote the number of possibilities to find jobs for everybody by m_{G}^{+}(X). If X′ ⊆ X, then the number of ways to find a job (with alternative capacities) for every person x ∈ X′ (for which this person is qualified) is m_{G}^{+}(X′). This defines a new set function m_{G}^{+} : 2^{X} \ ∅ → ℤ we want to study :

M_{G}^{+}(χ) := ∑_{∅⊂X′⊆X} m_{G}^{+}(X′) · χ^{X′}.  (3.20)

Our preceding discussion proves an analogue of our preceding lemma.

Lemma 3. We have

1 + M_{G}^{+}(χ) = ∏_{∅⊂X′⊆X} ∑_{k=0}^{|X′|} x_{G}(X′)\overline{k} · \frac{X′^{k}}{k!}  (3.21)
= ∏_{∅⊂X′⊆X}(1 − X′)^{−x_{G}(X′)},  (3.22)

where x_{G}(X′)\overline{k} = x_{G}(X′)(x_{G}(X′) + 1)(x_{G}(X′) + 2) ⋯ (x_{G}(X′) + k − 1) by definition.

Proof. For every ∅ ⊂ X′ ⊆ X we have

∑_{k=0}^{|X′|} x_{G}(X′)\overline{k}· \frac{X′^{k}}{k!} = ∑_{k=0}^{|X′|}(−1)^{k} (−x_{G}(X′))\underline{k}· \frac{X′^{k}}{k!} = ∑_{k=0}^{|X′|} \binom{−x_{G}(X′)}{k}(−X′)^{k} = (1−X′)^{−x_{G}(X′)}.

(3.23)

Identities (3.4) and (3.22) show that by choosing negative integers for x_{G}(X′), ∅ ⊂ X′ ⊆ X, we get (−1)^{n}m_{G}^{+}(X) with n = |X| instead of m_{G}^{−}(X). This proves the following theorem.

Theorem 4. We have

1 + M_{G}^{+}(χ) = (1 + M_{G}^{−}(−χ))^{−1} .  (3.24)

Corollary 5. We have

m_{G}^{+}(X) = ∑_{k=1}^{n}(−1)^{n−k}k! ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} m_{G}^{−}(B_{i}),  (3.25)

m_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{n−k}k! ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} m_{G}^{+}(B_{i}).  (3.26)

In particular, the bipartite graph G = (X, Y; E) is determined up to isomorphism by the set function m_{G}^{+} : 2^{X} \ ∅ → ℤ. Moreover, the identity (1 + M_{G}^{+}(−χ)) (1 + M_{G}^{−}(χ)) = 1 means

(−1)^{|X|}m_{G}^{+}(X) + m_{G}^{−}(X) + ∑_{∅⊂X′⊂X}(−1)^{|X′|}m_{G}^{+}(X′) · m_{G}^{−}(X \ X′) = 0.  (3.27)

The two preceding theorems imply the following results.

Theorem 5. We have the identities :

1 + M_{G}^{+}(χ) = exp (D_{G}^{−}!(χ)) ,  (3.28)
log (1 + M_{G}^{+}(χ)) = D_{G}^{−}!(χ),  (3.29)
∂^{x}M_{G}^{+}(χ) = (1 + M_{G}^{+}(χ)) · ∂^{x}D_{G}^{−}!(χ) ∀ x ∈ X, (3.30)
∂M_{G}^{+}(χ) = (1 + M_{G}^{+}(χ)) · ∂D_{G}^{−}!(χ).  (3.31)

Corollary 6. We have

m_{G}^{+}(X) = ∑_{k=1}^{n} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)!d_{G}^{−}(B_{i}),  (3.32)

d_{G}^{−}(X) = ∑_{k=1}^{n}(−1)^{k−1} \frac{(k − 1)!}{(n − 1)!} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} m_{G}^{+}(B_{i}).  (3.33)

Therefore, m_{G}^{+}(X) depends monotonically on the numbers d_{G}^{−}(X′), ∅ ⊂ X′ ⊆ X, if d_{G}^{−}(X′) ≥ 0 for every ∅ ⊂ X′ ⊆ X, i.e. in particular if x_{G}(X′) ≥ 0 for every ∅ ⊂ X′ ⊆ X, which are the defining inequalities for bipartite graphs.

Remark. It is possible to interpret formula (3.32) in such a way, that we sum over all permutations of X the number of functions from X to Y which respect the edges E of our bipartite graph and which are constant on the cycles of the permutations. This provides a link to Pólya’s Counting Theory.

Example. For n = 3 and X = {1, 2, 3}, we use shorthand notations of type m_{13}^{+} = m_{G}^{+}({1, 3}). Then our formulae read as follows.

m_{1}^{+} = d_{1}^{−},  (3.34)
m_{12}^{+} = d_{1}^{−}d_{2}^{−} + d_{12}^{−},  (3.35)
m_{123}^{+} = d_{1}^{−}d_{2}^{−}d_{3}^{−} + d_{12}^{−}d_{3}^{−} + d_{13}^{−}d_{2}^{−} + d_{23}^{−}d_{1}^{−} + 2d_{123}^{−};  (3.36)
d_{1}^{−} = m_{1}^{+},  (3.37)
d_{12}^{−} = −m_{1}^{+}m_{2}^{+} + m_{12}^{+},  (3.38)
d_{123}^{−} = m_{1}^{+}m_{2}^{+}m_{3}^{+} − \frac{1}{2}m_{12}^{+}m_{3}^{+} − \frac{1}{2}m_{13}^{+}m_{2}^{+} − \frac{1}{2}m_{23}^{+}m_{1}^{+} + \frac{1}{2}m_{123}^{+}.  (3.39)

The end of this section is not necessary for understanding the rest of the article : it is written only for readers interested in exponential generating functions. If we want to work with them instead of working with set functions, we must use an infinite set X. Moreover, everything must depend just on the cardinalities of the finite subsets of X and not on those subsets themselves. For our bipartite graph G = (X, Y; E), this means that every vertex of Y is either joint to all vertices of X or to just one vertex of X : if a vertex y ∈ Y is joint to x ∈ X and to X′ with ∅ ⊂ X′ ⊂ X \ {x}, then, by permuting the elements of X \ {x}, we see that there must be infinitely many vertices y ∈ Y each of which is joint to x and to a subset X′′ of X \ {x} in bijection with X′. Therefore, x would get an infinite degree, which makes it impossible to count matchings.

In other words, we can suppose that there is one y ∈ Y of capacity a joint to every x ∈ X, and for every vertex x ∈ X, there is a vertex in Y of capacity i joint only to x. Let us denote this infinite bipartite graph by G(a, i). It is evident that 1 + M_{G(1,0)}^{−}(χ) = 1 + X and 1 + M_{G(0,1)}^{−}(χ) = exp(X). Therefore the product theorem implies the following proposition.

Proposition 1. We have

1 + M_{G(a,i)}^{−}(χ) = (1 + X)^{a} exp(i · X),  (3.40)
1 + M_{G(a,i)}^{+}(χ) = 1 + M_{G(−a,−i)}^{−}(−χ) = (1 − X)^{−a} exp(i · X).  (3.41)

Example. Let G_{n}(2) be the number of connected 2-regular bipartite multigraphs (i.e. multiple edges are allowed) G = ({1, 2, …, n}, {1, 2, …, n}; E) with fixed marked vertices, then G_{1}(2) = 1 and G_{n}(2) = n!(n − 1)!/2 for n > 1 : if we choose every second edge of such a cycle, then we get an arbitrary first permutation, and a second permutation which is cyclic with respect to the first one.

Let H_{n}(2) be the number of arbitrary 2-regular bipartite multigraphs G = (X, Y; E) with fixed marked vertex sets of cardinality n. By permuting the vertices of Y, we get

\frac{H_{n}(2)}{n!} = ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} \frac{G_{|B_{i}|}(2)}{|B_{i}|!} = m_{G(1/2,1/2)}^{+}(X).  (3.42)

Therefore our preceding proposition implies (see Stanley’s book [24], 3.15.1.d) :

∑_{n=0}^{∞} H_{n}(2)\frac{X^{n}}{(n!)^{2}} = (1 − X)^{−1/2} exp(X /2).  (3.43)

4 Duality for Matchings in Bipartite Graphs

Let us come back to our study of bipartite graphs G = (X, Y; E) with the help of set functions. Until now, we have never used x_{G}(∅), that is the number of vertices y ∈ Y which are joint to no x ∈ X at all. If we want to construct the bipartite complement of G, however, or just a partial complement C_{X′}(G) with ∅ ⊂ X′ ⊆ X, then x_{G}(∅) will become indispensable. In fact, for every ∅ ⊆ X′′ ⊆ X, we have the identity

x_{C_{X′}(G)}(X′′) = x_{G}(X′△X′′),  and in particular  x\overline{G}(X′′) = x_{G}(X \ X′′).  (4.1)

Therefore it is convenient to choose x_{G}(∅) in a useful way, namely in such a way that we get normality in the sense of the duality theory of [20].

Proposition 2. The set of injective functions from X to Y, that is the set of functions with usual capacities x_{G}(X′), ∅ ⊆ X′ ⊆ X is normal if and only if

∑_{∅⊆X′⊆X} x_{G}(X′) = |X| − 1.  (4.2)

Proof. Since the edges of our bipartite graph have no importance at all for the question of normality (see [20]), it is sufficient to consider the situation with a single job of capacity

∑_{∅⊆X′⊆X} x_{G}(X′).  (4.3)

If everybody except one person has already chosen this job, then the last person has

( ∑_{∅⊆X′⊆X} x_{G}(X′)) − (|X| − 1)  (4.4)

choices to take this job, and the situation is called normal if and only if the last number is equal to 0.

The same kind of argument proves the analogous result for alternative capacities.

Proposition 3. The set of functions from X to Y with alternative capacities x_{G}(X′), ∅ ⊆ X′ ⊆ X is normal if and only if

∑_{∅⊆X′⊆X} x_{G}(X′) = 1 − |X|.  (4.5)

These propositions, together with the duality theory of [20], imply the following theorems.

Theorem 6. (Duality Theorem for Usual Matchings in Bipartite Graphs) If x_{G}(∅) is chosen in such a way that

∑_{∅⊆X′⊆X} x_{G}(X′) = |X| − 1,  (4.6)

then

m_{C_{x}(G)}^{−}(X) = −m_{G}^{−}(X)  ∀ x ∈ X,  (4.7)
m_{C_{X′}(G)}^{−}(X) = (−1)^{|X′|}m_{G}^{−}(X)  ∀ X′ ⊆ X,  (4.8)
m− ; \overline{G}(X) = (−1)^{|X|}m_{G}^{−}(X).  (4.9)

Theorem 7. (Duality Theorem for Alternative Matchings in Bipartite Graphs) If x_{G}(∅) is chosen in such a way that

∑_{∅⊆X′⊆X} x_{G}(X′) = 1 − |X|,  (4.10)

then

m_{C_{x}(G)}^{+}(X) = −m_{G}^{+}(X)  ∀ x ∈ X,  (4.11)
m_{C_{X′}(G)}^{+}(X) = (−1)^{|X′|}m_{G}^{+}(X)  ∀ X′ ⊆ X,  (4.12)
m+ ; \overline{G}(X) = (−1)^{|X|}m_{G}^{+}(X).  (4.13)

It is evident that for every ∅ ⊂ X′ ⊆ X we have

d_{G}^{−}(X′) + d+ ; \overline{G}(X′) = d− ; \overline{G}(X′) + d_{G}^{+}(X′) = ∑_{∅⊆X′′⊆X} x_{G}(X′′).  (4.14)

This identity allows us to prove the following two corollaries easily.

Corollary 7. We have

m_{G}^{+}(X) = ∑_{k=1}^{n}(−1)^{n−k} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)! (d_{G}^{+}(B_{i}) + n − 1) .  (4.15)

Proof. If we are in a normal situation, then the preceding duality theorem for alternative matchings in bipartite graphs and our formula (3.32) imply

m_{G}^{+}(X) = (−1)^{|X|}m+ ; \overline{G}(X)
= (−1)^{|X|} ∑_{k=1}^{|X|} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)!d− ; \overline{G}(B_{i})

= ∑_{k=1}^{|X|}(−1)^{|X|} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)! (1 − |X| − d_{G}^{+}(B_{i})) .  (4.16)

In the same way, we obtain the formula already mentioned in the introduction.

Corollary 8. We have

m_{G}^{−}(X) = ∑_{k=1}^{n} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)! (d_{G}^{+}(B_{i}) − n + 1) .  (4.17)

Therefore, m_{G}^{−}(X) depends monotonically on the numbers d_{G}^{+}(X′), ∅ ⊂ X′ ⊆ X, if d_{G}^{+}(X′) ≥ n − 1 for every ∅ ⊂ X′ ⊆ X, i.e. in particular if x_{G}(X′) ≥ 0 for all ∅ ⊂ X′ ⊆ X and d_{G}^{+}(x) = d_{G}^{−}(x) = d_{G}(x) ≥ n − 1 for all x ∈ X, where the last condition is satisfied as soon as x_{G}(X′) ∈ ℤ and x_{G}(X′) > 0 for all ∅ ⊂ X′ ⊆ X.

Proof. If we are in a normal situation, then the preceding duality theorem for usual matchings in bipartite graphs and our formula (3.12) imply

m_{G}^{−}(X) = (−1)^{|X|}m− ; \overline{G}(X)
= (−1)^{|X|} ∑_{k=1}^{|X|}(−1)^{|X|−k} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)!d− ; \overline{G}(B_{i})

= ∑_{k=1}^{|X|}(−1)^{k} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} (|B_{i}| − 1)! (|X| − 1 − d_{G}^{+}(B_{i})) .  (4.18)

The conjecture imagined by Triesch [25] does not follow in all cases from the preceding corollary because it affirms that m_{G}^{−}(X) depends monotonically on the numbers d_{G}^{+}(X′), ∅ ⊂ X′ ⊆ X, as soon as x_{G}(X′) ∈ ℤ and x_{G}(X′) ≥ 0 for all ∅ ⊂ X′ ⊆ X. If we consider bipartite graphs as integer points in the cone defined by the inequalities x_{G}(X′) ≥ 0 for all ∅ ⊂ X′ ⊆ X, then we have proved the conjecture for all points which are not on the boundary of the cone.

It is possible to prove the monotonicity directly, if just one component of the vector d_{G}^{+} is increased by 1. Ideas of this kind can also be used in order to give a more elementary (but less instructive) proof of our formula (4.17). If we increase d_{G}^{+}(X′), ∅ ⊂ X′ ⊆ X, by 1, then all x_{G}(X′′), ∅ ⊂ X′′ ⊆ X, with X′′ ∪ X′ = X are modified : they decrease by 1 if |X′′ ∩ X′| ≡ 0 (mod 2) and they increase by 1 if |X′′ ∩ X′| ≡ 1 (mod 2); see our formula (2.6). In particular, in order to accomplish this transformation without violating the conditions x_{G}(X′′) ∈ ℤ and x_{G}(X′′) ≥ 0 for all ∅ ⊂ X′′ ⊆ X, we need the conditions d_{G}(x) ≥ 2^{|X′|−1} for all x ∈ X \ X′ and d_{G}(x) ≥ 2^{|X′|−2} for all x ∈ X′ if |X′| > 1.

If we increase only components of d_{G}^{+} of the same parity (the parity of the component d_{G}^{+}(X′) is by definition the parity of |X′|), then the monotonicity follows directly from what has already been said. If we increase just two arbitrary components, then it can also be shown directly.

The right hand side of (4.17) looks perfect if d_{G}^{+}(X′) ≥ n − 1 for every ∅ ⊂ X′ ⊆ X, but far from perfect if some of the numbers d_{G}^{+}(X′) − n + 1 are negative, since a lot of cancellation occurs. A natural way to avoid it consists in replacing d_{G}^{+}(X′) − n + 1 by (d_{G}^{+}(X′) − n + 1)_{+}, where (x)_{+} := max(x, 0) denotes the maximum of x and 0 for any real number x. More precisely, we conjecture that an identity of the following type holds :

m_{G}^{−}(X) = ∑_{k=1}^{n} ∑_{B_{1}⊎···⊎B_{k}=X} ∏_{i=1}^{k} f(B_{i}) (d_{G}^{+}(B_{i}) − n + 1)_{+} ,  (4.19)

where f(X′), ∅ ⊂ X′ ⊆ X, depends monotonically on the numbers d_{G}^{+}(X′′), ∅ ⊂ X′′ ⊆ X′. In other words, formula (1.11) can be replaced by a monotonic interpolation with multidimensional spline functions.

Our conjectured formula would imply, as a corollary, that any bipartite graph G = (X, Y; E) with |X| = |Y | = n has at most (n − 1)! perfect matchings (matchings covering every vertex of G), if for any partition of X into two nonempty blocks X′ and X′′ we have d_{G}^{+}(X′) ≤ n − 1 or d_{G}^{+}(X′′) ≤ n−1. This corollary can indeed be proved by induction on n. Moreover, if G really has those (n−1)! perfect matchings, then either there exists an x ∈ X such that d_{G}^{+}(X \{x}) = n−1 or G is isomorphic to C_{6}, a circle with 6 vertices.

Let us conclude this section with an easy example for exponential generating functions.

Example. Let D(n) be the number of fixed point free permutations of the set {1, 2, …, n} = X (or, equivalently, the number of possibilities to put n letters into n envelopes in such a way, that no letter will be in the correct envelope). In other words, D(n) is the number of perfect matchings of the complete bipartite graph K_{n,n} from which one perfect matching has been removed. This situation can be normalized with an additional vertex y ∈ Y of weight −1, which is not joined to any vertex of X, that is x_{G}(∅) = −1. Now our duality theorem for usual matchings in bipartite graphs proves D(n) = (−1)^{n}m_{G(−1,1)}^{−}(X), and the last proposition of Section 3 implies

∑_{n=0}^{∞} D(n) · \frac{X^{n}}{n!} = 1 + M_{G(−1,1)}^{−}(−χ) = (1 − X)^{−1} exp(−X),  (4.20)

one of the most classical results of enumerative combinatorics, which can be found in [1] or [24], for example.

5 Rook Theory

Let G = (X, Y; E) be a simple bipartite graph with |X| = n. We denote by G + z the graph obtained from G by adding to Y one vertex with the usual capacity z which is joined to every x ∈ X by an edge. Let G_{a} be a graph for which x_{G}(∅) has been chosen in such a way that

∑_{∅⊆X′⊆X} x_{G}(X′) = |X| + a.  (5.1)

Then our duality theorem for usual matchings in bipartite graphs implies the following lemma.

Lemma 4. We have

m_{\overline{G_{a}}+z}^{−}(X) = (−1)^{|X|}m_{G_{a}−z−a−1}^{−}(X).  (5.2)

We can define the factorial rook polynomial easily by

ρ!(G_{a}, z) := m_{G_{a}+z}^{−}(X) = ∑_{r=0}^{n} p(G_{a}, r)z\underline{n−r},  (5.3)

where z\underline{n−r} = z(z − 1)(z − 2) ⋯ (z − n + r + 1) and where p(G_{a}, r) denotes the number of r-matchings of G_{a}, p(G_{a}, 0) := 1. An r-matching is a set of r independent (i.e., mutually non adjacent) edges. Traditionally, one considers X and Y as rows and columns of a checkerboard so that r-matchings become placements of non-attacking rooks; see [5] for an introduction to rook theory. It is classical (see the book [22] by Riordan, chapter 7.7), that the numbers p(\overline{G_{a}}, r) are determined by the numbers p(G_{a}, r). No simple relation between them, however, has been found yet. Inspired by the definition of Chung and Graham’s cover polynomial [7], Chow (and Gessel) [6] have introduced our factorial rook polynomial, which proved already to be useful in the work of Foata and Schützenberger [9] on Ferrers relations, because in that case, it factorizes naturally (see [13] and Stanley’s book [24], theorem 2.4.1). Our preceding lemma implies the following duality relation for the factorial rook polynomial, which was imagined by Chow (and Gessel) [6] in the case a = 0.

Proposition 4. We have

ρ!(\overline{G_{a}}, z) = (−1)^{n}ρ!(G_{a}, −z − a − 1).  (5.4)

The classical rook polynomial can be found, for example, in Godsil’s book [11], chapter 1.3. We will define it as follows :

ρ(G_{a}, t) := ∑_{r=0}^{n}(−1)^{r}p(G_{a}, r)t^{n−r}.  (5.5)

Let G_{a}[X′] be the simple bipartite graph formed by the vertices of X′ (∅ ⊂ X′ ⊆ X), the edges of G incident with them and the second endpoints (in Y) of those edges. Our main theorem of Section 3, i.e. identity (3.8), implies the following lemma.

Lemma 5. We have

1 + ∑_{∅⊂X′⊆X} ρ(G_{a}[X′], t) · χ^{X′} = exp (t · X) · (1 + M_{G_{a}}^{−}(−χ))  (5.6)
= exp (t · X − D_{G_{a}}^{−}!(χ)) .  (5.7)

It allows us to prove the the last theorem of this article.

Theorem 8. We have

∫_{0}^{∞} t^{z+a} · e^{−t}ρ(G_{a}, t)dt = (−1)^{n}ρ!(G_{a}, −z − a − 1) · Γ(z + a + 1)  (5.8)
= ρ!(\overline{G_{a}}, z) · Γ(z + a + 1).  (5.9)

In particular, if a = −1, then ρ!(\overline{G_{−1}}, z)·Γ(z) = (−1)^{n}ρ!(G_{−1}, −z)·Γ(z) is the Mellin transform of e^{−t}ρ(G_{−1}, t).

Proof. The first identity can be proved easily with the algebra of set functions :

∫_{0}^{∞} t^{z+a}e^{−t} · exp (t · X) · (1 + M_{G_{a}}^{−}(−χ)) · dt

= (1 + M_{G_{a}}^{−}(−χ)) ∫_{0}^{∞} t^{z+a} exp (−t(1 − X)) dt

= (1 + M_{G_{a}}^{−}(−χ)) ∫_{0}^{∞} (\frac{s}{1 − X} )^{z+a} exp (−s) \frac{ds}{1 − X}

= (1 + M_{G_{a}}^{−}(−χ)) (1 − X)^{−z−a−1} ∫_{0}^{∞} s^{z+a}e^{−s}ds

= (1 + M_{G_{a}−z−a−1}^{−}(−χ)) · Γ(z + a + 1).  (5.10)

The second identity is nothing else but the preceding proposition.

The preceding theorem is closely related to results of [19]. Its special case a = z = 0 was found by Joni, Rota and Zeilberger [15], since ρ!(\overline{G_{0}}, 0) = m− ; \overline{G_{0}}(X) counts the number of perfect matchings of \overline{G_{0}}. This result makes it possible to interpret combinatorially integrals of products of generalized Laguerre polynomials; see [2, 3, 4, 8, 10, 11, 12, 14, 23, 26]. Following Godsil [11], we can define Laguerre polynomials as rook polynomials of complete bipartite graphs K_{n,m} := (X, Y; X × Y) with |X| = n and |Y | = m. More precisely, for every a ∈ ℕ we define

Le_{n}^{(a)}(t) := ρ(K_{n,n+a}, t).  (5.11)

Since ρ(K_{n,n+a} ⊎ K_{m+a,m}, t) = t^{a} · Le_{n}^{(a)}(t) · Le_{m}^{(a)}(t), the identity of Joni, Rota and Zeilberger implies that

ρ!(\overline{K_{n,n+a} ⊎ K_{m+a,m}}, 0) = ∫_{0}^{∞} Le_{n}^{(a)}(t) · Le_{m}^{(a)}(t) · t^{a}e^{−t}dt  (5.12)

(see [12]). This proves in particular the orthogonality of our polynomials Le_{n}^{(a)}(t) with respect to t^{a}e^{−t}dt. Therefore our definition of Laguerre polynomials corresponds to the classical definition. Our normalization, however, is chosen in such a way that the first coefficient (i.e. the coefficient of t^{n}) is equal to 1.

Acknowledgements: I should like to thank most cordially Eberhard Triesch, who has familiarized me with his very beautiful conjecture, which inspired all results of this article and many others. I am also grateful to D. Foata and G. Han for all their help and encouragement.

References

[1] M. Aigner, ”Combinatorial Theory”, Springer-Verlag, Heidelberg, 1979.

[2] R. Askey and G. Gasper, ”Convolution structures for Laguerre polynomials”, J. Analyse Math. 31 (1977), 48-68.

[3] R. Askey and M. Ismail, ”Permutation problems and special functions”, Canad. J. Math. 28 (1976), 853-874.

[4] R. Askey, M. Ismail and T. Koornwinder, ”Weighted permutation problems and Laguerre Polynomials”, J. Combin. Theory Ser. A 25 (1978), 277-287.

[5] F. Butler, M. Can, J. Haglund and J.B. Remmel, ”Rook Theory Notes”.

[6] T. Chow, ”A short proof of the rook reciprocity theorem”, Electronic J. Combin. 3 (1996), R10.

[7] F.R.K. Chung and R.L. Graham, ”On the cover polynomial of a digraph”, J. Combin. Theory Ser. B 65 (1995), 273-290.

[8] S. Even and J. Gillis, ”Derangements and Laguerre polynomials”, Math. Proc. Camb. Phil. Soc. 79 (1976), 135-143.

[9] D. Foata and M.-P. Schützenberger, ”On the rook polynomials of Ferrers relations”, in : Combinatorial Theory and its Applications, vol. 2 (P. Erdös, A. Renyi and V. T. Sós, eds.), Colloq. Math. Soc. János Bolyai 4 (1970), North-Holland, Amsterdam, 431-436.

[10] D. Foata and D. Zeilberger, ”Laguerre polynomials, weighted derangements and positivity”, SIAM J. Disc. Math. 1 (1988), 425-433.

[11] C.D. Godsil, ”Algebraic Combinatorics”, Chapman & Hall, 1993.

[12] C.D. Godsil, ”Hermite polynomials and a duality relation for matchings polynomials”, Combinatorica 1 (1981), 257-262.

[13] J.R. Goldman, J.T. Joichi and D.E. White, ”Rook theory I, Rook equivalence of Ferrers boards”, Proc. Amer. Math. Soc. 52 (1975), 485-492.

[14] D. M. Jackson, ”Laguerre polynomials and derangements”, Math. Proc. Camb. Phil. Soc. 80 (1976), 213-214.

[15] S.A. Joni and G.-C. Rota, ”A vector space analog of permutations with restricted position”, J. Combinatorial Theory, Series A 29 (1980), 59-73.

[16] B. Lass, ”Matching polynomials and duality”, Combinatorica 24 (2004), 427-440.

[17] B. Lass, ”Orientations acycliques et le polynôme chromatique”, European J. Combin. 22 (2001), 1101-1123.

[18] B. Lass, ”The N-dimensional matching polynomial”, Geom. Funct. Anal. 15 (2005), 453-475.

[19] B. Lass, ”Variations sur le thème E + \overline{E} = XY ”, Adv. in Appl. Math. 29 (2002), 215–242.

[20] B. Lass, ”The algebra of set functions I : The product theorem and duality”, preprint.

[21] H. Minc, ”Permanents”, Addison-Wesley, 1978.

[22] J. Riordan, ”An Introduction to Combinatorial Analysis”, Wiley, New York, 1958.

[23] M. de Sainte-Catherine and G. Viennot, ”Combinatorial interpretation of integrals of products of Hermite, Laguerre and Tchebycheff polynomials”, in : Polynômes orthogonaux et applications (C. Brezinski, et al., eds.), Bar-le-Duc, 1984, Lecture Notes in Mathematics 1175 (1985), Springer-Verlag, Berlin, 120-128.

[24] R.P. Stanley, ”Enumerative Combinatorics”, Volume 1, Cambridge University Press, Cambridge, 1997.

[25] E. Triesch, ”Conjectures on the uniqueness of Hamiltonian cycles and the number of perfect matchings”, Proceedings of the Fourth Prague Combinatorial Workshop (Martin Klazar, editor) KAM Series No. 97-339 (1997), 42-46.

[26] G. Viennot, ”Une théorie combinatoire des polynômes orthogonaux généraux”, Notes de conférences données à l’Université du Québec à Montréal, 1983.