How many ways can a row of 7 children be rearranged so that each has a different person on their right than originally? My approach to solving this problem was to think of the children as $\{ A, B, C, D, E, F, G \}$ and to avoid having the following configurations in the rearranged set: $\{ A, B \},  \{ B, C\}, \{C, D\}, \{D, E\}, \{E, F\}$, and $\{F, G\}$. However, I'm not sure how to translate that into math. Is there a different way to solve the problem? Thanks!
 A: Let $S_{\{A\}}$ be the set of arrangements in which $A$ has the same person seated to their right as originally, that is, the set of arrangements in which $AB$ occurs.  Define $S_{\{B\}}$, etc. up to $S_{\{F\}}$ similarly.  Each of these sets has size $6!$.  Also define, for example, $S_{\{B,C,F\}}$ to be $S_{\{B\}}\cap S_{\{C\}}\cap S_{\{F\}}$, which is the set of arrangements in which $BCD$ and $FG$ occur. This set has size $4!$.  One can also define $S_{\{\}}$ to be the set in which no individual is required to have the same person seated to their right as originally, that is, the set of all arrangements without restriction.  This set has size $7!$.
Now use inclusion-exclusion. The number you seek is
$$
\begin{aligned}
\lvert S_{\{\}}\rvert&-\lvert S_{\{A\}}\rvert-\lvert S_{\{B\}}\rvert-\ldots-\lvert S_{\{F\}}\rvert\\
&+\lvert S_{\{A,B\}}\rvert+\lvert S_{\{A,C\}}\rvert+\ldots+\lvert S_{\{E,F\}}\rvert\\
&-\ldots\\
=&7!-\binom{6}{1}\cdot6!+\binom{6}{2}\cdot5!-\ldots.
\end{aligned}
$$
The binomial coefficients give the number of ways to choose the elements that are to retain their original right neighbors and the factorials give the number of ways of arranging the elements that may still be freely placed.
A: Let us phrase  this question in terms of blocks. The  nodes $P$ of the
inclusion-exclusion  poset will  represent sets  of  blocks containing
contiguous  runs that  consist of  elements that  are adjacent  in the
original permutation  and which are fused together  and together cover
the entire  permutation. The  permutations at a  node thus  consist of
permutations of the blocks where the elements in the blocks of $P$ are
adjacent plus possibly  more, which happens when a  permutation of the
blocks places two  blocks next to each other that  are adjacent in the
original permutation.  The weight of  a node i.e.  the Mobius function
for the poset is given  by $(-1)^{n-|P|}.$ A permutation that consists
of  exactly $p$  blocks is  included in  all nodes  that we  obtain by
splitting these  blocks at some subset  of size $q$  of $(n-1)-(p-1) =
n-p$ possible locations, obtaining  $p+q$ blocks.  Therefore the total
weight of such a permutation in the poset is given by
$$\sum_{q=0}^{n-p} {n-p\choose q} (-1)^{n-(p+q)}
= (-1)^{n-p} \sum_{q=0}^{n-p} {n-p\choose q} (-1)^q.$$
This evaluates  to zero when  $p\lt n$ and  one when $p=n,$  which are
precisely the weights we  require. We thus have by inclusion-exclusion
and using these weights the formula
$$\sum_{P\subseteq [n], P\ne\emptyset} (-1)^{n-|P|} |P|!.$$
Note that  in order  to get  $p=|P|$ blocks we  must choose  the $p-1$
splitting points from among the $n-1$ available ones and we obtain
$$\sum_{p=1}^n {n-1\choose p-1} (-1)^{n-p} p!.$$
This formula yields the sequence
$$1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 
\\ 1468457, 16019531, 190899411,\ldots$$
which  points  us  to OEIS  A000255  which
looks to be a match. We can also check by enumeration.

with(combinat);

ENUM :=
proc(n)
option remember;
local perm, res, pos;

    res := 0;
    perm := firstperm(n);

    while type(perm, `list`) do

        for pos to n-1 do
            if perm[pos]+1 = perm[pos+1] then
                break;
            fi;
        od;

        if pos = n then
            res := res + 1;
        fi;

        perm := nextperm(perm);
    od;

    res;
end;

X := n -> add(binomial(n-1,p-1)*(-1)^(n-p)*p!, p=1..n);

A slightly different approach as well as a recurrence appeared at this MSE link.
