1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inclusion-Exclusion Principle and Circular Arrangement

  1. Dec 19, 2014 #1
    6 people are invited to a dinner party and they are sitting on a round table.
    Each person is sitting on a chair there are exactly 6 chairs.
    So each person has exactly two neighboring chairs, one on the left and the other on the right.
    The host decides to shuffle the sitting arrangements.
    A person will be happy with the new arrangement if he can sit on his initial chair or any of his initial neighboring chairs.

    1. We have to find the number of different arrangements such that only 1 person is happy.
    2. We have to find the number of different arrangements such that only 2 persons are happy.
    3. We have to find the number of different arrangements such that only 3 persons are happy.
    Two arrangements are considered different if there is at least one person sitting on a different chair in the arrangements.

    Can this problem be solved with inclusion-exclusion principle ? If so can anyone give me intuitive explanation of the solution process.
     
  2. jcsd
  3. Dec 19, 2014 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Before you can apply inclusion-exclusion you need to decide what your system of subsets is. E.g. if you could work out the answers for 'at least k are happy' then you could use it to deduce the answers to 'exactly k are happy'. But in this case I would think it is easier to answer the second question and deduce the answer to the first from that.
    Another approach might be to consider specific subsets of guests, like 1st, 3rd and 4th from some starting point, independently of the rest. Having solved for each pair of the three, you may be able to use the principle to deduce the count for the triple.
    The principle is really quite simple. You want to count the elements of some set. The set is spanned by some system of subsets, but these may overlap. If you count the elements of each subset and add them you will be counting some elements twice. To fix that you consider each pair of these subsets, count the elements in their intersection, and subtract those. But what if three of the subsets have a nonempty common intersection? You first of all counted those elements three times, then you subtracted them three times - once for each pair. So now you haven't counted them at all, and must add them back in.... etc.
     
  4. Dec 19, 2014 #3
  5. Dec 19, 2014 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Inclusion-Exclusion Principle and Circular Arrangement
  1. Arranging Formulas (Replies: 4)

Loading...