Посчитать количество написать все $$$n!$$$ перестановок в одну строку, так, чтобы любые два соседних элемента были различны.

Я совершенно без понятия, как к этому подступиться.

Это может быть очевидно переформулированно в нечто более общее: у нас есть по $$$k$$$ (в конкретной задаче $$$(n-2)!$$$) пар $$$(i, j), i\neq j$$$. Расставить их в одну линию так, чтобы любые два соседних были различны.

Было бы очень круто узнать что угодно быстрее $$$O(n*2^{n!})$$$