I have to count the number of partitions of the set $\{1,\ldots,n\}$ under the constraint that for each $i$, the elements $i$ and $i+1$ are in different parts.
The my idea is:
We have two situation when it comes to $1,2,3 \to \{1\}\{2\}\{3\}$ or $\{1,3\}\{2\}\{\text{ one of }\{4,5,\ldots n\}\}$. For every element I choose part (there are two possibilities) Thus, $$2^{n-3} + (n-3)2^{n-4} $$
On
Since the unconstrained problem has as solution the set-partition counting function $B_n$ (the Bell numbers), for which no really simple expression exists, I don't see how one would expect to get an answer in terms of $2^n$.
Here inclusion-exclusion applies fairly easily. First count all $B_n$ partitions of $n$; then for each $1\leq i<n$ subtract the number $B_{n-1}$ of partitions in which $\{i,i+i\}$ is contained in one part (the two essentially function as a single new element); then for each $1\leq i<j<n$, the partitions in which $\{i,i+i\}$ and $\{j,j+i\}$ are each contained in one part (possibly the same part, as always happens when $j=i+1$) have been subtracted twice, so need to be added back, and there are $B_{n-2}$ such partitions (regardless of the choice of $i,j$); and so on, alternating signs. Taking into account the number of choices for $i$, $\{i,j\}$, ..., one finds $$ \sum_{k=0}^{n-1}(-1)^k\binom{n-1}kB_{n-k}. $$ The first Bell numbers (omitting $B_0$ which never occurs in this formula) are $1,2,15,52,203,877$, and computing the above formula (which can be done easily by taking repeated differences) it is hard not to notice that it evaluates to $B_{n-1}$, at least for small $n$. In fact these computations are reproducing the Bell triangle in an unusual way (in the arrangement as displayed under the link, one starts with the Bell numbers on the right edge, then computes successive rows from right to left, each value being the difference of the ones straight to its right and to its upper right; the usual order of construction is by addition left-to-right); this shows this hunch must be true in general. To understand why $B_{n-1}$ is the answer, I'll leave you the choice of deducing $$ B_{n-1}=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}kB_{n-k} \quad\text{from}\quad B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k $$ (the latter is mentioned here; the deduction is easy) or looking up the explanation of the Bell triangle, or interpreting the combinatorial argument in the answer by JiK.
On
A nice combinatorial approach is to 'read' a set partition as an arrangement of non-attacking rooks on the above-diagonal part of of a chess board:
set partition {1,5,6},{2,4,7},{3}
gets transformed to pairs (1,5),(5,6),(2,4),(4,7) by partitioning the non-singleton sets into successive (overlapping) pairs. Remark that this allows a full reconstruction of the original set partition.
Using this 'rooky' interpretation, it is easy to show that any pair (i,i+1) will sit on the diagonal just above the main diagonal.
Now, it is self-evident that the loss of this diagonal shrinks the above-diagonal chessboard from a n by n to a (n-1) by (n-1).
Hence, the number of neighbour-avoiding set partitions of size n is equal to the number of set partitions of size (n-1).
I call a partition of $\{1,2,\dots,n\}$ into exactly $k$ sets with the restrictions on neighbours mentioned in the question an "$(n,k)$ partition". Let $f(n,k)$ be the number of $(n,k)$ partitions. We can obtain a recursive formula as follows:
Consider an $(n,k)$ partition. Remove $n$ from the partition. Now we're left either with an $(n-1,k)$ partition (if $n$ was not in a singleton set) or with an $(n-1,k-1)$ partition (if $n$ was in a singleton set). Therefore, each $(n,k)$ partition can be constructed from an $(n-1,k)$ partition or from an $(n,k-1)$ partition. Moreover, the construction is always unique.
There are $k-1$ ways to extend an $(n-1,k)$ partition to an $(n,k)$ partition: $n$ can be added to any of the sets that don't have $n-1$. There is only $1$ way to extend an $(n-1,k-1)$ partition to an $(n,k)$ partition: add a new set $\{n\}$.
Now we get the recursion formula $$ f(n,k) = (k-1) f(n-1,k) + f(n-1,k-1). $$ The initial conditions are, for example, $f(1,1)=1$, $f(n,1)=0$ for all $n\geq2$, and $f(n,k)=0$ if $n<k$.
The answer to your question is now $\sum_{k=1}^{n} f(n,k)$.
Unfortunately I haven't figured out how to solve this recursive formula.
Edit 1: Thanks to xawey's comment, I looked more closely at the numbers given by this recursive formula. The recursive formula is similar to the recursive formula of Stirling numbers of second kind. This gives $f(n,k)=S(n-1,k-1)$, where $S(a,b)$ is the number of ways to partition a set of size $a$ into exactly $b$ sets. This implies that $\sum_{k=1}^{n} f(n,k) = B_{n-1}$, the number of ways to partition a set of size $n-1$. There must be a simple combinatorial interpretation.