Question:
In how many ways can $k$ people can sit in a line of $n$ chairs in a way that two empty chairs are going to be separated by at least one person?
My Answer:
First let each people select a chair: $P_k^{n}$. Now there are $n-k$ chairs remaining. Distribute them between the people:
$$
c_1+c_2+\cdots + c_k + c_{k+1}=n-k \text{ where } 0\leq c_i\leq 1
$$
Since $c_i\leq 1$ we get that $-c_i\geq -1$ and therefore $-c_i+1\geq 0$. Let $c_i'$ be $-c_i+1$. Hence:
$$
c_1'+c_2'+\cdots + c_k' + c_{k+1}'=k-n+(k+1)=2k-n+1 \text{ where } c_i'\geq 0
$$
Using stars and bars:
$$
{3k-n+1 \choose k}
$$
Therefore the final answer is:
$$
P_k^n {3k-n+1 \choose k}
$$
Is my approach correct? If it's not, I can't find what is wrong, so can someone show me?
Thanks!
Best Answer
Your argument is incorrect. To handle the restriction that $c_i \leq 1$, you need to use the Inclusion-Exclusion Principle because you need to exclude all cases in which one or more of the variables exceeds one. Doing so would be tricky since $k$ and $n$ are variables.
Here is an alternative approach.
Place $n - k$ empty chairs in a row. This creates $n - k + 1$ spaces in which we can place the $k$ people, $n - k - 1$ spaces between successive chairs and two at the ends of the row. The $n - k - 1$ spaces between successive chairs must each receive at least one person, so the answer is zero unless $k \geq n - k - 1$. The two spaces at the ends of the row need not receive a person. Therefore, if the number of people in the $i$th space from the left is $x_i$, the number of ways locations for the people may be distributed is the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_{n - k} + x_{n - k + 1} = k \tag{1}$$ in the integers subject to the constraints $x_2, x_2, \ldots, x_{n - k} \geq 1$ and $x_1, x_{n - k + 1} \geq 0$.
Let $x_1' = x_1 + 1$; let $x_{n - k + 1}' = x_{n - k + 1} + 1$; let $x_i' = x_i$ for $2 \leq i \leq n - k$. Then each $x_i'$, $1 \leq i \leq n - k + 1$, is a positive integer. Substituting $x_1' - 1$ for $x_1$, $x_{n - k + 1}' - 1$ for $x_{n - k + 1}$, and $x_i'$ for $x_i$, $2 \leq i \leq n - k$, in equation 1 yields \begin{align*} x_1' - 1 + x_2' + x_3' + \cdots + x_{n - k}' + x_{n - k + 1}' - 1 & = k\\ x_1' + x_2' + x_3' + \cdots + x_{n - k}' + x_{n - k + 1}' & = k + 2 \tag{2} \end{align*} A particular solution to equation 2 in the positive integers corresponds to the placement of $n - k$ addition signs in the $k + 1$ spaces between successive ones in a row of $k + 2$ ones. For instance, if $n = 12$ and $k = 7$, then $n - k = 5$ and $k + 2 = 9$, so $$1 + 1 1 + 1 + 1 1 + 1 + 1 1$$ corresponds to the solution $x_1' = 1$, $x_2' = 2$, $x_3' = 1$, $x_4' = 2$, $x_5 = 1$, $x_6' = 2$ of equation 2 and the solution $x_1 = 0$, $x_2 = 2$, $x_3 = 1$, $x_4 = 2$, $x_5 = 1$, $x_6 = 1$ of equation 1. The number of solutions of equation 2 is the number of ways we can select $n - k$ of the $k + 1$ spaces between successive ones in a row of $k + 2$ ones, which is $$\binom{k + 1}{n - k}$$
The $k$ people can then be arranged in those locations in $k!$ ways. Therefore, the number of ways that $k$ people can be seated in a row of $n$ chairs so that no two empty chairs are adjacent is $$\binom{k + 1}{n - k}k!$$