mjhjmtu

Find the number of ways of selecting k cells from a $(2times 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?

$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.

Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.

Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.

We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.

We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.