The Algebra of Set Functions I : The Product Theorem and Duality

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

Abstract We give a comprehensive introduction to the algebra of set functions and its generating functions. This algebraic tool allows us to formulate and prove a product theorem for the enumeration of functions of many different kinds, in particular injective functions, surjective functions, matchings and colourings of the vertices of a hypergraph. Moreover, we develop a general duality theory for counting functions.

1 Introduction

The algebra of set functions has been briefly introduced in order to count matchings [3, 5, 6], colourings and acyclic orientations [4]. In this paper we want to study this algebra in a more systematic way. Ordinary and exponential generating functions have always been the favourite tool in enumerative combinatorics. Generating functions for set functions offer the same advantages and increase the range of applications. In fact, exponential generating functions operate on set functions, and it is even possible to work with derivatives of set functions. Combinatorial techniques like Möbius inversion are then replaced by standard algebraic operations. For example, the product rule for differentiation reflects the most fundamental set theoretic fact :

x ∈ X_{1} ⊎ X_{2}  ⇔  x ∈ X_{1} or x ∈ X_{2}.  (1.1)

Many applications of the algebra of set functions have their origin in a product theorem for the enumeration of functions. The basic idea is the following. If we have a function, then we can look at the preimage of every element of its codomain. This defines a partition of its domain into blocks. Moreover, the function is injective if and only if the size of every block of the partition of the domain is 0 or 1, and it is surjective if and only if no block is an empty set. Therefore, studying partitions of the domain makes it possible to count many kinds of functions, and this is what the algebra of set functions can do via the product theorem. It even works with multiplicative weights.

In Section 2 the basic theory of set functions is fully developed. Our fundamental result, namely the product theorem, is stated and proved in Section 3. The last part, Section 4, is devoted to a general “global” duality theory for the enumeration of functions. This theory does not use the “local” set functions and works with weights which just have to form an abelian group. Many applications to the enumeration of matchings in bipartite graphs will be given in the subsequent article [7].

2 The Algebra of Set Functions

In this article, A will always be a commutative ring with identity element. Usually, A is just the ring of integers ℤ, but it can also be the field of complex numbers ℂ or the ring of polynomials with complex coefficients ℂ[x].

Let us denote by ℕ the nonnegative integers. A sequence of numbers is exactly the same as a function f : ℕ → A. It is quite usual in enumerative combinatorics to associate with such a function a power series, namely

F_{f}(x) = ∑_{n=0}^{∞} f(n) · x^{n}  (ordinary generating function)  or  (2.1)

F_{f}(x) = ∑_{n=0}^{∞} f(n) · \frac{x^{n}}{n!}  (exponential generating function).  (2.2)

In this way, the functions f : ℕ → A become an A-module. More precisely, for any f, g : ℕ → A, we can define the sum f + g : ℕ → A with the help of the generating functions : F_{f+g}(x) = F_{f}(x) + F_{g}(x). Of course, it was not necessary to use generating functions for this. We could have defined directly (f +g)(n) = f(n)+g(n) for every n ∈ ℕ. In the same way, for any element of our commutative ring a ∈ A and any function f : ℕ → A, we can define a · f : ℕ → A either with the help of the generating functions : F_{a·f}(x) = a · F_{f}(x) or directly : (a · f)(n) = a · f(n). Last but not least, working with generating functions turns the functions f : ℕ → A into an algebra. Indeed, we can define the product f · g : ℕ → A of two functions f, g : ℕ → A by F_{f·g}(x) = F_{f}(x) · F_{g}(x), but here we must pay attention. This definition means

(f · g)(n) = ∑_{k=0}^{n} f(k) · g(n − k)  for ordinary generating functions  but (2.3)

(f · g)(n) = ∑_{k=0}^{n} \binom{n}{k} · f(k) · g(n − k)  for exponential generating functions. (2.4)

In other words, the algebra structure of number sequences depends on the generating functions that we work with. In enumerative combinatorics, however, number sequences are not the only interesting objects. We have seen already in the introduction that set functions appear naturally. Therefore we want to study their algebra structure carefully.

Let X be a finite set of cardinality n. We denote by 2^{X} the family of finite subsets of X, which has of course cardinality 2^{n}. Let F(2^{X}, A) be the A-algebra of set functions f, g : 2^{X} → A, equipped with the multiplication

(f · g)(X′) = ∑_{X_{1}⊎X_{2}=X′} f(X_{1}) · g(X_{2})  ∀ ∅ ⊆ X′ ⊆ X  (2.5)

(where ⊎ denotes disjoint union) and the obvious pointwise addition (f +g)(X′) = f(X′)+g(X′) and scalar multiplication (a · f)(X′) = a · f(X′) for every ∅ ⊆ X′ ⊆ X and for every a ∈ A.

Next let A[X] be the A-algebra of multiaffine (= square-free) polynomials

F (χ) = ∑_{X′⊆X} a_{X′} · χ^{X′},  a_{X′} ∈ A ∀ ∅ ⊆ X′ ⊆ X  (2.6)

in the n indeterminates χ = (χ_{x})_{x∈X}, where we use the shorthand notation

χ^{X′} = ∏_{x∈X′} χ_{x},  χ^{∅} := 1.  (2.7)

This algebra is equipped with the usual multiplication of polynomials followed by extraction of the multiaffine part (i.e. discarding all monomials that are not of the form χ^{X′} for some X′ ⊆ X), that is

( ∑_{X′⊆X} a_{X′} · χ^{X′} ) · ( ∑_{X′⊆X} b_{X′} · χ^{X′} ) = ∑_{X′⊆X} ∑_{X_{1}⊎X_{2}=X′} a_{X_{1}}b_{X_{2}} · χ^{X′},  (2.8)

together with the usual addition and scalar multiplication. Note that A[X] is isomorphic in an obvious way to the quotient algebra A[{χ_{x}}]/⟨{χ_{x}^{2}}⟩. Remark. In a more combinatorial way, we could have defined the multiplication of monomials for all X_{1}, X_{2} ⊆ X by

χ^{X_{1}} · χ^{X_{2}} := χ^{X_{1}+X_{2}}, where  (2.9)
X_{1} + X_{2} := \{ \begin{matrix}X_{1} ∪ X_{2}, & if X_{1} ∩ X_{2} = ∅, \\ †, & if X_{1} ∩ X_{2} ≠ ∅, where \end{matrix}  (2.10)
† + X′ := †, † + † := †,  and  χ^{†} := 0.  (2.11)

Here † corresponds to multisets that are systematically discarded.

Finally, the map f ↦ F_{f} that associates the generating polynomial F_{f} ∈ A[X] with each set function f ∈ F(2^{X}, A), i.e.

F_{f}(χ) = ∑_{X′⊆X} f(X′) · χ^{X′},  (2.12)

is manifestly an algebra isomorphism of F(2^{X}, A) onto A[X]. In other words, we have F_{f·g}(χ) = F_{f}(χ) · F_{g}(χ), F_{f+g}(χ) = F_{f}(χ) + F_{g}(χ) and F_{a·f}(χ) = a · F_{f}(χ) for every f, g ∈ F(2^{X}, A) and for all a ∈ A. Many applications of our algebra of set functions A[X] in different parts of enumerative graph theory can be found in [3], [4], [5] and [6].

For |X| = ∞ let (2^{X})_{fin} be the partially ordered set of all finite subsets of X. We have the canonical projections p_{X_{1},X_{2}} : A[X_{1}] → A[X_{2}] (X_{1}, X_{2} ∈ (2^{X})_{fin}, X_{1} ⊇ X_{2}) and define

A[X] := lim_{⟵} A[X′], X′ ∈ (2^{X})_{fin}  (2.13)

with the help of the projective limit. This means nothing else than working with generating functions of the form

F (χ) = ∑_{X′∈(2^{X})_{fin}} a_{X′} · χ^{X′},  a_{X′} ∈ A ∀ ∅ ⊆ X′ ⊆ X.  (2.14)

Now for any X (finite or infinite), we consider the particular element

X := ∑_{x∈X} χ^{{x}} = ∑_{x∈X} χ_{x}  (2.15)

in A[X] : it is the generating function for the indicator function of the subsets of X of cardinality 1. Then, in the product X^{k} in the algebra A[X], each set of cardinality k occurs k! times, so X^{k}/k! is the generating function for the indicator function of the subsets of X of cardinality k. If now g : ℕ → A is an A-valued function on the natural numbers, the identity

∑_{k=0}^{∞} g(k) · \frac{X^{k}}{k!} = ∑_{X′∈(2^{X})_{fin}} g(|X′|) · χ^{X′}  (2.16)

provides an embedding of the algebra A![[X]] of generating functions of exponential type (usually the variable is called x instead of X) into our algebra A[X] if and only if |X| = ∞. Simply remark that if k > |X|, then X^{k}/k! = 0. If |X| = ∞, the image of this embedding is the subalgebra of A[X] consisting of all generating functions F_{f} of set functions f, where the value depends only on the cardinality of the set, i.e. f(X′) = g(|X′|) for every X′ ∈ (2^{X})_{fin}. This embedding is at the origin of (almost?) all the applications of A![[X]] in combinatorics, but it requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, A[X] provides more flexibility and closeness to combinatorics; it is also ideally suited for computer calculations. Remark. The ring ℤ![[X]] is not noetherian, but it contains the important functions exp(X) and log(1 + X).

Example. If char A = 2, then we have

(1 + X)^{−1} = ∑_{k=0}^{∞}(−1)^{k}k! · \frac{X^{k}}{k!}  (2.17)
≡ 1 + X and  (2.18)
log(1 + X) = ∑_{k=1}^{∞}(−1)^{k−1}(k − 1)! · \frac{X^{k}}{k!}  (2.19)

≡ X + \frac{X^{2}}{2}  (2.20)

in the ring A![[X]]. These identities are at the origin of lots of results on parity in combinatorics; see [6].

For all t ∈ A let (t · χ)^{X′} := t^{|X′|} · χ^{X′}, X′ ∈ (2^{X})_{fin}, and therefore

F_{f}(t · χ) = ∑_{X′∈(2^{X})_{fin}} f(X′) t^{|X′|} · χ^{X′},  (2.21)

where f : (2^{X})_{fin} → A is an arbitrary set function. It is evident that this definition is compatible with the addition and the multiplication, in particular (t · χ)^{X_{1}} · (t · χ)^{X_{2}} = (t · χ)^{X_{1}+X_{2}}. Most important are the special cases t = −1 and t = 0: F_{f}(0) = F_{f}(0 · χ) = f(∅).

We define the degree of a set function f : (2^{X})_{fin} → A by

deg F_{f}(χ) := min{n ∈ ℕ | ∃ X′ ∈ (2^{X})_{fin} such that |X′| = n and f(X′) ≠ 0},  (2.22)

where the minimum over an empty set is ∞, that is, the set function which is zero for every subset of X has the degree ∞. Our definition implies deg (χ^{X_{1}} · χ^{X_{2}}) ≥ deg (χ^{X_{1}}) + deg (χ^{X_{2}}) and, more generally,

deg (F_{f}(χ) · F_{g}(χ)) ≥ deg (F_{f}(χ)) + deg (F_{g}(χ))  (2.23)

for arbitrary f, g : (2^{X})_{fin} → A. It is interesting to remark that these inequalities are not satisfied for other natural definitions of X_{1} + X_{2} such as X_{1} + X_{2} = X_{1} ∪ X_{2}.

If F_{f}(0) = f(∅) = 0, i.e. deg(F_{f}(χ)) ≥ 1, then deg(F_{f}(χ)^{k}) ≥ k for every k ∈ ℕ. Moreover, F_{f}(χ)^{k}/k! is defined for any ring A, because a partition into k nonempty subsets can be ordered in k! different ways. Thus, we have an operation of A![[X]] on A[X] via the substitution G(F_{f}(χ)) defined for any G ∈ A![[X]] (all calculations in A are finite). The following proposition is now easy to prove.

Proposition 1. The set function F_{f}(χ) is invertible if and only if F_{f}(0) = f(∅) is invertible. In that case F_{f}(χ)^{−1} = F_{f^{−1}}(χ), where f^{−1} : (2^{X})_{fin} → A can be calculated recursively by using f^{−1}(∅) = f(∅)^{−1} and

f^{−1}(X′) = f(∅)^{−1} · (− ∑_{∅⊂X′′⊆X′} f(X′′) · f^{−1}(X′ \ X′′))  (2.24)

for all ∅ ⊂ X′ ⊆ X. Moreover, if F_{g}(0) = g(∅) = 0, then the inverse of 1 + F_{g}(χ) can also be calculated by substituting F_{g}(χ) into (1 + X)^{−1}, that is

(1 + F_{g}(χ))^{−1} = ∑_{k=0}^{∞}(−1)^{k}k! · \frac{F_{g}(χ)^{k}}{k!} .  (2.25)

If char A = 2, this reduces to (1 + F_{g}(χ))^{−1} ≡ 1 + F_{g}(χ).

Example. For two set functions f, g : (2^{X})_{fin} → A we have the following equivalence :

F_{g}(χ) = exp(X) · F_{f}(χ)  ⇔  F_{f}(χ) = exp(−X) · F_{g}(χ).  (2.26)

In other words,

g(X′) = ∑_{X′′⊆X′} f(X′′)  ∀ X′ ∈ (2^{X})_{fin}  ⇔
f(X′) = ∑_{X′′⊆X′}(−1)^{|X′\X′′|}g(X′′)  ∀ X′ ∈ (2^{X})_{fin}.  (2.27)

This is nothing else than the famous inclusion-exclusion principle, also known as the sieve principle.

Finally, for every x ∈ X, we use the derivatives ∂^{x} defined by

∂^{x} χ^{X′} := \{ \begin{matrix}χ^{X′}, & if x ∈ X′, \\ 0, & otherwise. \end{matrix}  (2.28)

The product rule

∂^{x} (F_{f}(χ) · F_{g}(χ)) = (∂^{x}F_{f}(χ)) · F_{g}(χ) + F_{f}(χ) · (∂^{x}F_{g}(χ))  (2.29)

is the algebraic analogue of the most fundamental set theoretic fact:

x ∈ X_{1} ⊎ X_{2}  ⇔  x ∈ X_{1} or x ∈ X_{2}.  (2.30)

In this way, combinatorial arguments where two cases have to be distinguished can be replaced by differential calculus. The product rule immediately implies that ∂^{x} (F_{f}(χ))^{n} = n·(F_{f}(χ))^{n−1}· ∂^{x}F_{f}(χ), i.e., it implies the chain rule :

∂^{x} (G(F_{f}(χ))) = G′(F_{f}(χ)) · ∂^{x}F_{f}(χ), G ∈ A![[X]].  (2.31)

Remark. Under the algebra isomorphism A[X] ≃ A[{χ_{x}}]/⟨{χ_{x}^{2}}⟩, ∂^{x} does not correspond to ∂/∂χ_{x}, but to χ_{x} · ∂/∂χ_{x}. The partial derivative ∂/∂χ_{x} cannot be defined in A[X].

For any weight function w : X → A, we can also use the differential operator

∂_{w} := ∑_{x∈X} w(x) · ∂^{x},  (2.32)

which is the general form of a differential operator for which the product rule is satisfied. In particular, if w(x) = 1 for every x ∈ X, we let ∂_{w} = ∂. This means that

∂F_{f}(χ) = \frac{d}{dt}F_{f}(t · χ)|_{t=1} = ∑_{∅⊆X′⊆X} f(X′) · |X′| · χ^{X′}.  (2.33)

If now g : ℕ → A is an A-valued function on the natural numbers, then

∂ ∑_{k=0}^{∞} g(k) · \frac{X^{k}}{k!} = ∑_{k=0}^{∞} g(k) · k · \frac{X^{k}}{k!} = X \frac{d}{dX} ∑_{k=0}^{∞} g(k) · \frac{X^{k}}{k!} .  (2.34)

It is remarkable that Pólya and Szegö [8] introduce X \frac{d}{dX} as “the” differential operator for power series. Example. For two set functions f, g : (2^{X})_{fin} → A with f(∅) = g(∅) = 0 we have the following equivalence :

1 + F_{g}(χ) = exp (F_{f}(χ))  ⇔  F_{f}(χ) = log (1 + F_{g}(χ)) .  (2.35)

In other words,

g(X′) = ∑_{k=1}^{∞} ∑_{B_{1}⊎···⊎B_{k}=X′} ∏_{i=1}^{k} f(B_{i})  ∀X′ ∈ (2^{X})_{fin} \ ∅  ⇔

f(X′) = ∑_{k=1}^{∞}(−1)^{k−1}(k − 1)! ∑_{B_{1}⊎···⊎B_{k}=X′} ∏_{i=1}^{k} g(B_{i})  ∀X′ ∈ (2^{X})_{fin} \ ∅. (2.36)

This is nothing else than Möbius inversion for the lattice of partitions, for generalized multiplicative functions (i.e. the value on a partition is the product of the values on its blocks; but the latter may depend on the block and not just on its cardinality; see [1], chapter V.1.C, and [2], chapter 5.2). Our equivalence 2.35 can be continued :

F_{f}(χ) = log (1 + F_{g}(χ))  (2.37)
⇔  ∂^{x}F_{f}(χ) = ∂^{x} log (1 + F_{g}(χ))  ∀ x ∈ X (2.38)
⇔  (1 + F_{g}(χ)) · ∂^{x}F_{f}(χ) = ∂^{x}F_{g}(χ)  ∀ x ∈ X  (2.39)
⇔  f(X′) + ∑_{x∈X′′⊂X′} f(X′′)g(X′ \ X′′) = g(X′)  ∀ x ∈ X′ ⊆ X.  (2.40)

If char A = 0, then we also get the equivalences

F_{f}(χ) = log (1 + F_{g}(χ))  (2.41)
⇔  ∂F_{f}(χ) = ∂ log (1 + F_{g}(χ))  (2.42)
⇔  (1 + F_{g}(χ)) · ∂F_{f}(χ) = ∂F_{g}(χ)  (2.43)
⇔  |X′|f(X′) + ∑_{∅⊂X′′⊂X′} |X′′|f(X′′)g(X′ \ X′′) = |X′|g(X′) ∀ ∅ ⊂ X′ ⊆ X. (2.44)

All those equivalences have the great advantage that they use just one single product of set functions. This is particularly useful for calculating the logarithm of a set function by computer.

3 The Product Theorem for Counting Functions

For finite sets X and Y let T be a family of functions t : X′ → Y′, X′ ⊆ X, Y′ ⊆ Y. In order to evaluate the number of those functions, we consider a partition Y′ = Y_{1} ⊎ Y_{2}, which induces a partition of X′ via t, namely X′ = t^{−1}(Y_{1}) ⊎ t^{−1}(Y_{2}). Definition. The family of functions T is called partitionable if the following conditions are satisfied :

a) For every t ∈ T, t : X′ → Y′, and Y′ = Y_{1} ⊎ Y_{2}, the two functions t|_{t^{−1}(Y_{1})} : t^{−1}(Y_{1}) → Y_{1} and t|_{t^{−1}(Y_{2})} : t^{−1}(Y_{2}) → Y_{2} also belong to the family T.

b) For any t_{1}, t_{2} ∈ T, t_{1} : X_{1} → Y_{1}, t_{2} : X_{2} → Y_{2}, with X_{1} ∩ X_{2} = Y_{1} ∩ Y_{2} = ∅, there exists exactly one t ∈ T, t : X_{1} ∪ X_{2} → Y_{1} ∪ Y_{2} such that t|_{X_{1}} = t_{1} and t|_{X_{2}} = t_{2}.

In particular, there is exactly one t_{0} ∈ T: t_{0} : ∅ → ∅, and there are no further functions of the form t : X′ → ∅. Moreover, there is exactly one function of the form t : ∅ → Y′ if every y ∈ Y′ can have an empty preimage; if one y ∈ Y′ has to have a nonempty preimage, then there is no function t : ∅ → Y′.

From now on, we will only make use of partitionable families of functions. This is not very restrictive as can be seen in the following proposition.

Proposition 2. The family of surjective functions is partitionable, the family of injective functions is partitionable, and the family of bijective functions is partitionable. If G = (X, Y; E) is a bipartite graph, then the family of functions respecting its edges (that is (x, t(x)) must always be an edge of G) is also partitionable. If a hypergraph is defined on X (its so-called hyperedges form just a family of subsets of X) and if Y is considered as a set of colours, then colourings of X′ using colours of Y′ without monochromatic hyperedges are partitionable. Moreover, the intersection of two partitionable families of functions is also partitionable.

Proof. It is sufficient to verify that for any t_{1} : X_{1} → Y_{1}, t_{2} : X_{2} → Y_{2} with X_{1}∩X_{2} = Y_{1}∩Y_{2} = ∅, and t : X_{1} ∪ X_{2} → Y_{1} ∪ Y_{2} with t|_{X_{1}} = t_{1} and t|_{X_{2}} = t_{2}, we have the following equivalences :

The function t is surjective if and only if t_{1} and t_{2} are surjective. The function t is injective if and only if t_{1} and t_{2} are injective. The function t is bijective if and only if t_{1} and t_{2} are bijective. The function t respects the edges of a bipartite graph G = (X, Y; E) if and only if t_{1} and t_{2} respect its edges. The function t is a colouring without monochromatic hyperedges if and only if t_{1} and t_{2} are colourings of this type.

Let T be a partitionable family of functions. If we want to count all t : X′ → Y′ with X′ ⊆ X, Y′ ⊆ Y and t ∈ T, then we can fix a partition Y′ = Y_{1} ⊎ Y_{2}. Next, for all partitions X′ = X_{1} ⊎ X_{2}, we just have to count the number of functions t_{1} : X_{1} → Y_{1} with t_{1} ∈ T and the number of functions t_{2} : X_{2} → Y_{2} with t_{2} ∈ T. If we multiply the two results and sum over all partitions X′ = X_{1} ⊎ X_{2} we get exactly the desired result. Therefore, for every Y′ ⊆ Y, we define the set function

T^{Y′}(χ) := ∑_{∅⊆X′⊆X} |{t ∈ T |t : X′ → Y′}| · χ^{X′}.  (3.1)

The argument that we have just presented proves now the following lemma.

Lemma 1. For finite sets X and Y let T be a partitionable family of functions t : X′ → Y′, X′ ⊆ X, Y′ ⊆ Y. Then, for any partition Y′ = Y_{1} ⊎ Y_{2} we have the following identity :

T^{Y′}(χ) = T^{Y_{1}}(χ) · T^{Y_{2}}(χ).  (3.2)

If we apply our lemma several times, we get the main theorem of this section.

Theorem 1. (Product Theorem) For finite sets X and Y, let T be a partitionable family of functions t : X′ → Y′, X′ ⊆ X, Y′ ⊆ Y. Then for any Y′ ⊆ Y the following identity holds :

T^{Y′}(χ) = ∏_{y∈Y′} T^{{y}}(χ).  (3.3)

In particular,

T^{∅}(χ) = 1  and  T^{Y′}(0) = ∏_{y∈Y′} T^{{y}}(0).  (3.4)

For any y ∈ Y and X′ ⊆ X the coefficient of χ^{X′} in T^{{y}}(χ) is 1 if t : X′ → {y} belongs to T and 0 otherwise. Those coefficients determine a family of partitionable functions uniquely.

Example. If T is the family of injective functions, then T^{{y}}(χ) = 1 + X because a function is injective if and only if the preimage of every y ∈ Y is either the empty set or a one-element subset of X. Therefore, the product theorem implies

T^{Y} (χ) = ∏_{y∈Y} T^{\{y\}}(χ) = (1 + X)^{|Y |} = ∑_{k=0}^{|X|} \binom{|Y |}{k}X^{k} = ∑_{k=0}^{|X|} |Y |\underline{k} · \frac{X^{k}}{k!} ,  (3.5)

where |Y |\underline{k} = |Y |(|Y | − 1)(|Y | − 2) ⋯ (|Y | − k + 1) by definition. The coefficient of χ^{X} in T^{Y} (χ) counts the number of injective functions from X to Y. It is equal to |Y |\underline{|X|} = |Y |(|Y | − 1)(|Y | − 2) ⋯ (|Y | − |X| + 1), as expected.

Definition. A weight function w : T → A is called multiplicative if for every t : X′ → Y′, (X′ ⊆ X, Y′ ⊆ Y, t ∈ T) and Y′ = Y_{1} ⊎ Y_{2} we have

w(t) = w(t|_{t^{−1}(Y_{1})}) · w(t|_{t^{−1}(Y_{2})}),  (3.6)

where t|_{t^{−1}(Y_{1})} : t^{−1}(Y_{1}) → Y_{1}, t|_{t^{−1}(Y_{2})} : t^{−1}(Y_{2}) → Y_{2}, and in particular w(t_{0}) = 1 for t_{0} : ∅ → ∅.

Example. If a hypergraph is defined on X (its so-called hyperedges form just a family of subsets of X) and if Y is considered as a set of colours, we can study colourings c : X′ → Y′ with X′ ⊆ X and Y′ ⊆ Y. Let m(c) be the number of monochromatic hyperedges in X′. Then, for every a ∈ A (or for a variable a), w(c) = a^{m(c)} is a multiplicative weight function.

In the same spirit as previously, for every Y′ ⊆ Y, let us define the set function

T_{w}^{Y′}(χ) := ∑_{∅⊆X′⊆X} ( ∑_{t:X′→Y′, t∈T} w(t)) · χ^{X′}  (3.7)

(in the unweighted case, the weight of every function from T was 1). Then, we get again a product theorem.

Theorem 2. (Weighted Product Theorem) For finite sets X and Y let T be a partitionable family of functions t : X′ → Y′, X′ ⊆ X, Y′ ⊆ Y and let w : T → A be a multiplicative weight function. Then, for any Y′ ⊆ Y the following identity holds :

T_{w}^{Y′}(χ) = ∏_{y∈Y′} T_{w}^{{y}}(χ).  (3.8)

In particular,

T_{w}^{∅}(χ) = 1  and  T_{w}^{Y′}(0) = ∏_{y∈Y′} T_{w}^{{y}}(0).  (3.9)

Without loss of generality, it is possible in the weighted case to take for T the partitionable family of all functions t : X′ → Y′, as functions which do not belong to the original T can just get the weight 0.

On the other hand, if we choose for every y ∈ Y an arbitrary set function T_{w}^{{y}}(χ) ∈ A[X] and if we consider the previous theorem as a definition, then we automatically get a partitionable family of functions with a multiplicative weight function. This situation is characterized by the fact that, for every y ∈ Y, we can choose independently which subsets X′ ⊆ X may be mapped to y and what kind of weight we want to use for every X′ ⊆ X.

In that case, T_{w}^{Y′}(χ) counts functions to Y′ in such a way that every y ∈ Y′ contributes a multiplication with the coefficient of χ^{t^{−1}{y}} in T_{w}^{{y}}(χ). In particular, every y ∈ Y′ that is not in the image of t contributes a multiplication with T_{w}^{{y}}(0). Therefore T_{w}^{Y′}(χ) counts weighted surjective functions to Y′ ⊆ Y if T_{w}^{{y}}(0) = 0 for every y ∈ Y. If T_{w}^{{y}}(0) = 1 for every y ∈ Y, then T_{w}^{Y′}(χ) counts arbitrary weighted functions to Y′.

4 Duality for the Enumeration of Functions

For finite sets X and Y let T be a set of functions t : X → Y, and let w : T → A be a weight function. In this section, A need not be a ring : it is sufficient to have an abelian group. Without loss of generality, we can (and will) assume that T is the set of all the |Y |^{|X|} possible functions t : X → Y, because functions which did not belong to the original T can just get the weight 0.

If |X| = 1, then we have |Y | different functions and therefore |Y | weights. Those weights can be considered as a vector with |Y | elements from our abelian group A. Let s be the sum of those |Y | weights. It is possible, in a unique way, to find one additional element of A, namely −s, and to form a vector with |Y | + 1 elements, namely our original |Y | weights and the additional weight, in such a way that the sum of all the weights of our new vector of length |Y |+1 equals 0.

This completely trivial observation becomes more interesting if |X| = 2. In that case, we have |Y |^{2} different functions and therefore |Y |^{2} weights forming a matrix of size |Y | × |Y |. Now it is possible, in a unique way, to add exactly one row and one column to our matrix in order to get a matrix of size (|Y | + 1) × (|Y | + 1) with the property that every row sum and every column sum of it equals 0. This is still almost trivial, but already a little bit tricky for the element which is both in the new row and in the new column. This element, however, has to be equal to the sum of all elements of our original matrix of size |Y | × |Y |.

If |X| = 3, our weights form a cube of size |Y | × |Y | × |Y |, which can be embedded uniquely in a cube of size (|Y | + 1) × (|Y | + 1) × (|Y | + 1) in such a way that the sum of the elements of every row, every column and every pillar becomes 0, etc. We want to formalize those ideas rigorously in the language of functions. Definition. The pair (T, w) is called normal if for every x ∈ X and for every test function t^{∗} : X \ {x} → Y we have

∑ ; t : X → Y, t|_{X\{x}} = t^{∗} w(t) = 0.  (4.1)

Usually, (T, w) is not normal, but we have the following proposition.

Proposition 3. The pair (T, w) can be normalized in a unique way by adding one new element y to the set Y. Thereby the function t′ : X → Y ∪ {y} gets the weight

w(t′) = (−1)^{|t^{′−1}(y)|} ∑ ; t : X → Y, t|_{t^{′−1}(Y)} = t′|_{t^{′−1}(Y)} w(t).  (4.2)

Proof. If we choose the weights according to the preceding formula, then the situation becomes normal : for every test function t^{∗} : X \ {x} → Y ∪ {y} we get

∑ ; t′ : X → Y ∪ {y}, t′|_{X\{x}} = t^{∗} w(t′)

= ∑ ; t′ : X → Y ∪ {y}, t′|_{X\{x}} = t^{∗}, t′(x) ∈ Y w(t′) +

∑ ; t′ : X → Y ∪ {y}, t′|_{X\{x}} = t^{∗}, t′(x) = y w(t′)

= (−1)^{|t^{∗}^{−1}(y)|} ∑ ; t : X → Y, t|_{t^{∗}^{−1}(Y)} = t^{∗}|_{t^{∗}^{−1}(Y)} w(t) +

(−1)^{|t^{∗}^{−1}(y)∪{x}|} ∑ ; t : X → Y, t|_{t^{∗}^{−1}(Y)} = t^{∗}|_{t^{∗}^{−1}(Y)} w(t)

= 0,  (4.3)

as desired. On the other hand, if we want to have normality, we must choose the weights as indicated in the proposition. This can be proved easily by induction on |t^{′−1}(y)|. The basis |t^{′−1}(y)| = 0 is evident. But if x ∈ t^{′−1}(y), the normality and the inductive hypothesis imply

w(t′) = − ∑ ; t′′ : X → Y ∪ {y}, t′′|_{X\{x}} = t′|_{X\{x}}, t′′(x) ∈ Y w(t′′)

= (−1)^{|t^{′−1}(y)|} ∑ ; t : X → Y, t|_{t^{′−1}(Y)} = t′|_{t^{′−1}(Y)} w(t).  (4.4)

Now choose for every x ∈ X some Y_{x} ⊆ Y and join x to every y ∈ Y_{x} by an edge. The bipartite graph obtained in this way will be denoted by G = (X, Y; E). If for some x ∈ X we choose the set Y \ Y_{x} instead of Y_{x}, then, instead of G, we obtain its partial complement denoted by C_{x}(G). In general, for any X′ ⊆ X, we can define the complement C_{X′}(G) with respect to X′ by replacing, for every x ∈ X′, the set Y_{x} by Y \ Y_{x}. It is evident that for all X′, X′′ ⊆ X we have C_{X′}(C_{X′′}(G)) = C_{X′△X′′}(G), where △ denotes the symmetric difference of two sets. Naturally, C_{∅}(G) = G and C_{X}(G) = \overline{G}, where \overline{G} is called the bipartite complement of G. Finally, we define W (T, w, G) as the weighted number of functions from T which respect the edges of G, that is

W (T, w, G) = ∑ ; t : X → Y, t(x) ∈ Y_{x} ∀x ∈ X w(t).  (4.5)

Let us suppose that (T, w) is normal, and let us fix some x ∈ X. If we sum, for every test function t^{∗} : X \ {x} → Y respecting the edges of G the condition of normality (see the previous definition), then we get the relation W (T, w, G)+W (T, w, C_{x}(G)) = 0. This proves the following theorem.

Theorem 3. (Duality Theorem) Let (T, w) be normal. Then, for every x ∈ X,

W (T, w, C_{x}(G)) = −W (T, w, G).  (4.6)

More generally, for any X′ ⊆ X,

W (T, w, C_{X′}(G)) = (−1)^{|X′|}W (T, w, G),  (4.7)

and in particular,

W (T, w, \overline{G}) = (−1)^{|X|}W (T, w, G).  (4.8)

Remark. On the other hand, if t^{∗} : X \ {x} → Y is a test function and if for G we choose the graph which has the |X| − 1 edges (x′, t^{∗}(x′)) with x′ ∈ X \ {x}, then the equation W (T, w, C_{x}(G)) = −W (T, w, G) implies the normality condition (see the preceding definition).

Acknowledgements: I am grateful to D. Foata and G. Han for all their help and encouragement.

References

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

[2] P. Doubilet, G.-C. Rota and R. Stanley, ”On the foundations of combinatorial theory (VI)”, in : Proceedings of the Sixth Berkely Symposium on Mathematical Statistics and Probability, v. II, University of California Press, Berkeley, 1972, 267-318.

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

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

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

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

[7] B. Lass, ”The algebra of set functions II : An enumerative analogue of Hall’s theorem for bipartite graphs”, preprint.

[8] G. Pólya and G. Szegö, ”Problems and Theorems in Analysis I, Series, integral calculus, theory of functions”, Springer-Verlag, Berlin, 1978.