# Subsets of $\{1,2 \dots n\}$ with no consecutive integers

How many subsets with cardinality k of $$\{1, 2, \dots n\}$$ contain no consecutive integers? I know that there are $$F_{n+2}$$ subsets of $$\{1, 2, \dots n\}$$ with no consecutive integers, but I do not know how to go about finding the number for a given $$k$$.

This is equivalent to chooosing a sequence of $$k$$ ones and $$n-k$$ zeroes with no adjacent ones. An example with $$n=8$$ and $$k=3$$ is $$00101001, \text{ corresponding to the set }\{3,5,8\}$$ To choose such a sequence, start with a string of $$n-k$$ zeroes, with $$n-k-1$$ spaces between the zeroes, plus two extra spaces before and after, for $$n-k+1$$ spaces total: $$\;\_\; 0\;\_\;0\;\_\;0\;\_\;0\;\_\;0\;\_\qquad,\text{ with 8-3+1=6 gaps}.$$ Each of the $$k$$ $$1$$'s goes into exactly one gap. We need to choose $$k$$ of these gaps to put a $$1$$ in. This can be done in $$\binom{n-k+1}{k}\text{ ways.}$$

Without loss of generality, let your $$k$$ elements from a selected subset be $$x_1

Given such a $$k$$-tuple $$(x_1,x_2,\dots,x_k)$$, construct the related $$(k+1)$$-tuple $$(x_1-1, x_2-x_1, x_3-x_2,\dots, x_k-x_{k-1}, n-x_k)$$ describing the distance between each number and/or the boundaries in the case of the first and last numbers.

Renaming those values in the $$(k+1)$$-tuple $$(y_1,y_2,\dots,y_{k+1})$$ we can recognize that $$y_1+y_2+\dots+y_{k+1} = n-1$$ as the sum telescopes.

Now, consider the related problem of finding the number of integer solutions to the system:

$$\begin{cases}y_1+y_2+\dots+y_{k+1} = n-1\\ y_1\geq 0\\ y_{k+1}\geq 0\\ y_i\geq 2~~~\text{for all other }i\end{cases}$$

The inequalities here coming from that the elements may not be consecutive. This should now be in a known problem format for you or can be slightly modified further with another change of variable to be in a known format and the problem can be completed using stars-and-bars.

We select the first value of the set:

$$\frac{z}{1-z}$$

followed by $$k-1$$ differences that are at least two:

$$\frac{z}{1-z} \left(\frac{z^2}{1-z}\right)^{k-1}$$

and we conclude by collecting the count for all subsets with maximum element $$\le n:$$

$$[z^n] \frac{1}{1-z} \times \frac{z}{1-z} \left(\frac{z^2}{1-z}\right)^{k-1}.$$

This is

$$[z^n] \frac{z^{2k-1}}{(1-z)^{k+1}} = [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}} = {n+1-2k+k\choose k}$$

or equivalently

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

We get for the total

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

Here the coefficient extractor enforces the range and we may continue with

$$[z^{n+1}] \frac{1}{1-z} \sum_{k\ge 0} z^{2k} \frac{1}{(1-z)^{k}} \\ = [z^{n+1}] \frac{1}{1-z} \frac{1}{1-z^2/(1-z)} \\ = [z^{n+1}] \frac{1}{1-z-z^2} = [z^{n+2}] \frac{z}{1-z-z^2} = F_{n+2}.$$

The above construction works for $$k\ge 1.$$ For $$k=0$$ we get the empty set, for a total count of one. Note however that $${n+1\choose 0} = 1$$ so the formula holds there as well.

Hint: Choose $$k$$ pairs of consecutive numbers from $$\{1, 2, \ldots, n, n+1\}$$, then choose the lowest number in each pair.