• Support PF! Buy your school textbooks, materials and every day products Here!

Inclusion-Exclusion Principle and Circular Arrangement

  • #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.
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,721
5,029
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.
 
  • #3
473
13
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,721
5,029

Related Threads on Inclusion-Exclusion Principle and Circular Arrangement

Replies
1
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
6
Views
2K
Replies
8
Views
2K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
24
Views
935
  • Last Post
Replies
12
Views
801
  • Last Post
Replies
6
Views
2K
Replies
8
Views
6K
Top