Find the number of ways of selecting k cells from a $(2\times n)$-board such that no two selected cells share a side (non-adjacent). 


For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$. 


Counting manually works for small numbers. 



> 
> **Question.** Is there any formula that can be derived for large numbers?
> 
> 
> 



Counting configurations on a 2xn board under restrictions
$\dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
\begin{align}G(t,q):=\frac{t+(2t+t^2)q}{1-t-(t+t^2)q}
&=\frac{t+(2t+t^2)q}{1-t}\cdot\frac1{1-\left(\frac{t+t^2}{1-t}\right)q} \\
&=\frac{t+(2t+t^2)q}{1-t}\sum\_{j\geq0}\left(\frac{t+t^2}{1-t}\right)^jq^j \\
&=\sum\_{k\geq0}\left(\frac{2t^k(1+t)^{k-1}}{(1-t)^{k+1}}\right)q^k.
\end{align}
Further calculation reveals that
$$\frac{2t^k(1+t)^{k-1}}{(1-t)^{k+1}}
=\sum\_{n\geq0}\left(2\sum\_{r=0}^{n-k}\binom{n-r}k\binom{k-1}r\right)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2\sum\_{r=0}^{n-k}\binom{n-r}k\binom{k-1}r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.


