Solving a combinatorial problem

  • #1
< Mentor Note -- thread moved to HH from the technical math forums, so no HH Template is shown >

N 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 N 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.

We have to find the number of different arrangements such that at least K people 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.
 
Last edited by a moderator:

Answers and Replies

  • #2
berkeman
Mentor
59,062
9,160
< Mentor Note -- thread moved to HH from the technical math forums, so no HH Template is shown >

N 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 N 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.

We have to find the number of different arrangements such that at least K people 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.
Please show us more effort in working out your problem...
 
  • #3
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,558
6,442
This strikes me as horrendously difficult.
Start with some relatively simple cases: k = N, k = N-1. Even the second of those is hard.
 

Related Threads on Solving a combinatorial problem

  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
902
  • Last Post
Replies
4
Views
960
  • Last Post
Replies
1
Views
576
Top