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

Question

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

Answer 1

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

Answer 2

Without loss of generality, let your $k$ elements from a selected subset be $x_1<x_2<x_3<\dots<x_k$

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.

Answer 3

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.

Answer 4

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