Principle of Inclusion Exclusion regarding circular arrangements

  • Thread starter drifter24
  • Start date
  • #1
1
0
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.
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,569
1,465
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...".
 

Related Threads on Principle of Inclusion Exclusion regarding circular arrangements

Replies
3
Views
614
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
24
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
11
Views
894
  • Last Post
Replies
4
Views
2K
Replies
8
Views
2K
  • Last Post
Replies
14
Views
2K
Top