The Art and Craft of Problem Solving

212 CHAPTER 6 COMBINATORICS

bi is sitting to the left of gi or vice versa. For each case, there will be 7! possibili­

ties, since we are permuting seven symbols: the single symbol bigi (or gibi), plus the

other six people. Hence IAi I = 2. 7! for each i. Next, let us compute IAi n A j I. Now

we are fixing couple i and couple j, and letting the other four people permute freely.

This is the same as permuting six symbols, so we get 6!. However, there are 22 = 4

cases, since couple i can be seated either boy-girl or girl-boy, and the same is true for

couple j. Hence IAi nAjl = 4· 6!. By the same reasoning, IAi nAj nAkl = 23. 5! and

IAI nA 2 nA 3 nA 41 =^24. 4!. Finally, PIE yields

IAI UA 2 UA 3 UA 41 = 4·2·7! -G) 4 .6! + G) 23 ·5! _2^4 ·4!,

where the binomial coefficients were used because there were (i) ways of intersecting

two of the sets, etc. Anyway, when we subtract this from 8!, we get the number of

permutations in which no boy sits next to his girl, which is 13 ,824.

PIE with Indicator Functions

We're not done with PIE yet. By now you should feel comfortable with the truth of

PIE, and you may understand the proof given above, but you should feel a bit baftled

by the peculiar equivalence of PIE and the fact that (1 - 1 Y = O. We shall now present

a proof of the complement formulation of PIE (6.3.6), using the "binary" language of

indicator functions.

Recall that the indicator function of A (see page 14 6) is denoted by lA and is a

function with domain U (where U is a "universal set" containing A) and range {O, I}

defined by

1 ( x) = {

O �fx9tA,

A

1 If x E A,

for each x E U. For example, if U = N and A = {1,2,3,4, 5}, then lA(3) = 1 and

lA(17) = O.

Also recall that for any two setsA,B, the following are true (this was Problem 5.1. 2

on page 14 6):

lA(X)lB(X) = lAnB(x).

1 - 1A(X) = lX(x).

(6)

(7)

In other words, the product of two indicator fu nctions is the indicator function of

the intersection of the two sets and the indicator fu nction of a set's complement is just

one subtracted from the indicator function of that set.

Another easy thing to check (Problem 5.3. 12 on page 16 3) is that for any finite set

A,

(8)

This is just a fancy way of saying that if you consider each x in U and write down a

"I" whenever x lies in A, then the sum of these "1"s will of course be the number of

elements in A.