7
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does $a_n$ represent exactly ? It can't be a good subset of size $n$ because of a good subset had $n$ elements, it would have consecutive elements. $\endgroup$ – user230452 Jun 29 '16 at 10:35
  • $\begingroup$ $a_n$ is the number of subsets of $\{1,2,\dots,n\}$ that contain no consecutive numbers. $\endgroup$ – André Nicolas Jun 29 '16 at 11:32
  • $\begingroup$ Good one. If this was the explanation offered in the book, I would have understood much clearly since it eschews a bijection with binary $n$ words $\endgroup$ – user230452 Jun 29 '16 at 11:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow. Thanks a lot. I wouldn't have guessed that on my own. How did you understand the logic ? Have you done these type of problems before ? $\endgroup$ – user230452 Jun 27 '16 at 17:35
  • 1
    $\begingroup$ @user230452, if you imagine lining people up in a row and saying "everyone who wants to be in the subset, raise your hand," it's easy to picture the result as a string of $1$'s and $0$'s. $\endgroup$ – Barry Cipra Jun 27 '16 at 18:27
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you explain what you are summing up over exactly in the first step ? $\endgroup$ – user230452 Jun 29 '16 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.