Find the number of non-empty subsets of $\{1,2,3,\dots,8\}$ which do not contain two consecutive numbers.

Question

I obtained that for the set $A:=\{1,2\ldots,n\}$, the number of subsets $S$ of size $k$ such that no two elements of $S$ are consecutive numbers is $\binom{n-k+1}{k}$. Applying $$\sum_{k=1}^{4} \binom{9-k}{k}$$ gives me $54$, however, the answer given is $34$. Is there any mistake I have made?

---

Derivation of $\binom{n-k+1}{k}$:
Define $X:=\{-1,0,1,\dots,n\}$. Note that no. of $k+1$ length subsets $S$ of $X$ with no two consecutive integers such that $-1 \in S$ forms a bijection with the number of $k$ length subsets of $A$ with no 2 consecutive numbers.

Write the elements of $X$ in a row and colour $-1$. $$\color{red}{-1} \ \ 0 \ \ 1 \ \ \ldots\ \ n$$ We want to colour $k$ more numbers such that no two coloured numbers are consecutive. Define $g_i$ as the gap between the $i$th coloured number and the $i+1$th coloured number. For example, if we only colour $-1$ and $n$, $g_1 = n$. Thus, if we colour $k$ numbers other than $-1$, we observe that $$\sum_{i=1}^k g_i \le n-k+1 \implies \left(\sum_{i=1}^k g_i\right) + t = n-k+1$$where $t$ is a non-negative integer. We note that each $g_i$ is greater than 0 (since we cannot colour consecutive integers), so we define $a_i = g_i-1$, so that $a_i$ are non-negative. $$\left(\sum_{i=1}^k a_i+1\right) + t = n-k+1 \implies \left(\sum_{i=1}^k a_i\right) + t = n-2k+1$$By stars and bars, the no. of solutions for this is $$\binom{(n-2k+1)+(k+1)-1}{(k+1)-1} = \color{green}{\binom{n-k+1}{k}}$$

Answer 1

Your answer is completely correct. There are 54 non consecutive subsets of the the first 8 natural numbers.

I can guess what mistake the book made. One can prove that the total number of nonconsecutive subsets, including the empty subset, of the first $n$ natural numbers is always a Fibonacci number, $F_{n+1}$. Note that 34 and 55 are both Fibonacci numbers; perhaps the book used $F_8$ instead of $F_{8+1}$, and also forgot to subtract one for the lack of empty set.

Answer 2

Another way to rephrase this question is to ask about binary strings of length $n$ (in your case, $n=8$) for which there are no consecutive $1$'s. The bijection between such an approach and your question can be seen by viewing $0$ in slot $k$ as meaning "exclude $k$" and $1$ in slot $k$ as meaning "include $k$." If you want to specify nonempty, then you would just subtract one from the total (represented by the string of eight $0$'s).

With this view, you can now google and find the answer in various places, including MSE (example).

If you are looking for just a hint, then looking at this from a recursive lens may be fruitful. In particular, how many strings of length $n = 1,2,3,4$ have no consecutive $1$'s? How does each case relate to the previous?

Answer 3

I'm sure the correct answer is 54.

We denote the number of such subsets as $N(n, k)$ and consider two cases:

Case 1: The element $n$ is not in the subset. In this case, we need to choose $k$ elements from the set ${1, 2, \dots, n-1}$ such that no two elements are consecutive. The number of ways to do this is $N(n-1, k)$.

Case 2: The element $n$ is in the subset. In this case, we need to choose $k-1$ elements from the set ${1, 2, \dots, n-2}$ such that no two elements are consecutive. The number of ways to do this is $N(n-2, k-1)$.

Therefore, we can write the recurrence relation for $N(n, k)$ as $$N(n, k) = N(n-1, k) + N(n-2, k-1)$$ Of course we could use this relation to verify your formula inductively, but to save time I wrote a little program to implement this recursive algorithm:

function f = re(n,k)
if k == 0
    f = 1;
elseif k>=n && n>1
    f = 0;
elseif n==2 && k == 1
    f = 2;
elseif n == 2 && k == 2
    f = 0;
elseif n == 1 && k == 1
    f = 1;
else
    f = re(n-1,k) + re(n-2,k-1);
end
end

The result is re(8,1)=8, re(8,2)=21, re(8,3)=20, re(8,4)=5.

Answer 4

Alternative approach: Inclusion Exclusion

Much less elegant, but still viable.

See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

Let $~S~$ denote the set of all non-empty subsets of $~\{1,2,\cdots,8\} \implies |S| = \displaystyle \left(2^8\right) - 1.$

For $~k \in \{1,2,\cdots,7\},~$ let $~S_k~$ denote the subset of $~S~$ that contains both of the elements $~\{k,k+1\}.$

Then, the desired enumeration is

$$|S| - |S_1 \cup S_2 \cup \cdots \cup S_7|.$$

Let $~T_0~$ denote $~|S| \implies T_0 = \displaystyle \left(2^8\right) - 1 = 255. \tag1 $

Let $~T_1~$ denote $~\displaystyle \sum_{k=1}^7 |S_k|.~$
That is, $~T_1~$ represents the sum of $~\displaystyle \binom{7}{1}~$ numbers.

For $~r \in \{2,3,4,5,6,7\},~$ let $~T_r~$ denote
$\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq 7} |S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r}|.$
That is, $~T_r~$ represents the sum of $~\displaystyle \binom{7}{r}~$ numbers.

Then, in accordance with Inclusion Exclusion Theory,

$$|S| - |S_1 \cup S_2 \cup \cdots \cup S_7| = \sum_{r = 0}^7 (-1)^r T_r. \tag2 $$

Therefore, the entire problem reduces to computing $~T_r ~: r \in \{1,2,\cdots,7\},~$ and then performing the computation on the RHS of (2) above.

---

$\underline{\text{Computation of} ~T_1}$

For a set that is part of the collection represented by $~S_1~$, the set must contain the specific elements $~1~$ and $~2.~$ Therefore, $~|S_1| = 2^6 = 64.~$

By symmetry, for each $~k \in \{2,3,4,5,6,7\},~$ you have that $~|S_k| = |S_1|.~$

Therefore,

$$~T_1 = 7 \times 64 = 448. \tag3 $$

---

$\underline{\text{Computation of} ~T_2}$

For a set that is part of the collection represented by $~S_1\cap S_2~$, the set must contain the specific elements $~1, ~2,~$ and $~3.$ Therefore, $~|S_1 \cap S_2| = 2^5 = 32.~$

For a set that is part of the collection represented by $~S_1\cap S_3~$, the set must contain the specific elements $~1, ~2, ~3,~$ and $~4.$ Therefore, $~|S_1 \cap S_3| = 2^4 = 16.~$

By symmetry, when examining the set intersections that will be used to compute the $~\displaystyle \binom{7}{2} = 21~$ terms in $~T_2,~$ exactly $~6~$ of them will have an enumeration of $~32~$ and the remaining $~(21 - 6) = 15~$ terms will have an enumeration of $~16.~$

Therefore,

$$~T_2 = (6 \times 32) + (15 \times 16) = 432. \tag4 $$

---

$\underline{\text{Computation of} ~T_3}$

For a set that is part of the collection represented by $~S_1\cap S_2 \cap S_3~$, the set must contain the specific elements $~1, ~2, ~3,~$ and $~4.$ Therefore, $~|S_1 \cap S_2 \cap S_3| = 2^4 = 16.~$

For a set that is part of the collection represented by $~S_1\cap S_2 \cap S_4~$, the set must contain the specific elements $~1, ~2, ~3, ~4,~$ and $~5.$ Therefore, $~|S_1 \cap S_2 \cap S_4| = 2^3 = 8.~$

For a set that is part of the collection represented by $~S_1 \cap S_3 \cap S_5~$, the set must contain the specific elements $~1, ~2, ~3, ~4, ~5~$ and $~6.$ Therefore, $~|S_1 \cap S_3 \cap S_5| = 2^2 = 4.~$

The computation of $~T_3~$ is complicated enough that I choose to complete this section by presenting the corresponding data lexicographically, in a table.

\begin{array}{| r | r | r | r |} \hline \text{Initial Sets} & \text{Added Set} & \text{Terms} & \text{Total} \\ \hline 1,2 & [3 : 4 : 5 : 6 : 7] & 16 + 8 + 8 + 8 + 8 & 48 \\ 1,3 & [4 : 5 : 6 : 7] & 8 + 4 + 4 + 4 & 20 \\ 1,4 & [5 : 6 : 7] & 8 + 4 + 4 & 16 \\ 1,5 & [6 : 7] & 8 + 4 & 12 \\ 1,6 & [7] & 8 & 8 \\ \hline 2,3 & [4 : 5 : 6 : 7] & 16 + 8 + 8 + 8 & 40 \\ 2,4 & [5 : 6 : 7] & 8 + 4 + 4 & 16 \\ 2,5 & [6 : 7] & 8 + 4 & 12 \\ 2,6 & [7] & 8 & 8 \\ \hline 3,4 & [5 : 6 : 7] & 16 + 8 + 8 & 32 \\ 3,5 & [6 : 7] & 8 + 4 & 12 \\ 3,6 & [7] & 8 & 8 \\ \hline 4,5 & [6 : 7] & 16 + 8 & 24 \\ 4,6 & [7] & 8 & 8 \\ \hline 5,6 & [7] & 16 & 16 \\ \hline & & & \color{red}{280} \\ \hline \end{array} Therefore,

$$~T_3 = 280. \tag5 $$

---

$\underline{\text{Subsequent} ~T_r~ \text{Computations}}$

Initially, I considered that (for example) there is a 1-1 correspondence between the $~\displaystyle \binom{7}{3} = 35~$ set intersections represented in the enumeration of $~T_3~$ and the $~\displaystyle \binom{7}{4} = 35~$ set intersections represented in the enumeration of $~T_4.$

However, consider the specific $~T_3~$ terms represented by $~|S_1 \cap S_2 \cap S_3|,~$ and $~|S_2 \cap S_3 \cap S_4|.~$ These two terms have the same enumeration.

Now consider the corresponding $~T_4~$ terms represented by $~|S_4 \cap S_5 \cap S_6 \cap S_7|~$ and $~|S_1 \cap S_5 \cap S_6 \cap S_7|.~$ These two terms do not have the same enumeration. Therefore, I abandoned this approach.

Instead, for the computations of $~T_4, T_5,~$ and $~T_6,~$ I also choose to present the corresponding data lexicographically, in a table.

---

$\underline{\text{Computation of} ~T_4}$

\begin{array}{| r | r | r | r |} \hline \text{Initial Sets} & \text{Added Set} & \text{Terms} & \text{Total} \\ \hline 1,2,3 & [4 : 5 : 6 : 7] & 8 + 4 + 4 + 4 & 20 \\ 1,2,4 & [5 : 6 : 7] & 4 + 2 + 2 & 8 \\ 1,2,5 & [6 : 7] & 4 + 2 & 6 \\ 1,2,6 & [7] & 4 & 4 \\ \hline 1,3,4 & [5 : 6 : 7] & 4 + 2 + 2 & 8 \\ 1,3,5 & [6 : 7] & 2 + 1 & 3 \\ 1,3,6 & [7] & 2 & 2 \\ \hline 1,4,5 & [6 : 7] & 4 + 2 & 6 \\ 1,4,6 & [7] & 2 & 2 \\ \hline 1,5,6 & [7] & 4 & 4 \\ \hline 2,3,4 & [5 : 6 : 7] & 8 + 4 + 4 & 16 \\ 2,3,5 & [6 : 7] & 4 + 2 & 6 \\ 2,3,6 & [7] & 4 & 4 \\ \hline 2,4,5 & [6 : 7] & 4 + 2 & 6 \\ 2,4,6 & [7] & 2 & 2 \\ \hline 2,5,6 & [7] & 4 & 4 \\ \hline 3,4,5 & [6 : 7] & 8 + 4 & 12 \\ 3,4,6 & [7] & 4 & 4 \\ \hline 3,5,6 & [7] & 4 & 4 \\ \hline 4,5,6 & [7] & 8 & 8 \\ \hline & & & \color{red}{129} \\ \hline \end{array} Therefore,

$$~T_4 = 129. \tag6 $$

---

$\underline{\text{Computation of} ~T_5}$

\begin{array}{| r | r | r | r |} \hline \text{Initial Sets} & \text{Added Set} & \text{Terms} & \text{Total} \\ \hline 1,2,3,4 & [5 : 6 : 7] & 4 + 2 + 2 & 8 \\ 1,2,3,5 & [6 : 7] & 2 + 1 & 3 \\ 1,2,3,6 & [7] & 2 & 2 \\ \hline 1,2,4,5 & [6 : 7] & 2 + 1 & 3 \\ 1,2,4,6 & [7] & 1 & 1 \\ \hline 1,2,5,6 & [7] & 2 & 2 \\ \hline 1,3,4,5 & [6 : 7] & 2 + 1 & 3 \\ 1,3,4,6 & [7] & 1 & 1 \\ \hline 1,3,5,6 & [7] & 1 & 1 \\ \hline 1,4,5,6 & [7] & 2 & 2 \\ \hline 2,3,4,5 & [6 : 7] & 4 + 2 & 6 \\ 2,3,4,6 & [7] & 2 & 2 \\ \hline 2,3,5,6 & [7] & 2 & 2 \\ \hline 2,4,5,6 & [7] & 2 & 2 \\ \hline 3,4,5,6 & [7] & 4 & 4 \\ \hline & & & \color{red}{42} \\ \hline \end{array} Therefore,

$$~T_5 = 42. \tag7 $$

---

$\underline{\text{Computation of} ~T_6}$

\begin{array}{| r | r | r | r |} \hline \text{Initial Sets} & \text{Added Set} & \text{Terms} & \text{Total} \\ \hline 1,2,3,4,5 & [6 : 7] & 2 + 1 & 3 \\ 1,2,3,4,6 & [7] & 1 & 1 \\ \hline 1,2,3,5,6 & [7] & 1 & 1 \\ \hline 1,2,4,5,6 & [7] & 1 & 1 \\ \hline 1,3,4,5,6 & [7] & 1 & 1 \\ \hline 2,3,4,5,6 & [7] & 2 & 2 \\ \hline & & & \color{red}{9} \\ \hline \end{array} Therefore,

$$~T_6 = 9. \tag8 $$

---

$\underline{\text{Computation of}}$

$T_7~$ represents $|S_1 \cap S_2 \cap \cdots \cap S_7|$ which implies that the subset must have each of the elements in $~\{1,2,3,\cdots,8\}.$

Therefore,

$$~T_7 = 1. \tag9 $$

---

$\underline{\text{Final Computation}}$

$$T_0 - T_1 + T_2 - T_3 + T_4 - T_5 + T_6 - T_7 = \\ (T_0 + T_2 + T_4 + T_6) - (T_1 + T_3 + T_5 + T_7) = \\ (255 + 432 + 129 + 9) - (448 + 280 + 42 + 1) = 54.$$