Index the chosen cells from left to right, and let $c_i$ and $r_i$ be the column and row of cell $i$. Consider how many times your chosen cells switch from being in the bottom row to being in the top as you go from left to right, and call the number of switches $s$. The configuration is uniquely specified by:

- A choice of whether the first cell is in the top or bottom row.
- Which cells are in the opposite row from the previous one.
- The "distance" between subsequent cells, where distance between cell $i$ and $i+1$ is $c_{i+1}-c_{i}$ if they are in opposite rows and $c_{i+1}-c_{i}-1$ if they are in the same row. This definition ensures that distance 1 corresponds to the closest the two cells can be in either case. We must also specify the column of the first cell $c_1$ so we have a starting point.

Example:

The switches happen between cells 1 & 2 and between cells 3 & 4. The distances between successive cells are 1 (between cells 1 & 2), 1 (between 2 & 3), and 3 (between cells 3 & 4).

For fixed $s$, we can enumerate the number of possibilities for each of the above bullet points:

- There are two choices for the first row.
- There are $\binom{k-1}{s}$ ways to choose where the switches occur.
- We can evaluate the sum of the distances plus $c_{1}$ plus $n-c_{k}$: If we switched rows between every two chosen cells, it would just be $n$, but every time we
**don't** switch we lose $1$ because the cells can't be adjacent. So the sum is $n-\left(\text{number of non-switches}\right) = n-(k-1-s)$. This sum is split into $k+1$ boxes, with at least 1 in each of the first $k$ boxes. Hence there are $\binom{n+1+s-k}{k}$ choices here.

So the total number of combinations for fixed $s$ is $2\binom{k-1}{s}\binom{n+1+s-k}{k}$, and the total number of arrangements is the sum of this over $s=0,\dots,k-1$, $$\sum_{s=0}^{k-1} 2\binom{k-1}{s}\binom{n+1+s-k}{k}$$

Happily, this agrees with your calculations for $n=3,k=2$ and $n=5,k=3$.