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.

My question is that if I'm given the value of N and K how can I determine the number of different arrangements according to the above condition.

The person who asked me the question gave results like the following:

1.For N=4,K=2,the number of different arrangements will be 23

2.For N=4,k=4 the number of different arrangements will be 9

I need hints to solve the problem. If someone knows the solving way please explain it with great details


1 Answer 1


To get your answer, you need to consider how many different options there are, and how many of these options make K amount of people happy.

So let's just look at example 1.

if N = 4, we have 4 people

Person 1     Person 2
Person 3     Person 4

How many ways can you arrange these people?

4!, since every time you place a person, there is one less option for the next person as to where to be places

(so 4 options for person 1, 3 for person 2 etc...)

Now how many of these options will at least two people be happy in?

Once you figure this out, you just need to take away 1, to account for the fact the new arrangement cannot be the same as the starting arrangement and you will have your answer!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .