# $k$-element subsets of $$that do not contain 2 consecutive integers Let k,n\in \mathbb{N} with k\leq n. Find the total number of k-element selections from [n] = \{1, 2, \ldots, n\} that do not contain any 2 consecutive integers #### Solutions Collecting From Web of "k-element subsets of$$ that do not contain $2$ consecutive integers"

Hints:

It’s the same as counting bitstrings of length $n$ containing exactly $k$ ones, no two of them consecutive,

which is the same as counting solutions of $x_0+x_1+\cdots+x_k=n-k$ in integers $x_j$ such that $x_0\ge0$, $x_k\ge0$, and $x_j\gt0$ for $0\lt j\lt k$,

which is the same as counting solutions of $y_0+y_1+\cdots+y_k=n+2-k$ in positive integers $y_j$,

which is the same as counting solutions of $z_0+z_1+\cdots+z_k=n+1-2k$ in nonnegative integers $z_j$.

Don’t use inclusion-exclusion. It’s a simple binomial coefficient.

Using generating functions and the binary string of length $n$ with $k$ ones model we need to select the size of the $k+1$ gaps between the ones, where the first and last one may be empty and the inner gaps must have size at least one. This gives
$$f(z) = \frac{1}{1-z}\times\frac{z}{1-z}\times\frac{z}{1-z}\times\cdots \times\frac{z}{1-z}\times\frac{z}{1-z}\times\frac{1}{1-z}.$$
This simplifies to
$$f(z) = \frac{z^{k-1}}{(1-z)^{k+1}}.$$
Now the gaps must add up to $n-k$ so the answer is
$$[z^{n-k}] f(z) = [z^{n-k}] \frac{z^{k-1}}{(1-z)^{k+1}} = [z^{n+1-2k}] \frac{1}{(1-z)^{k+1}}.$$
By Newton’s binomial series this is
$$\binom{n+1-2k + k}{n+1-2k} = \binom{n+1-k}{n+1-2k} = \binom{n+1-k}{k}.$$

Try looking at the Fibonacci Sequence! $F_{n+2}$ (where $F_n$ is Fibonacci) will also create this sequence.