Combinatorial problem about permutations

Правка ru1, от 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!})$$$

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский tfr 2020-06-20 01:17:56 777
en2 Английский tfr 2020-06-20 00:11:11 2 Tiny change: 'r than $O(2^{n!})$' -> 'r than $O(n*2^{n!})$'
en1 Английский tfr 2020-06-20 00:04:44 534 Initial revision for English translation
ru1 Русский tfr 2020-06-20 00:04:22 534 Первая редакция (опубликовано)