Can this enumeration problem be generalized? (counting $20$-subsets of $\{1,2,3,\dots 30\}$ with no three consecutive elements) I found a problem in a brazilian contest that goes as follows:
In how many ways can we select $20$ elements among $\{1,2,3,\dots, 30\}$ such that no three consecutive elements are chosen?
My solution:

 Split the elements into groups of $3: \{1,2,3\},\{4,5,6\}\dots \{28,29,30\}$ and notice that we must pick two from each group. There are three options for each group, and we call the group a "left", "center" or "right" group depending on the "missing" element. Notice that a "left" group cannot appear to the left of a "center" or "right" group, and a right group cannot appear to the right of a "center" or "left" group. Hence, selecting the quantity of each kind of group uniquely determines the arrangements, so the answer is the number of solutions to $l+c+r=30$ in non-negative integers, which is $\binom{32}{2}$ by stars and bars.

This solution clearly used that $\frac{20}{30}=\frac{2}{3}$. Is it possible to solve it for $k$-subsets of $[n]$ such that no three elements are consecutive? (I am especially interested in whether the answer can be computed efficiently, it's probably possible to do this with a $2$-dimensional recurrence but that doesn't seem very efficient)
 A: Suppose that we have a row of $n$ squares, and we have to shade in $k$ of them, without shading three in a row.
Any pattern of that description can be constructed out of tiles looking like this:
$$\blacksquare\blacksquare\square\qquad\blacksquare\square\qquad\square$$
(The tiles cannot be rotated or flipped. The last square is always $\square$, so it can be ignored.)
Assume that we have $p$ of the first kind of tile, and $k-2p$ of the second kind, and any number of the third kind. Then the problem is equivalent to lining up those tiles in a row of length $n+1$.
As there are three kinds of tiles, we know by elementary counting that the number of arrangements will be of the form $\binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\ b!\ c!}$.
The total number of tiles used must be equal to the number of squares, minus the number of tiles of the second kind, minus twice the number of tiles of the first kind:
$$(n+1)-(k-2p)-2(p)=n-k+1$$
Thus the number of arrangements for specific $p$ is the trinomial:
$$\binom{n-k+1}{p,\ k-2p,\ n-2k+p+1}$$
And we have to sum that over all relevant $p$.
A: Let $m$ be a fixed positive integer.  We say that a subset $S$ of $U:=\{1,2,\ldots,3m\}$ is eligible if $|S|=2m$ and $S$ does not contain $3$ consecutive elements of $U$.  Let $A_k:=\{3k-2,3k-1,3k\}$ for $k=1,2,\ldots,m$.  We note that each eligible subset $S$ of $U$ must omit exactly one element from each $A_k$.  We say that $k\in\{1,2,\ldots,m+1\}$ is bad with respect to $S$ if $3k-2\notin S$.  (Obviously, $m+1$ is always bad for any eligible subset $S$)
Observe that, if $k$ is bad with respect to $S$, then any $j\in\{k,k+1,k+2,\ldots,m+1\}$ is also bad with respect to $S$.  For $k\in\{1,2,\ldots,m+1\}$, write $N_k$ for the number of eligible subsets $S$ such that $k$ is the smallest bad integer with respect to $S$.  It can be easily seen that
$$N_k=k$$
because, for some $t\in\{0,1,2,\ldots,k-1\}$, $S$ must omit integers of the form $3r$ for $r\in\{1,2,\ldots,t\}$ and omit integers of the form $3r-1$ for $r\in \{t+1,t+2,\ldots,k-1\}$.   Thus, the total number of eligible subsets $S$ is
$$F(m):=\sum_{k=1}^{m+1}\,N_k=\sum_{k=1}^{m+1}\,k=\frac{(m+1)(m+2)}{2}\,.$$
In particular,
$$F(10)=\frac{11\cdot 12}{2}=66\,.$$
