How many subsets contain no consecutive elements?

Question

How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ?

Here is the solution :

The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n-1}$ ways or start with $10$ and proceed in $a_{n-2}$ ways. Therefore, $a_{n} = a_{n-1} + a_{n-2}$. $a_1 = 2, a_2 = 3$. So, $a_n = F_{n+2}$.

I have no trouble understanding the part of the argument linking $a_n$ with the Fibonacci numbers. But, I have trouble understanding the bijective argument.

What is a $n$ word ? And, how is the bijective constructed here ? How is $a_n$ linked to the question ?

Answer 1

An $n$-word is a word of length $n$. Call a set with no consecutives good.

There are two types of good set (i) the ones that do not contain $1$, and (ii) the ones that contain $1$.

There are $a_{n-1}$ good subsets of $\{1,2,\dots,n\}$ of Type $1$. There are $a_{n-2}$ good subsets of $\{1,2,\dots,n\}$ of Type (ii), since if our set contains $1$, then $2$ is forbidden.

Remark: The author has chosen to phrase things in terms of characteristic functions instead of subsets. That makes no difference, characteristic functions and subsets are essentially the same.

Answer 2

An $n$-word is just a binary string of length $n$. Given an $n$-word, you can construct a subset of $\{1,2,\ldots,n\}$ by including $i$ if and only if the $i$th digit of the $n$-word is a $1$, and vice versa. This is the bijection. In the problem at hand, a subset has no consecutive numbers if and only if its corresponding $n$-word has no adjacent $1$'s.

Answer 3

Choose the first value in the set:

$$\sum_{q=1}^n z^q = z \sum_{q=0}^{n-1} z^q = z\frac{1-z^n}{1-z}.$$

Choose some number of gaps that are at least two:

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

Sum the contributions that end in at most $n$ and extract the coefficient:

$$[z^n] \frac{1}{1-z} z\frac{1-z^n}{1-z} \frac{1-z^{2n}/(1-z)^n}{1-z^2/(1-z)} \\ = [z^{n-1}] \frac{1-z^n}{1-z} \frac{1-z^{2n}/(1-z)^n}{1-z-z^2}.$$

Eliminate the terms that do not contribute to $[z^{n-1}],$ first

$$[z^{n-1}] \frac{1-z^n}{1-z} \frac{1}{1-z-z^2}.$$

and second

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

Extracting coefficients we obtain

$$F_{n-1} + 2 F_n - 1 = F_n + F_{n+1} - 1 = F_{n+2} - 1.$$

Remark. Here we have not counted the empty set as pointed out in the comments. The answer is $$F_{n+2}$$ if the empty set is included, which it should be.

Answer 4

A $n$-word is a word with $n$ letters, 00, 01, 10, 11 are the $2$-words on the alphabet $\{0,1\}$.

Proposition. Let $E$ be a set, then the subsets of $E$ are in bijection with $\{0,1\}^E$.

Proof. Let define the following map: $$\varphi:\left\{\begin{array}{ccc}\mathcal{P}(E)&\to&\{0,1\}^E\\A&\mapsto&x\in E\mapsto\left\{\begin{array}{ll}0&\textrm{, if }x\notin A\\1&\textrm{, if }x\in A\end{array}\right.\end{array}\right..$$ $\varphi$ is a bijection whose inverse is given by: $$\left\{\begin{array}{ccc}\{0,1\}^E&\to&\mathcal{P}(E)\\f&\mapsto&\{x\in E\textrm{ s.t. }f(x)=1\}\end{array}\right..$$ Whence the result. $\Box$

In your case, your proposition tells us that the subsets of $\{1,\cdots,n\}$ are in bijection with $\{0,1\}^{\{1,\cdots,n\}}$, that is the $n$-words on the alphabet $\{0,1\}$.

Can you see from there why the number of $n$-words without consecutive $1$s is the number of subsets of $\{1,\cdots,n\}$ without consecutive numbers?

Answer 5

An $n$-word is just a binary string of length $n$.

For example, if $n=4$, there are $2^4=16$ subsets of $\{1,2,3,4\}$. A subset $A \subseteq \{1,2,3,4\}$ corresponds to the binary string $a_1 a_2 a_3 a_4$, where $a_i = 1$ if $i \in A$ and $a_i=0$ if $i \notin A$. In other words, you put a $1$ in the $i$th coordinate of the string iff element $i$ is in the subset. So, a $1$ in the string means "the element is present in the subset" and a $0$ means "the element is absent in the subset". For example, the subset $\{2,3\}$ corresponds to the binary string $\{0110\}$, where the $1$'s tell you which elements are present in the subset.

It's clear that the number of binary strings of length $n$ is $2^n$ because each of the $n$ bits can be chosen in two ways. Observe that a subset $A$ contains two consecutive integers if and only if the corresponding $n$-bit string contains two consecutive $1$'s.