$n>k\geq 2$ are integers.
Around a round table there are $n$ chairs: $n-1$ identical chairs and one taller chair.
We want to paint $k$ from $n$ chairs in red so that there won't be $2$ red chairs next to each other.
Need to prove that the number of possibilities to the painting above is $\binom{n-k-1}{k-1}\cdot \frac{n}{k}$
I can't figure how to get that term i need to prove.
Thank you.
Line up the chairs in a row, with the throne on the left. We either (i) do not paint the throne or (ii) paint the throne red.
Case (i): We have $n-1$ chairs left in the row, and want to paint $k$ of them red. So $n-k-1$ of them will remain unpainted. Write down $n-k-1$ occurrences of $\times$, like this $$ \times\quad\times\quad\times\quad\times\quad\times\quad\times\quad\times\quad\times\quad\times$$ to represent spots for the unpainted chairs. These determine $n-k$ "gaps" ($n-k-2$ real gaps between $\times$'s, plus the $2$ "endgaps") from which we must choose $k$ to slip a painted chair into. There are $\binom{n-k}{k}$ ways to do this. By a standard result, easily checked by a combinatorial argument or by playing with factorials, we have $$\binom{n-k}{k}=\frac{n-k}{k}\binom{n-k-1}{k-1},\tag{1}$$
Case (ii): We must leave the chair next to the throne, and the one at the right end, unpainted. So we must paint $k-1$ of the remaining $n-3$. That will leave $n-k-2$ unpainted. A "gap" argument like the previous one shows that there are $$\binom{n-k-1}{k-1}\tag{2}$$ ways to do this.
Finishing: Add the answers (1) and (2). We get $$\left(\frac{n-k}{k}+1\right)\binom{n-k-1}{k-1},$$ which is what we wanted to show.
