Problem
COM-B1-M01-P024 Permutations Without Adjacent Consecutive Numbers
#24
★★★★★ Level 5 of 5
How many permutations of \(1,2,\ldots,8\) have no adjacent elements differing by \(1\)?
Use inclusion-exclusion over the forbidden adjacencies \(\{1,2\},\{2,3\},\ldots,\{7,8\}\).
Consider the \(7\) possible forbidden adjacencies. If \(k\) adjacencies are chosen, they form \(c\) blocks of consecutive edges in a path. Such \(k\) edges can be chosen in \(C(k-1,c-1)C(8-k,c)\) ways. Each block has \(2\) orientations, so \(2^c\) orientations, and after gluing there are \(8-k\) objects to permute, giving \((8-k)!\). Inclusion-exclusion gives \(40320-70560+51840-20400+4608-612+48-2=5242\).
Strong challenge problem; suitable for the best students.