Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Inclusion exclusion

  1. Jun 15, 2010 #1
    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 [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.
    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
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted