6

I want to solve a problem and I have no idea how or where to begin. I don't even know if it's possible to solve. I tried to find any clues in books about discrete maths but I didn't find anything that could help me solve the problem.

Suppose there are n (distinctive) symbols (e.g. a, b and c). Therefore there are $n!$ possible permutations. It is possible to list all those permutations where each permutation appears only one time in that list (e.g. abc, acb, cab, cba, bca and bac).

How many ways are there to list all possible permutations if the next permutation in the list differs only by swapping two symbols and if the last permutation in the list differs with the first one only by swapping two symbols. (e.g. abc, cba, bca, bac, cab, acb). Another condition is that the first permutation in the list is always the same.

Is it possible to compute the number of possible lists without searching for all possible lists?

sclaes
  • 61
  • I don't know any results in this particular area, but here's my initial thought. The group of permutations of a set $\Omega$ is called the symmetric group, Sym$(\Omega)$. We can generate a graph, called the Cayley graph of Sym($\Omega$), because this group is generated by "involutions": those permutations that switch two set elements. Your question is equivalent to counting Hamilton cycles of this Cayley graph, but that's all I can tell you. – pjs36 Jan 23 '14 at 21:03
  • Did you figure it out? – yona tan Aug 13 '20 at 19:38
  • Not yet. It seems to be rather complicated :-/ I guess I need to find out more about Hamilton cycles and Cayley graphs but I haven't had time to do so. – sclaes Aug 14 '20 at 21:51

0 Answers0