Sitting in chairs with empty space

There are n chairs in a row. In how many ways can a teacher sit k students on these chairs so that no 2 students sit next to each other (and obviously no 2 students sit on 1 chair)?

I was thinking about inclusion-exclusion, that each student will sit next to each other, however it isn't good enough since there could be more chairs than students. Basically currently I have no idea how to solve it.

Solution 1:

Line up $n-k$ of the chairs in a row; these will be the ones that remain empty.

Now choose $k$ of the gaps created by the empty chairs in which to seat the students;

since there are $n-k+1$ gaps, this gives $\dbinom{n-k+1}{k}$ possibilities.

EDIT: As pointed out in the comments, the final answer should be $\dbinom{n-k+1}{k}\cdot k!$,

since there are $k!$ ways to arrange the $k$ students in their seats.

Solution 2:

Hint: Label the seats $1, 2, \ldots n$. If the $k$ students occupy the seats $a_1, a_2, \ldots, a_k$ (in increasing order), let $b_1=a_1-1$, $b_2=a_2-2$, ... , $b_k=a_k-k$. Then $$0 \leqslant b_1 < b_2 < \dotsb < b_k \leqslant n-k,$$ so $B = \{b_1 \ldots, b_k\}$ is a $k$-element subset of an $(n-k+1)$-set. Conversely, from any such subset you can obtain a seating configuration.

Now the question becomes: How many such sets $B$ are there?

Solution 3:

If it's solvable, then $k\le \lfloor{\frac{n}{2}}\rfloor$ ($\lfloor x\rfloor$ is the floor function in case you didn't know). We get that because each student has to have space around them if you start from the very front and go student space student space ... and continue like this it's like choosing a container of two to put each student in. There are at most $\frac{n}{2}$ of these containers of two. Therefore, via the pigeonhole principle, there can't be more than $\frac{n}{2}$ students. There are two cases that can eventually be combined either the first student is at the very front or one seat back. Now, the representation of multiplying all the positive numbers together up to a number n! . You can also define multifactorials as: $n\underbrace{!...!}_m=\prod_{d=0}^{\lfloor {\frac{n}{m}}\rfloor} n-dm$

This comes in use, because, with m=2 we have n$\cdot(n-2)...$ which means, the first student has n seats to choose from, the second has n-2 ... (not the seat the first student had or the one behind it if they are in the very front). The teacher could also have started the spacing starting with the first student at the second desk in the row leading to $(n-1)\cdot (n-3)...$ . To spread out the students like this, has taken up $2\cdot k-1$ seats from either representation so in the first case we have $\frac{n!!}{(n-2\cdot k)!!}$ , and the second case $\frac{(n-1)!!}{(n-2\cdot k-1)!!}$ and depending on ordering of things mattering you can divide by $k!\cdot (n-k)!$ for the arrangements of the students and the empty chairs ( as if ordering doesn't matter all the students are the same and all the empty chairs are the same when put in the same places).

at least that's the best explanation I can give.

Solution 4:

Consider strings over the alphabet $\{0,1\}$ where $0$ denotes a chair and $1$ denotes a student. The strings that do not contain $11$ are captured by the regular expression $0^* (10^+)^* \{\varepsilon, 1\}$. If we give $0$ a weight of $x$ and $1$ a weight of $xy$ then we are looking for the coefficient of $[x^ny^k]$.

Using these weights, the generating function for $0^* (10^+)^* \{\varepsilon, 1\}$ is

$$ \frac{1}{1 - x} \cdot \frac{1}{1 - \frac{x^2y}{1 - x}} \cdot (1 + xy) = \frac{1 + xy}{1 - x - x^2y}. $$

Hence the answer is $$ [x^ny^k]\frac{1 + xy}{1 - x - x^2y} = [x^ny^k]\frac{1}{1 - x - x^2y} + [x^{n - 1}y^{k-1}]\frac{1}{1 - x - x^2y} $$ where \begin{align} [x^ny^k]\frac{1}{1 - x - x^2y} &= [x^ny^k] \sum_m (x + x^2y)^m \\ &= [x^ny^k] \sum_m \sum_r \binom{m}{r} x^{m-r}x^{2r}y^r \\ &= [x^ny^k] \sum_m \sum_r \binom{m}{r} x^{m + r}y^r \\ &= \binom{n - k}{k}. \end{align} Therefore $$ [x^ny^k]\frac{1 + xy}{1 - x - x^2y} = \binom{n - k}{k} + \binom{(n - 1) - (k - 1)}{k - 1} = \binom{n - k + 1}{k}. $$