Let $k$ and $n$ be positive integers with $k \leq n$. Let $a(n,k)$ be the number of ways to place $k$ non-attacking rooks on an $n \times n$ board, where we exclude the tiles $\{(1, 1), (2, 2), \dotsc, (n, n)\}$, and the tiles $\{(1, 2), (2, 3), \dots, (n-1, n)\}$, and also the tile $(n, 1)$.
Prove that $$a(n , k) = \frac{2n}{2n-k} {{2n-k}\choose{k}}$$
Note that $a(n, k)$ is also the number of ways to choose $k$ children from a ring with $2n$ children in such a way that no two consecutive children are chosen.
My thoughts: First of all, I'm not sure how the two interpretations are equivalent. I think that the idea is if the first rook is placed in square $(\ell, k)$, then square $(\ell, k)$ represents the first child chosen, and the rest of row $\ell$ and column $k$ represent the children on each side of the first child. However, I"m not sure if this is the correct interpretation.
Second, I know that to prove that the formula holds I want to use some kind of inclusion-exclusion argument (the problem is problem 33 from chapter 6 - Inclusion-Exclusion principle from Brualdi's Introductory Combinatorics).
I suppose an inclusion-exclusion argument would start with noticing that there are ${2n \choose k}$ ways to choose $k$ children from the circle. There are $2n(2n-3){2n-2 \choose k-2}$ ways to choose them so that the first and second child are not next to each other. I'm not sure how to proceed from here. I get really confused when we are working with circles...
I'll use the reworded version - let there be $2n$ numbers, $1 \cdots 2n$ in a circle.
How many ways are there to pick $k$ numbers that are not next to each other in a circle?
Well, we don't need inclusion-exclusion principle here.
Lemma. There are $\binom{n-r+1}{r}$ ways to pick $r$ numbers out of $1 \cdots r$ so that no two numbers are consecutive.
Proof. Take the $r$ numbers as $x_1 \cdots x_r$.
Between $x_i$ and $x_{i+1}$, there must be at least one number - so let $y_i=x_i+1 \not= x_{i+1}$ for $1 \le i \le r-1$.
Now let there be $z_1$ numbers that are less than $x_1$.
For $2 \le i \le r$, let $z_i$ be the number of numbers that are larger than $y_{i-1}$ but smaller than $x_i$.
Let there be $z_{r+1}$ numbers that are larger than $x_r$ but not greater than $n$.
Note that $\sum_{i=1}^{r+1} z_i = n-2r+1$.
Since $z_i$ are nonnegative integers, we use stars and bars to find that there are $\binom{n-r+1}{r}$ ways to set $z_1 \cdots z_{r+1}$.
Also, it is clear that there is a bijection between $x_1 \cdots x_r$ and $z_1 \cdots z_{r+1}$.
This completes the proof of the lemma.
Now we divide cases.
Case 1. $2n$ is chosen.
We can't choose $1$ or $2n-1$. We have to choose $k-1$ numbers from $2$ to $2n-2$ so that there are no consecutive numbers.
By our Lemma, we have $\binom{2n-3-(k-1)+1}{k-1} = \binom{2n-1-k}{k-1}$ ways to do so.
Case 2. $2n$ is not chosen.
We have to choose $k$ numbers from $1$ to $2n-1$ so that there are no consecutive numbers.
By our Lemma, we have $\binom{2n-1-k+1}{k} = \binom{2n-k}{k}$ ways to do so.
We conclude with basic arithmetic - $$\binom{2n-k-1}{k-1}+\binom{2n-k}{k} = \frac{k}{2n-k} \binom{2n-k}{k} + \binom{2n-k}{k} = \frac{2n}{2n-k} \binom{2n-k}{k}$$ as desired.