Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.