I am trying to find the number of ways for any number of people to sit in a row of 7 chairs if no two people sit next to each other.
With the restriction of 7 chairs then the most number of people can be 4 and there is only way that this can be arranged as well as there being no people also being a solution.
I have brute forced it and got that there are 34 ways. How do I get the formula for this however?
ex. x _ x _ _ x _ works but _ x x _ _ _ x does not.
Thanks in advance
Best Answer
You can use stars and bars to solve for individual $n$.
For example, take $n=3$.
With $3$ people, there will be $4$ empty chairs. Let those be our stars:
$****$
Now we use $3$ bars for the people (or, what is the same thing, occupied seats). Since they cannot be next to each other, they need to take up $3$ of $5$ spots: the $3$ spots between the stars, and the two spots on either end. So, you have $5 \choose 3$ ways to do this.
It should be easy to see how this generalizes: with $n\leq 4$ people, you have $7-n$ empty chairs, and thus $8-n$ spots for the $n$ people to go, and thus ${8-n}\choose n$ way to place those $n$ people.
So, do this for all $n\leq 4$, and add them all up.