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!

Principle of Inclusion Exclusion regarding circular arrangements

  1. Nov 5, 2011 #1
    I've been working through the AOPS Intermediate Counting and Probability text, but do not understand the explanation given for one of the problems.

    Two biologists, two chemists and two physicists sit at a round table with 6 chairs. In how many ways can they sit so that no two scientists of the same type are seated next to each other?

    I don't understand the given PIE (Principle of Inclusion Exclusion) solution.
    According to the book,
    # of seatings with no pair adjacent = # of seatings (with no restriction) - # of seatings with 1 pair adjacent + " 2 pair adjacent - " 3 pairs adjacent

    I don't understand why 2 pair adjacent is being added to the problem. If we eliminate with all seatings with 1 pair adjacent, does that not mean we also eliminate all invalid options? Isn't it true that there cannot be a valid option/arrangement in the set of (1 pair adjacent)--no matter how you arrange the other 4 scientists once you have 1 pair adjacent in the set--everything is invalid. I see how the solution makes sense in other examples, but the idea of a circular table is throwing me off tremendously. I can't seem to create concrete examples of repeats, when I try to draw out the tables and subsequently position the people.

    Could someone please explain the second step (1 pair and 2 pair)? Thanks.
     
  2. jcsd
  3. Nov 5, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    The number of seatings "with 1 pair adjacent" probably means the the number of seatings "with at least 1 pair adjacent", so it counts the seatings with 2 or more pairs adjacent.

    The convention in most mathematical discussions is that the statement "There are N things..." means "There are N or more things...". If you want there to be exactly N things, you are supposed to say "There are exactly N things...".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Principle of Inclusion Exclusion regarding circular arrangements
  1. Arranging Formulas (Replies: 4)

Loading...