Solving a combinatorial problem

  • Thread starter Thread starter Shahed al mamun
  • Start date Start date
  • Tags Tags
    Combinatorics
AI Thread Summary
The discussion revolves around a combinatorial problem involving N people seated at a round table, where each person can be happy with their new seating arrangement if they occupy their original chair or one of their neighboring chairs. The goal is to determine the number of arrangements where at least K people are happy, with a focus on whether the inclusion-exclusion principle can be applied to solve it. Participants suggest starting with simpler cases, such as K equal to N or N-1, to better understand the complexity of the problem. The challenge is acknowledged as significant, indicating that a thorough approach is necessary for a solution. This problem exemplifies the intricacies of combinatorial mathematics in seating arrangements.
Shahed al mamun
Messages
5
Reaction score
0
< Mentor Note -- thread moved to HH from the technical math forums, so no HH Template is shown >[/color]

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:
Physics news on Phys.org
Shahed al mamun said:
< 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...
 
This strikes me as horrendously difficult.
Start with some relatively simple cases: k = N, k = N-1. Even the second of those is hard.
 

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Thread 'Making the denominator of a certain fraction real'

Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
View full post »

Similar threads

Inclusion-Exclusion Principle and Circular Arrangement
Replies
3
Views
2K
A counting problem (combinatorics)
Replies
9
Views
3K
Technique for proving Inclusion-Exclusion principle combinatorically
Replies
5
Views
3K
How Can a Mixed Doubles Tournament Avoid Family Pairings?
Replies
1
Views
3K
Can a Grasshopper Reach Infinite Points on a Number Line?
Replies
17
Views
5K
I Ways to put n balls in m boxes such that exactly k boxes are empty?
Replies
29
Views
3K
Problems on permutation and combination
Replies
2
Views
4K
Please solve these CAT problems
Replies
2
Views
2K
Logical solving problems (brainy and tricky)
Replies
11
Views
6K
Various combinatorial analysis problems involving ordering of groups
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top