tfr's blog

By tfr, history, 4 years ago, translation, In English

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!})$$$

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

"I am really stuck without any ideas."
Maybe you should tfr