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