# Principle of Inclusion / Exclusion Word Problem

I'm just trying to understand how to use PIE one word problems. I've got this silly situation in front of me:

A woman is having a dinner party with 9 of her female friends, and she's every so nicely written each lady's name on a piece of paper and placed it at a seat at her kitchen table. Unfortunately, her dough-head of a husband left the back door open! It turned out to be a very blustery day, and the oh so blustery wind came in and blew all the seat assignments away! And now, the husbands flustered and trying to recover the seat assignments... How many ways are there for him to arrange the pieces of paper so that 1) exactly 4 of the 10 ladies are sitting in the spots that the wife intended? and 2) at least 4 of the 10 ladies are sitting in the spots that the wife intended?

So here's what I've come up with:

We've got 10 women, $w_1, w_2, .. , w_{10}$. Let $c_i$ be the condition that $w_i$ (where $1 \leq i \leq 10$) is seated in the spot that the wife originally intended.

We let $S_j$ be the set of arrangements that has $j$ (where $0 \leq j \leq 10$) women being seated in the spot originally intended for them.

When determining the value of $S_j$, we first need to choose $j$ seats from $10$, then arrange the remaining $10-j$ individuals around the table.. So we have:

$$S_j = \binom{10}{j}*(10-j)!$$

Then, the answer to 1) will be

$S_4 - S_5 + S_6 - S_7 + S_8 - S_9 + S_{10}$

$= \binom{10}{4}(6!) - \binom{10}{5}(5!) + \binom{10}{6}(4!) - \binom{10}{7}(3!) + \binom{10}{8}(2!) - \binom{10}{9}(1!) + \binom{10}{10}(0!)$

$= 125361$

The answer to 2) is simply $S_4$ and does not require the use of PIE.

Cheers!

-
I do not have time right now to write out a solution. The answer to the first question is not correct. The right answer is $\binom{10}{4}$ times the number of derangements (fixed-point free permutations) of $6$ items. These can be counted by a PIE argument, and in other ways. – André Nicolas Oct 14 '12 at 20:13

For Question $1$, the general idea is right, some details are not.

We can choose the people who are in the right place in $\binom{10}{4}$ ways. For every one of these ways, there are $N$ ways for the remaining people to be all in the wrong places.

There are $6!$ permutations of these $6$ people. We count the permutations that have at least one person in the right place. By a PIE argument that you are clearly familiar with, the number of these that have at least one person in the right place is $$\binom{6}{1}5!-\binom{6}{2}4!+\binom{6}{3}3!-\binom{6}{2}2!+\binom{6}{1}1!-\binom{6}{0}0!.$$ It follows that $$N=6!-\left(\binom{6}{1}5!-\binom{6}{2}4!+\binom{6}{3}3!-\binom{6}{2}2!+\binom{6}{1}1!-\binom{6}{0}0!\right).$$ Calculate, first expressing the binomial coefficients in terms of factorials. We get the very nice $$N=6!\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!} \right),$$ which, if I remember my derangement numbers, is $265$. Thus our answer is $\dbinom{10}{4}N$.

For Question $2$, the way that minimizes thinking is to recycle the above idea. Note that the number of arrangements with at least $4$ right is $10!$ minus the sum of exactly $3$ right, exactly $2$ riht, exactly $1$ right, exactly $0$ right. Each of these is obtained as in the solution to the first problem.

Remark: Counting the number of derangements of $n$, that is, fixed-point free permutations of a set of $n$ elements, is a classic combinatorial problem with many nice solutions. The Wikipedia article is a useful introduction. The calculation we made for $6$ generalizes. The answer turns out to be essentially $\dfrac{n!}{e}$.

-
Very clear. My only objection is that I keep wanting to read PIE as Proto-Indo-European! – Brian M. Scott Oct 14 '12 at 23:19
@BrianM.Scott: It took me a while to get accustomed to the acronym. Only in America! – André Nicolas Oct 14 '12 at 23:43