Can this enumeration problem be generalized? (counting $20$-subsets of $\{1,2,3,\dots 30\}$ with no three consecutive elements)

Suppose $n$ is the number of elements and $k$ the size of the subset. The idea here is to construct a generating function by choosing the first element of each subset and thereafter appending a series of gaps between adjacent values, marking runs of consecutive elements. We use $w$ for these runs and $u$ to mark runs of at least three consecutive elements and $z$ for ordinary gaps of size at least two. We also use $v$ to count elements. We then have from first principles the OGF

$$f(z,w,u,v) = \frac{vz}{1-z}\sum_{q\ge 0} \frac{v^q z^{2q}}{(1-z)^q} \\ \times \left(\sum_{p\ge 0} (vw+uv^2w^2+uv^3w^3+uv^4w^4+\cdots)^p \left(\sum_{q\ge 1} \frac{v^q z^{2q}}{(1-z)^q}\right)^p\right) \\ \times (1+vw+uv^2w^2+uv^3w^3+uv^4w^4+\cdots) + 1.$$

As a sanity check we should get all subsets from

$$\frac{1}{1-z} f(z,z,1,1)$$

(the multiplier by $1/(1-z)$ sums the contributions as these subsets are classifified according to the last element). We obtain

$$\frac{z}{1-z} \sum_{q\ge 0} \frac{z^{2q}}{(1-z)^q} \\ \times \left(\sum_{p\ge 0} (w+w^2+w^3+w^4+\cdots)^p \left(\sum_{q\ge 1} \frac{z^{2q}}{(1-z)^q}\right)^p\right) \\ \times (1+w+w^2+w^3+w^4+\cdots) + 1.$$

This simplifies to

$$\frac{z}{1-z} \frac{1}{1-z^2/(1-z)} \left(\sum_{p\ge 0} \frac{w^p}{(1-w)^p} \left(\frac{z^2/(1-z)}{1-z^2/(1-z)}\right)^p\right) \frac{1}{1-w} + 1 \\ = \frac{z}{1-z-z^2} \frac{1}{1-wz^2/(1-z)/(1-w)/(1-z^2/(1-z))} \frac{1}{1-w} + 1 \\ = \frac{z}{1-z-z^2} \frac{1}{1-wz^2/(1-w)/(1-z-z^2)} \frac{1}{1-w} + 1 \\ = z \frac{1}{1-z-z^2-wz^2/(1-w)} \frac{1}{1-w} + 1 = z \frac{1}{(1-z-z^2)(1-w)-wz^2} + 1.$$

To conclude we put $w=z$ and get

$$z \frac{1}{(1-z-z^2)(1-z)-z^3} + 1 = z \frac{1}{1-z-z^2-z+z^2+z^3-z^3} + 1 \\ = z \frac{1}{1-2z} + 1 = \frac{1-z}{1-2z}.$$

We see that on multiplying by $1/(1-z)$ we obtain

$$\bbox[5px,border:2px solid #00A000]{\frac{1}{1-2z}.}$$

There are $2^n$ subsets and the sanity check goes through.

Now to eliminate subsets containing three consecutive elements we compute

$$\frac{1}{1-z} f(z,z,0,v)$$

which yields

$$\frac{vz}{1-z}\sum_{q\ge 0} \frac{v^q z^{2q}}{(1-z)^q} \\ \times \left(\sum_{p\ge 0} v^p w^p \left(\sum_{q\ge 1} \frac{v^q z^{2q}}{(1-z)^q}\right)^p\right) \\ \times (1+vw) + 1$$

which is

$$\frac{vz}{1-z} \frac{1}{1-vz^2/(1-z)} \times \left(\sum_{p\ge 0} v^p w^p \left(\frac{vz^2/(1-z)}{1-vz^2/(1-z)}\right)^p\right) \times (1+vw) + 1 \\ = \frac{vz}{1-z} \frac{1}{1-vz^2/(1-z)} \times \left( \frac{1}{1-v^2wz^2/(1-z)/(1-vz^2/(1-z))}\right) \\ \times (1+vw) + 1 \\ = \frac{vz(1+vw)}{(1-z)(1-vz^2/(1-z)) - v^2wz^2} + 1 \\ = \frac{vz(1+vw)}{1-z-vz^2 - v^2wz^2} + 1.$$

On replacing $w$ by $z$ and multiplying by $1/(1-z)$we thus have

$$\frac{1}{1-z}\frac{vz+v^2z^2}{1-z-vz^2 - v^2z^3} + \frac{1}{1-z}.$$

The second term only contributes for $k=0$ while the first does not contribute when $k=0.$ This means there is one subset of zero elements not containing three consecutive elements, namely the empty set, and this is obviously true.

Simplifying we find

$$\frac{1}{1-z}\frac{vz+v^2z^2-(1-z)/z}{1-z-vz^2 - v^2z^3} + \frac{1}{z} \frac{1}{1-z-vz^2 - v^2z^3} + \frac{1}{1-z} \\ = \left(1-\frac{1}{z}\right)\frac{1}{1-z} + \frac{1}{z} \frac{1}{1-z-vz^2 - v^2z^3} \\ = -\frac{1}{z} + \frac{1}{z} \frac{1}{1-z-vz^2 - v^2z^3} \\ = -\frac{1}{z} + \frac{1}{z} \frac{1}{1-z} \frac{1}{1-vz^2/(1-z) - v^2z^3/(1-z)}.$$

Observe that

$$[v^k] \frac{1}{1-vz^2/(1-z) - v^2z^3/(1-z)} = \sum_{q=0}^k [v^k] \frac{v^q z^{2q}}{(1-z)^q} (1+vz)^q \\ = \sum_{q=0}^k \frac{z^{2q}}{(1-z)^q} [v^{k-q}] (1+vz)^q = \sum_{q=0}^k {q\choose k-q} \frac{z^{2q}}{(1-z)^q} z^{k-q} \\ = \sum_{q=0}^k {q\choose k-q} \frac{z^{k+q}}{(1-z)^q}.$$

The coefficient extraction in $z$ now proceeds as follows:

$$[z^n] \frac{1}{z}\frac{1}{1-z} \sum_{q=0}^k {q\choose k-q} \frac{z^{k+q}}{(1-z)^q} = [z^{n+1}] \sum_{q=0}^k {q\choose k-q} \frac{z^{k+q}}{(1-z)^{q+1}} \\ = \sum_{q=0}^k {q\choose k-q} [z^{n+1-k-q}] \frac{1}{(1-z)^{q+1}}.$$

We have the closed form which is

$$\bbox[5px,border:2px solid #00A000]{ \sum_{q=0}^k {q\choose k-q} {n+1-k\choose q}.}$$

Listing these values in a triangular format we find

$$1, 1, 1, 1, 2, 1, 1, 3, 3, 0, 1, 4, 6, 2, 0, 1, 5, 10, 7, 1, \\ 0, 1, 6, 15, 16, 6, 0, 0, 1, 7, 21, 30, 19, 3, 0, 0, 1, \\ 8, 28, 50, 45, 16, 1, 0, 0, \ldots$$

which points us to OEIS A078802 where the above analysis is confirmed.

The above computation was supported by the following Maple code.

with(combinat);

ENUM :=
proc(n, k)
    option remember;
    local list, pos, res;

    if k < 3 then return binomial(n,k) fi;

    res := 0;

    for list in choose(n, k) do
        for pos to k-2 do
            if list[pos] + 1 = list[pos + 1] and
            list[pos + 1] + 1 = list[pos+2] then
                break;
            fi;
        od;

        if pos = k-1 then
            res := res + 1;
        fi;
    od;

    res;
end;

X1 := (n, k) ->
coeftayl(coeftayl(-1/z+1/z*1/(1-z-v*z^2-v^2*z^3),
                  v=0, k), z=0, n);

X2 := (n, k) ->
add(binomial(q,k-q)*binomial(n+1-k,q), q=0..k);

In particular for subsets of twenty elements of a set containing the integer range from one to thirty the number of subsets without three consecutive elements is

$$\bbox[5px,border:2px solid #00A000]{66.}$$

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$.