- #1
talolard
- 125
- 0
Homework Statement
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.
Homework Equations
Inclusion exclusion principle
The Attempt at a Solution
for 2n books, where there are n identical pairs, there are [tex] \frac{2n!}{2^n} [/tex] 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 [tex] A_i [/tex] the group of all arangemnts such that at least i pairs are next to each other.
[tex] A_i=C(n,i)* \frac{(2n-i)!}{2^{n-i}} [/tex]
In words: We chose i pairs from n, we arange 2n-i distinct items and divide by [tex]2^{n-i} [/tex] 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
[tex]\sum (-1)^i*C(n,i)* \frac{(2n-i)!}{2^{n-i}} [/tex] where the summation is from 0 to n.