I thought up this problem How many ways are there to arrange person A, person B, and person C in a row such that A is not next to B, and B is not next to C? I suppose there's a way with Inclusion-Exclusion and complementary counting, but can't seem to figure it out.
Edit: This seems impossible. so how about with 5 people, such that A is not touching B, B not touching C, and C not touching D, and D not touching E? I found one possible case, ACEBD, where this works.
 A: Inclusion-exclusion works, but is very much overkill (in terms of the difficulty of computation). Instead, I have a rather pretty algorithmic approach. This works for general $n$, and is fast enough to compute by hand quite easily. I'll label the people $1, \ldots, n$.
Let us consider building the permutation with different "strings" of people; that is, we have a number of different ordered rows, and we add people one at a time. More precisely, define a "row" as an ordered string of people, such as $[1, 5, 3, 4]$. We consider a "row set" $S$, initially empty, and we add people in the order $1$, $2$, etc. through $n$. When adding the person $i$, we can do any of the following things.


*

*Add $i$ to a row by themselves. This corresponds to adding $[i]$ to the set $S$.

*Add $i$ to one of the ends of a pre-existing row. This corresponds to removing some row $R$ from the set $S$, and adding either $R + [i]$ or $[i] + R$ (but not both at once) back into $S$. Obviously, ensure that $R$ does not have $i-1$ on the end that you glue $i$ onto.

*Take two rows that already exist, and use $i$ to "glue" them together. This corresponds to removing some rows $R_1, R_2$ from $S$, and adding $R_1 + [i] + R_2$ to $S$. Obviously, ensure that neither $R_1$ nor $R_2$ have $i-1$ on the end that you use to glue $i$ on.


As an example of this procedure being run, let's consider one way of building the row set for $n = 5$.


*

*For $i = 1$, we add $[1]$ to $S$; we have no other choice. $S = \{1\}$.

*For $i = 2$, we add $[2]$ to $S$; again we have no other choice, since we cannot put $2$ next to $1$. $S = \{1, 2\}$.

*For $i = 3$, we remove $[1]$ from $S$, and add $[3] + [1] = [3, 1]$ to $S$. We do in fact have a choice at this step: we could alternatively have added $[1, 3]$, or we could just have not touched $[1]$ and added $[3]$. We couldn't have touched $[2]$, though, because $2$ cannot be next to $3$. $S = \{[2], [3, 1]\}$.

*For $i = 4$, we perform a "glue" operation with $R_1 = [3, 1]$ and $R_2 = [2]$. After this step, $S = \{[3, 1, 4, 2]\}$.

*For $i = 5$, we decide to add $[5]$ to $S$. After this step, $S = \{[3, 1, 4, 2], [5]\}$.


This procedure can obviously go many ways, and produce many different possible row sets. If we consider the final row set produced by some execution of this procedure, and assume that this final row set contains only a single row, we note that it is clearly a valid solution to our problem with $n$ people. However, we can note a much more important result: solutions to the problem are in bijection with final row sets containing only a single row, and final row sets are in bijection with possible runs of the procedure. (Two runs of the procedure are considered to be "different" if, after any step, they have a different row set.) I'll leave this as an exercise to prove.
The importance of this result is this. Suppose that we want to count the number of rows satisfying the problem's condition. Then, it suffices to compute the number of ways we could possibly run the procedure described above, such that we end up with a row set of size one. Thus, efficient computation of that quantity will allow us to solve the problem.
Define $f(i, s, a)$ as the number of possible partially-complete runs of the procedure which have just added person $i \in \{0, 1, \ldots, n\}$ ($i = 0$ if nobody has been added yet), which currently have $s \in \{0, 1, \ldots, n\}$ elements in their row set, and where $a \in \{0, 1, 2\}$ is the current "reactivity" of person $i$. The "reactivity" of person $x$ is the number of ends of rows which they are on in the current row set. We define the "reactivity" of person $0$ to be $0$. As some examples, in the row set $\{[1], [5, 3, 4, 2]\}$:


*

*the reactivity of people $2$ and $5$ is $1$, because they are on the end of a row.

*the reactivity of people $3$ and $4$ is $0$, because they are not on the end of a row.

*the reactivity of person $1$ is $2$, because they are on "two ends" of a row: both the front and back end of the row $[1]$.

*the reactivity of person $0$ is $0$ by definition; this "makes sense" because person $0$ is not on the end of any row by virtue of not existing.


The answer to our problem is the value of $\sum_{a=0}^{2} f(n, 1, a)$. Now, we shall set up a recursive equation for $f$ that will allow its efficient computation.


*

*$f(0, s, a) = 1$ if $s = a = 0$, and $0$ otherwise. (Clearly $s = 0$ at the start of any run of the procedure, so no procedures can start with $s > 0$; similarly, $a = 0$ because the reactivity of person $0$ is $0$ by definition, so no procedure can start with $a > 0$.)

*$f(i, s, 2) = \sum_{a=0}^{2} f(i-1, s-1, a)$ for $1 \leq i, s \leq n$. This is because the reactivity of person $i$ can only be $2$ if they were added in a new row by themselves; we can do this irrespective of the reactivity of person $i-1$, so the previous partially-complete procedure runs that could lead to this are only constrained by the required size of $S$.

*$f(i, s, 1) = \sum_{a=0}^{2} (2s - a)f(i-1, s, a)$ for $1 \leq i \leq n$ and $1 \leq s \leq n$; it is $0$ if $s = 0$. This is because the reactivity of person $i$ can only be $1$ if they were added to the end of a pre-existing row. We can add person $i$ to either end of any row that already exists (for a total of $2s$ possibilities), except any end of a row which has person $i-1$ on it; the number of such ends is $a$, which is the reason for the $2s - a$ term.

*$f(i, s, 0) = \sum_{a=0}^{2} (s+1-a)s f(i-1, s+1, a)$ for $1 \leq i \leq n$ and $1 \leq s \leq n-1$. If the reactivity of person $i$ is $0$, then we must have glued two rows together. There are $(s+1)s$ ways to do this (because there were $s+1$ ranges before adding person $i$), but it is not hard to see that $as$ of these are invalidated because they would put person $i$ next to person $i-1$.

*Anything not listed (e.g. $f(i, 0, a)$ for $i > 0$) is not possible under the normal course of the procedure running, and thus is $0$.


These rules alone are sufficient to compute our answer. If we compute everything at most once, our overall complexity is at most $O(n^2)$; for $n = 5$ this is easy enough to do by hand, especially if you work "top down" and only consider possibilities that can actually occur. Here is a Python script implementing this idea.
# value of n
n = 5

# cache values of f we already know
known = {}

def f(i, s, a):
    if (i, s, a) in known:
        return known[(i, s, a)]
    if i == 0:
        if s == 0 and a == 0:
            return 1
        else:
            return 0

    res = 0

    if a == 2 and 0 < s:
        for b in range(3):
            res += f(i-1, s-1, b)
    elif a == 1 and 0 < s:
        for b in range(3):
            res += (2*s-b) * f(i-1, s, b)
    elif a == 0 and 0 < s < n:
        for b in range(3):
            res += (s+1-b)*s * f(i-1, s+1, b)

    known[(i, s, a)] = res
    return res

print(sum(f(n, 1, a) for a in range(3)))

