Number of ordered subsets of $1...N$ where no two have a difference of $1$ This question has bugging me since it came in previous test.
You are given the set of integers from $1$ to $N$, i.e. $1, 2, 3, \ldots, N$.
Find the total number of proper ordered subsets such that no two numbers in the subset have a difference of $1$.
(That is: if take $x$ in the subset, we can't take $x+1$.)
Example: For $n=3$, the possible ordered subsets are:
$$(1), (2), (3), (1, 3), (3, 1)$$
(In total there are 5.)


*

*Example 2: for $n=5$, the possible sets subsets are:
(1), (2),(3),(4),(5) +[ (1,3),(1,4),(1,5),(2,4),(2,5),(3,5) ] * 2! + [ (1,3,5)]*3!

*In total there are 23.

*for N=6 it's 50.

*for N=7 it's 121.

*for N=8 it's 290.

*Note: empty sets are not counted.

*I have counted these manually.

*Please try to explain in simpler terms.

 A: First, find the number of unordered subsets of $[n]$ with no difference of 1, of size $k$.  The number of these is ${n - k + 1 \choose k}$.   If we have a subset $a_1, a_2, \ldots, a_k$ of $[n]$ in increasing order, with none of the differences 1, then $a_1, a_2 - 1, a_3 - 2, \cdots, a_k - (k-1)$ is a subset of $[n-k+1]$ in increasing order, and this transformation can be reversed.  For example, consider the subsets of $[7]$ of size 3 with no difference 1; these are
$$135, 136, 137, 146, 147, 157, 246, 247, 257, 357$$
(where I write $135$ for $\{1, 3, 5\}$ for conciseness).  We can subtract 1 from the second element and 2 from the third element of each of these to get
$$123, 124, 125, 134, 135, 145, 234, 235, 245, 345$$
Both of these contain ${7 - 3 + 1 \choose 3} = 10$ elements.
Now, as you've already noticed, each unordered set of size $k$ gives rise to $k!$ ordered sets.  For size $n$ we can have $k$ as large as $\lceil n/2 \rceil$. So we have
$$f(n) = \sum_{k=1}^{\lceil n/2 \rceil} {n-k+1 \choose k} k! = \sum_{k=1}^{\lceil n/2 \rceil} {(n-k+1)! \over (n-2k+1)!}$$
For numerical values, see https://oeis.org/A122852 (as has already been observed) and subtract one.  For example,
\begin{align} f(7) &= \sum_{k=1}^4 {8-k \choose k} k!  \\
&= {7 \choose 1} 1! + {6 \choose 2} 2! + {5 \choose 3} 3! + {4 \choose 4} 4! \\
&= 7 \times 1+ 15 \times 2 + 10 \times 6 + 1 \times 24 \\
&= 121 \end{align}
A: For subsets
For a natural number $n$, write $S_n := \{E \subset [\![1;n]\!] \ \big| \forall i,j \in E,\, i-j\neq 1 \}$, and $N_n := |S_n|$.
Let $n\geqslant 2$. For $E \in S_{n+1}$, one has two possibilities :


*

*$n+1 \in E$. In this case $n\notin E$, hence $E\cap [\![1;n]\!] \in S_{n-1}$.

*$n+1 \notin E$. In this case, $E \in S_n$.


This give us the following recurrence relation :
$$N_{n+1} = N_n + N_{n-1}$$
With $N_1 = 2$ and $N_2 = 3$. Hence, $N_n$ is the $(n+2)^\textrm{th}$ Fibonacci number. Take $\varphi := \frac{\sqrt{5} - 1}{2}$, the golden ratio, and you get the nice expression :
$$N_n = \frac{\varphi^{n+2} - (1 - \varphi)^{n+2}}{\sqrt{5}} $$
(EDIT) For "ordered" subsets
Write $[n] := [\![1;n]\!]$. I suggest the following definition of an "ordered" subset of size $k$ of $[n]$ : it is an injective function $f : [k] \mapsto [n]$.
Accordingly, define $S_n^k := \{ f \in [n]^{[k]} \ \big| \ f \textrm{ injective and }\forall i,j \leqslant k, \, f(i) - f(j) \neq 1\}$ and $N_n^k :=|S_n^k|$. For $k \leqslant \lceil \frac{n+1}{2} \rceil$, one gets the following recurrence relation :
$$N_{n+1}^k = N_n^k + k N_{n-1}^{k-1}$$
Of course, for $k>\lceil\frac{n}{2}\rceil$, one has $N_n^k=0$.
A: We will only consider subsets that contain no consecutive items.
Let $a_{n,k}$ be the number of $k$-subsets of $n$ items containing item $n$ (so does not contain item $n-1$).  
A $k$-subset of $n$ items containing item $n$ can be uniquely constructed from


*

*a $k$-subset of $n-1$ items containing item $n-1$ and substituting item $n$ for item $n-1$

*a $k-1$-subset of $n-2$ items containing item $n-2$ and adding item $n$
The uniqueness follows from the fact that if the $k$-subset constructed does not contain item $n-2$, it was constructed by 1, and if the $k$-subset constructed contains item $n-2$, it was constructed by 2.
Thus, by the construction above,
$$
a_{n,k}=a_{n-1,k}+a_{n-2,k-1}\tag1
$$
Starting with $a_{n,1}=1$ and $a_{1,k}=0$ (for $k\gt1)$, we get
$$
\begin{array}{c|cc}
a&1&2&3&4&5&k\\\hline
1&1&0&0&0&0\\
2&1&0&0&0&0\\
3&1&1&0&0&0\\
4&1&2&0&0&0\\
5&1&3&1&0&0\\
6&1&4&3&0&0\\
7&1&5&6&1&0\\
8&1&6&10&4&0\\
n
\end{array}\tag2
$$
Notice that column $k$ is the sum of column $k-1$ up to two rows above. Knowing that
$$
\sum_{j=k}^{n-2}\binom{j}{k}=\binom{n-1}{k+1}\tag3
$$
as we walk each row from left to right, the top argument decreases by one and the bottom increases by one. By looking at the values in $(2)$, it is reasonable to guess that
$$
a_{n,k}=\binom{n-k}{k-1}\tag4
$$
which satisfies $(1)$ and the initial conditions for $(2)$.
Now we can count all $k$-subsets of $n$ items by adding item $n+2$ and counting all $k+1$-subsets of $n+2$ items containing item $n+2$. That is, the number of $k$-subsets of $n$ items is
$$
a_{n+2,k+1}=\binom{n-k+1}{k}\tag5
$$
Therefore, the number of (unordered) subsets of $n$ items (with no consecutive items) is
$$
\sum_{k=1}^{\left\lfloor\frac{n+1}2\right\rfloor}\binom{n-k+1}{k}\tag6
$$
and the number of ordered subsets of $n$ items (with no consecutive items) is
$$
\sum_{k=1}^{\left\lfloor\frac{n+1}2\right\rfloor}\binom{n-k+1}{k}\,k!\tag7
$$
