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.

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}. $$
