Homework Help: Inclusion exclusion

1. Jun 15, 2010

talolard

1. The problem statement, all variables and given/known data
I'm not sure i got thiss one
John has n pairs of identitical books. Find a formula for the number of ways can he arange them so that no two identical books are next to each other.

2. Relevant equations
Inclusion exclusion principle

3. The attempt at a solution
for 2n books, where there are n identical pairs, there are $$\frac{2n!}{2^n}$$ ways to arange them. We divide by 2^n because there are n identical items and 2n! areanges 2n distinct items.

We will find the number of ways that at least one pair is adjanctent and and remove that from all possible arangements, then that is the awnser.
denote $$A_i$$ the group of all arangemnts such that at least i pairs are next to each other.
$$A_i=C(n,i)* \frac{(2n-i)!}{2^{n-i}}$$
In words: We chose i pairs from n, we arange 2n-i distinct items and divide by $$2^{n-i}$$ because we have already ignored the symetrys of the pairs.
Then by the inclusion exclusion principle the number of ways that no pair adjactent is
$$\sum (-1)^i*C(n,i)* \frac{(2n-i)!}{2^{n-i}}$$ where the summation is from 0 to n.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution