Séminaire Lotharingien de Combinatoire 54 (2006), Article B54b

SYMMETRIC INCLUSION-EXCLUSION

Ira M. Gessel^{∗}

Department of Mathematics, MS 050 Brandeis University Waltham, MA 02454-9110

                   gessel@brandeis.edu

Abstract. One form of the inclusion-exclusion principle asserts that if A and B are functions of finite sets then the formulas A(S) = ∑_{T ⊆S} B(T) and B(S) = ∑_{T ⊆S}(−1)^{|S|−|T |}A(T) are equivalent. If we replace B(S) by (−1)^{|S|}B(S) then these formulas take on the symmetric form

A(S) = ∑_{T ⊆S}(−1)^{|T |}B(T)
B(S) = ∑_{T ⊆S}(−1)^{|T |}A(T).

which we call symmetric inclusion-exclusion. We study instances of symmetric inclusion-exclusion in which the functions A and B have combinatorial or probabilistic interpretations. In particular, we study cases related to the Pólya-Eggenberger urn model in which A(S) and B(S) depend only on the cardinality of S.

1. Inclusion-exclusion

Let A and B be two functions defined on a set D of finite sets. We assume that if S ∈ D and T ⊆ S then T ∈ D. Then the inclusion-exclusion principle asserts that the following are equivalent:

\begin{aligned}A(S) & = ∑_{T ⊆S} B(T). \\ B(S) & = ∑_{T ⊆S}(−1)^{|S|−|T |}A(T). \end{aligned}  (1)

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05A19, 60C05. Key words and phrases. inclusion-exclusion, Pólya-Eggenberger urn model, hypergeometric series. ∗Partially supported by NSF Grant DMS-0200596.

The special case in which A(S) and B(S) depend only on |S| is especially important: for two sequences (A_{n}) and (B_{n}), the following are equivalent:

\begin{aligned}A_{n} & = ∑_{k=0}^{n} \binom{n}{k}B_{k} \\ B_{n} & = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}A_{k} \end{aligned}  (2)

It is very easy to find pairs of functions with combinatorial interpretations that satisfy (1): we may choose B to be an arbitrary function with a combinatorial interpretation. Then since (1) expresses A in terms of B with positive coefficients, A will also have a combinatorial interpretation. Similarly, it is easy to find instances of (2) with combinatorial interpretations.

In terms of exponential generating functions, (2) gives the familiar formulas

\begin{aligned}F_{A}(x) & = e^{x}F_{B}(x) \\ F_{B}(x) & = e^{−x}F_{A}(x), \end{aligned}

where

F_{A}(x) = ∑_{n=0}^{∞} A_{n} \frac{x^{n}}{n!} and F_{B}(x) = ∑_{n=0}^{∞} B_{n} \frac{x^{n}}{n!} .

Now in (1), let us replace B(T) with (−1)^{|T |}β(T) and A(S) with α(S), and multiply the second equation by (−1)^{|S|}. We obtain

\begin{aligned}α(S) & = ∑_{T ⊆S}(−1)^{|T |}β(T) \\ β(S) & = ∑_{T ⊆S}(−1)^{|T |}α(T). \end{aligned}  (3)

The corresponding substitution in (2) gives

\begin{aligned}α_{n} & = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}β_{k} \\ β_{n} & = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}α_{k}. \end{aligned}  (4)

In terms of exponential generating functions, (4) is the unfamiliar-looking

\begin{aligned}F_{α}(x) & = e^{x}F_{β}(−x) \\ F_{β}(x) & = e^{x}F_{α}(−x) \end{aligned}  (5)

We will call functions or sequences A and B that satisfy (1) and (2) asymmetric inclusion-exclusion pairs and we will call instances of (3) and (4) symmetric inclusionexclusion pairs. The goal of this paper is to study symmetric inclusion-exclusion pairs with combinatorial or probabilistic interpretations. We shall see that for the case in which the domain of the functions α and β in (3) is the set of subsets of a finite set, or if the sequences (α_{n}) and (β_{n}) in (4) are finite (i.e., α_{n} and β_{n} are defined only for n ≤ N, for some N), there is a very simple construction of symmetric inclusionexclusion pairs analogous to starting with an arbitrary function B in (1) or with an arbitrary sequence (B_{n}) in (2). We also give a very simple probabilistic setting for (3) in which the cardinalities of the sets in the domain of α and β are unbounded. Finding a probabilistic interpretation of (4) with infinite sequences does not seem so straightforward. We discuss some examples, related to the Pólya-Eggenberger urn model, of infinite sequences satisfying (4), but we have not found a general theory of such sequences.

2. Difference Tables

There is a close connection between asymmetric inclusion-exclusion pairs and symmetric inclusion-exclusion pairs. We illustrate with the special case of the derangement numbers. We take A_{n} = n!, so B_{n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}k! is the nth derangement number. We can compute B_{n} from A_{n} by using a difference table, in which the numbers A_{n} = n! appear in the zeroth row and each number in a row below the zeroth row is the number above it to the right minus the number above it to the left.

1  1  2  6 24 120
0  1  4 18 96
1  3 14 78
2 11 64
9 53

44

Then the numbers B_{n} = 1, 0, 1, 2, 9, 44, … appear in the zeroth diagonal. Now let us rotate this triangular array 60^{∘} counterclockwise, obtaining

120

24 96
6 18 78
2  4 14 64
1  1  3 11 53
1  0  1  2  9 44

In this array, every number above the bottom row is the sum of the two numbers below it. Let us define the numbers α_{i} = (5 − i)! to be the numbers in the left diagonal and let us define the numbers β_{i} = 120, 96, 78, … to be the numbers in the right diagonal. It is not hard to check that the sequences (α_{n}) and (β_{n}) satisfy (4) for n ≤ 5. We also note that these sequences have combinatorial interpretations: α_{i} is the number of permutations of {1, 2, 3, 4, 5}, in which 1, 2, …, i (or any i numbers from {1, 2, 3, 4, 5}) are all fixed points and β_{i} is the number of permutations of {1, 2, 3, 4, 5} in which 1, 2, …, i (or any i numbers from {1, 2, 3, 4, 5}) are all nonfixed points.

The general situation is described by the following theorem, which can be proved directly by a straightforward computation that we omit, or as a consequence of Theorem 2 below.

Theorem 1. Let B_{0}, B_{1}, …, B_{N} be arbitrary and let α_{n} and β_{n} for 0 ≤ n ≤ N be defined by

α_{N−n} = ∑_{k=0}^{n} \binom{n}{k}B_{k}  (6)

β_{N−n} = ∑_{k=0}^{n} \binom{n}{k}B_{N−k}.  (7)

Then the sequences (α_{n}) and (β_{n}) satisfy (4) for 0 ≤ n ≤ N.

We have a similar result that allows us to construct instances of (2) with combinatorial interpretations. The proof is also a straightforward verification, which we omit.

Theorem 2. Let Δ be a finite set, and let B be a function defined on the subsets of Δ. Let the functions α and β be defined on subsets of Δ by

α(S) = ∑_{T ⊆\overline{S}} B(T)

β(S) = ∑_{T ⊆\overline{S}} B(\overline{T}),

where the complements are with respect to Δ. Then the functions α and β satisfy (3).

We note that Theorem 1 is equivalent to the case of Theorem 2 in which B(T) depends only on the cardinality of T.

Theorems 1 and 2 allow us to construct instances of (3) and (4) with combinatorial interpretations. However, in any example constructed in this way, the cardinalities of the sets involved are bounded and cannot in general be extended to unbounded cardinalities.

For example, if we want to extend the triangular array given before Theorem 1 by adding a row at the bottom consisting of nonnegative real numbers, the 0 in the bottom row forces both numbers below it be 0, and the next row is then forced to have three consecutive 0’s. We then have the array

120

24 96
6 18 78
2  4 14 64
1  1  3 11 53
1  0  1  2  9 44
1  0  0  1  1  8 36
1  0  0  0  1  0  8 28

to which it is impossible to add another nonnegative row at the bottom.

In the next section we discuss a setting for (3) in which the sets may have unbounded cardinalities and the functions α and β are probabilities rather than integers.

3. General symmetric inclusion-exclusion

We consider a probability space containing sets E_{i}, where i ranges over an index set Δ, which in our examples will be the set of positive integers. Thus we have a probability function P, defined on all sets generated from the E_{i} by complements and finite unions and intersections, with the property that if S and T are disjoint then P (S ∪ T) = P (S) + P (T). (The usual definition of a probability function requires nonnegativity and countable additivity, and that the probability of the whole space is 1, but these conditions are not necessary for our results.) For every finite subset S ⊆ Δ we set

α(S) = P ( ⋂_{i∈S} E_{i})  (8)
β(S) = P ( ⋂_{i∈S} \overline{E}_{i}).  (9)

Theorem 3. The functions α and β defined by (8) form a symmetric inclusionexclusion pair; i.e.,

\begin{aligned}α(S) & = ∑_{T ⊆S}(−1)^{|T |}β(T) \\ β(S) & = ∑_{T ⊆S}(−1)^{|T |}α(T). \end{aligned}

Proof. By symmetry, it is enough to prove the second formula. Without loss of generality, we may assume that S = {1, 2, …, m}. A well-known form of the inclusionprinciple (see, e.g., [8, p. 6]) asserts that

P (E_{1} ∪ E_{2} ∪ ⋯ ∪ E_{m})

= ∑_{1≤i≤m} P (E_{i}) − ∑_{1≤i<j≤m} P (E_{i} ∩ E_{j}) + ⋯ + (−1)^{m−1}P (E_{1} ∩ ⋯ ∩ E_{m}).

This is equivalent to the desired formula. □

We note that if Δ is finite, Theorem 3 may be derived from Theorem 2 by taking

B(T) = P (( ⋂_{i∈Δ−T} E_{i}) ⋂ ( ⋂_{i∈T} \overline{E}_{i})).

In the general case, we can deduce Theorem 3 from Theorem 2 by restricting to a finite subset of Δ that contains S.

The most interesting examples of Theorem 3 are those in which α(S) and β(S) depend only on the cardinalities of S. Before discussing these examples, we give an example which is not of this type. We consider the set of infinite sequences (r_{1}, r_{2}, …) of real numbers between 0 and 1, and we assign probabilities in the obvious way to subsets defined by a finite number of inequalities among the r_{i}. Let us take E_{i} to be the set of sequences satisfying r_{i} < r_{i+1}. Then for any set S of positive integers, α(S) is the probability that r_{i} < r_{i+1} for all i ∈ S. To give a formula for α(S), we express S as a disjoint union of blocks of consecutive integers with gaps in between: S = V_{1} ∪ V_{2} ∪ ⋯ ∪ V_{m}, where V_{i} = {u_{i}, u_{i} + 1, …, u_{i} + s_{i} − 1} and u_{i+1} > u_{i} + s_{i}. Then

α(S) = \frac{1}{(s_{1} + 1)! (s_{2} + 1)! ⋯ (s_{m} + 1)!},

and by symmetry, β(S) = α(S).

4. A simple example

We now give a very simple example of Theorem 3 in which α(S) depends only on the cardinality of S, so that we have an instance of (4). We flip a coin infinitely many times. Each flip comes up heads with probability p and tails with probability 1 − p. For i ∈ P = {1, 2, 3, … } we let E_{i} be the event that the ith flip is a head. Then for any finite subset S ⊆ P

α(S) = P ( ⋂_{i∈S} E_{i}) = p^{|S|}
β(S) = P ( ⋂_{i∈S} \overline{E}_{i}) = (1 − p)^{|S|}

Then Theorem 3 gives

(1 − p)^{n} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}p^{k}

and (5) is the trivial formula e^{(1−p)x} = e^{x}e^{−px}. The example of the previous section, when all of the s_{i} are equal to 1, is equivalent to the case p = 1/2 of this example.

5. The Pólya-Eggenberger urn model

In the previous example, the events E_{i} were independent, which makes the situation easy to analyze, but not very interesting. Here we give a more interesting case of symmetric inclusion-exclusion sequences in which the E_{i} are not independent. It is based on a classical probabilistic model called the Pólya or Pólya-Eggenberger urn model [1, p. 120–121].

We have an urn that initially contains r red balls and b black balls. At each step we choose a ball at random from the urn. (So the probability of picking a red ball at the first step is r/(r + b) and the probability of choosing a black ball is b/(r + b).) We then replace the ball we have picked and add another ball of the same color to the same urn. We repeat this procedure forever.

The model is easily adapted to the case in which r and b are positive real numbers that are not necessarily integers. Often in descriptions of the model in the literature, c balls are added rather than one, but adding only one ball gives simpler hypergeometric formulas, and the case of adding c balls at each step with an initial inventory of r red and b black balls is equivalent to adding one ball at each step with an initial r/c red balls and b/c black balls.

An easy induction argument shows that the probability that the first m + n balls are any particular sequence of m red and n black balls is

\frac{(r)_{m}(b)_{n}}{(r + b)_{m+n}} ,

where (u)_{n} = u(u + 1) ⋯ (u + n − 1).

By ball i, we shall mean the ball chosen at the ith step. Then a consequence of the previous formula is that for any disjoint sets of positive integers R = {i_{1}, i_{2}, …, i_{m}} and B = {j_{1}, j_{2}, …, j_{n}}, the probability that the balls with numbers in R are red and the balls with numbers in B are black depends only on m and n, and is therefore

\frac{(r)_{m}(b)_{n}}{(r + b)_{m+n}} .  (10)

We note that this urn model is equivalent to a lattice path model in the plane, where a particle starts at the origin, and from the point (i, j) it moves right with probability (r + i)/(r + b + i + j) and up with probability (b + j)/(r + b + i + j). Then the probability that any particular path ending at (m, n) has been taken is (r)_{m}(b)_{n}/(r + b)_{m+n}.

Now let E_{i} be the event that ball i is red, so \overline{E}_{i} is the event that ball i is black. Then with the notation of Section 3, for any set S of positive integers, α(S) is the probability that all the balls with numbers in S are red, and

α(S) = \frac{(r)_{|S|}}{(r + b)_{|S|}} .

Similarly, β(S) is the probability that ball i is black for all i in S, and

β(S) = \frac{(b)_{|S|}}{(r + b)_{|S|}} .

So if we take S to be a set of size n, Theorem 3 gives

\frac{(b)_{n}}{(b + r)_{n}} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\frac{(r)_{k}}{(b + r)_{k}} ,

and the same identity with b and r switched.

This identity is a form of the Chu-Vandermonde summation theorem. The corresponding exponential generating function identity,

∑_{n=0}^{∞} \frac{(b)_{n}}{(b + r)_{n}} \frac{x^{n}}{n!} = e^{x} ∑_{n=0}^{∞}(−1)^{n} \frac{(r)_{k}}{(b + r)_{k}} \frac{x^{n}}{n!} ,

is the well-known _{1}F_{1} transformation

1F_{1} ({b \atop b + r} | x) = e^{x}_{1}F_{1} ({r \atop b + r} | −x) ,

where the hypergeometric series is defined by

pF_{q} ({u_{1}, …, u_{p} \atop v_{1}, …, v_{q}} | x) = ∑_{n=0}^{∞} \frac{(u_{1})_{n} ⋯ (u_{p})_{n}}{(v_{1})_{n} ⋯ (v_{q})_{n}} \frac{x^{n}}{n!} .  (11)

More generally, we can take m urns, where the ith urn starts with r_{i} red balls and b_{i} black balls. At each step, we choose a ball at random from each urn, replace it, and add another ball of the same color. What is the probability that if we do this n times, at each step we choose at least one black ball? We let E_{i} be the event that at the ith step all the balls chosen are red. Then for any finite set S ⊆ P, α(S) is the probability that for the steps in S, all of the balls chosen at are red. If |S| = n, this probability is

\frac{(r_{1})_{n}}{(r_{1} + b_{1})_{n}} \frac{(r_{2})_{n}}{(r_{2} + b_{2})_{n}} ⋯ \frac{(r_{n})_{n}}{(r_{m} + b_{m})_{n}} .

So the probability that in n steps at least one black ball is chosen at each step is

β(S) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\frac{(r_{1})_{k}}{(r_{1} + b_{1})_{k}} \frac{(r_{2})_{k}}{(r_{2} + b_{2})_{k}} ⋯ \frac{(r_{n})_{k}}{(r_{m} + b_{m})_{k}} ,  (12)

for |S| = n, which may be written as the hypergeometric series

m+1F_{m} (−n, {r_{1}, \atop r_{1} + b_{1},} {r_{2}, \atop r_{2} + b_{2},} {⋯, \atop ⋯,} {r_{m} \atop r_{m} + b_{m}} | 1) .  (13)

As a corollary, we get that this hypergeometric series is positive, as long as the r_{i} and b_{i} are positive real numbers. It is not difficult to prove this result analytically, using the integral representation

\frac{(r)_{k}}{(r + b)_{k}} = \frac{Γ(r + b)}{Γ(r)Γ(b)} ∫_{0}^{1} x^{k+r−1}(1 − x)^{b−1} dx;

However, the combinatorial approach gives a stronger result:

Theorem 4. For each nonnegative integer n, the hypergeometric series (13) can be expressed as a quotient of polynomials in the variables r_{1}, …, r_{m}, b_{1}, … b_{m} with positive coefficients.

Proof. We may assume that the variables are positive real numbers, so that the probabilistic interpretation given above applies. Then we can compute the probability (12) in another way by summing the probabilities of all possible outcomes in which at least one black ball is chosen at each step, and (10) implies that each such probability is a rational function of the desired form, and so, therefore, is their sum. □

In the case m = 2, the sum described in the proof of Theorem 4 is simple enough to write out explicitly. We can describe the colors of the two balls chosen at each step as (R, B), (B, R), or (B, B), where R denotes red and B denotes black. The number of sequences of allowable choices in which (R, B) occurs i times, (B, R) occurs j times, and (B, B) occurs k times is the trinomial coefficient (i + j + k)/(i! j! k!). The probability of such a sequence is, by (10),

\frac{(r_{1})_{i}(b_{1})_{j+k}}{(r_{1} + b_{1})_{i+j+k}} \frac{(r_{2})_{j}(b_{2})_{i+k}}{(r_{2} + b_{2})_{i+j+k}} ,

and thus we have the identity

3F_{2} (−n, {r_{1}, \atop r_{1} + b_{1},} {r_{2} \atop r_{2} + b_{2}} | 1) = ∑_{i+j+k=n} \frac{n!}{i! j! k!} \frac{(r_{1})_{i}(b_{1})_{j+k}}{(r_{1} + b_{1})_{i+j+k}} \frac{(r_{2})_{j}(b_{2})_{i+k}}{(r_{2} + b_{2})_{i+j+k}} . (14)

A slightly different approach allows us to express the double sum on the right side of (14) as the single sum

∑_{i=0}^{n} \binom{n}{i}\frac{(r_{1})_{i}(b_{1})_{n−i}(b_{2})_{i}}{(r_{1} + b_{1})_{n}(r_{2} + b_{2})_{i}} .  (15)

For each possible sequence of i red and n − i black balls chosen from the first urn, the probability of this sequence is (r_{1})_{i}(b_{1})_{n−i}/(r_{1} + b_{1})_{n} by (10). For the choices from the second urn to be compatible, whenever a red ball is chosen from the first urn a black ball must be chosen from the second urn, but when a black ball is chosen from the first urn, the color of the ball from the second urn is unrestricted. Thus given a sequence of i red and n − i black balls chosen from the first urn, the probability that the choices from the second urn are compatible with those from the first urn is (b_{2})_{i}/(r_{2} + b_{2})_{i}. Summing over all possible choices for the first urn gives (15).

Expressing (15) as a hypergeometric series, we may write the identity we have proved as the _{3}F_{2} transformation

3F_{2} (−n, {r_{1}, \atop r_{1} + b_{1},} {r_{2} \atop r_{2} + b_{2}} | 1) = \frac{(b_{1})_{n}}{(r_{1} + b_{1})_{n}}_{3}F_{2} (−n, {r_{1}, \atop 1 − b_{1} − n,} {b_{2} \atop r_{2} + b_{2}} | 1) ,

which is equivalent to formula (3.1.1) of [5].

A special case of the sum in (12) deserves mention. Suppose that r_{1} = r_{2} = ⋯ = r_{m} = r and b_{1} = b_{2} = ⋯ = b_{m} = 1. Then since

\frac{(r)_{k}}{(r + 1)_{k}} = \frac{r}{r + k} ,

the sum is

U_{m,n}(r) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} (\frac{r}{r + k} )^{m} .

One of the interesting properties of U_{m}(r) is the generating function

\binom{r + n}{n} ∑_{m=0}^{∞} U_{m,n}(r) (\frac{z}{r} )^{m} = \frac{z}{∏_{i=r}^{r+n} (1 − z/i)}

which is easily verified by partial fraction expansion.

These numbers (up to a constant factor) have appeared in several places in the literature. The case r = 1 of these numbers has been studied by Smiley [7], who mentions a combinatorial interpretation equivalent to ours and gives further references. The case r = 2 was considered by Foata, Han, and Lass [4] in connection with a coupon-collecting problem, and the general case was considered by Laforest [6] and by Flajolet et al. [2, 3] in the study of quadtrees. A combinatorial connection between the coupon-collecting and quadtree interpretations and that discussed here is not apparent.

Acknowledgment. The author wishes to thank Arthur Benjamin for asking a question that inspired this paper, Christian Krattenthaler for helpful suggestions, and the Institut Mittag-Leffler, where this paper was written, for their hospitality.

References

[1] W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, 3rd. edition, Wiley, New York, 1968.

[2] P. Flajolet, G. Gonnet, C. Puech, and J. M. Robson, Analytic variations on quadtrees, Algorithmica 10 (1993), 473–500.

[3] P. Flajolet, G. Labelle, L. Laforest, and B. Salvy, Hypergeometrics and the cost structure of quadtrees, Random Structures Algorithms 7 (1995), 117–144.

[4] D. Foata, G.-N. Han, and B. Lass, Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes, Séminaire Lotharingien de Combinatoire 47 (2001), Article B47a.

[5] G. Gasper and M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics and its Applications, Vol. 35, Cambridge University Press, Cambridge, 1990.

[6] L. Laforest, Étude des arbres hyperquaternaires, Publ. LaCIM 6, Univ. Québec à Montréal, 1991.

[7] L. M. Smiley, Completion of a rational function sequence of Carlitz, arXiv:math.C0/0006106.

[8] S. M. Ross, Introduction to Probability Models, Academic Press, San Diego, 1989.

Department of Mathematics, Brandeis University, Waltham, MA 02454-9110

  E-mail address: gessel@brandeis.edu