Calculate number of ways to write all $$$n!$$$ permutations in one line so that every two adjacent elements in line are different.
I am really stuck without any ideas. I even can't calculate for $$$n = 3$$$.
Of course it can be reformulated to smth like: we have $$$k$$$(in particular $$$(n-2)!$$$) pairs $$$(i, j): i\neq j$$$, calculate number of ways to write it in one line so that every two adjacent elements in line are different.
I would be very pleased to find out something faster than $$$O(n*2^{n!})$$$
"I am really stuck without any ideas."
Maybe you should tfr