Combinatorial problem about permutations

Revision ru1, by tfr, 2020-06-20 00:04:22

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(2^{n!})$$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian tfr 2020-06-20 01:17:56 777
en2 English tfr 2020-06-20 00:11:11 2 Tiny change: 'r than $O(2^{n!})$' -> 'r than $O(n*2^{n!})$'
en1 English tfr 2020-06-20 00:04:44 534 Initial revision for English translation
ru1 Russian tfr 2020-06-20 00:04:22 534 Первая редакция (опубликовано)