[reference to question] (Problem - C - Codeforces)
1 Like
Consider any permutation p_i, i = 1 to n. Construct an un-directed Graph with edges of the form (i, p[i]). Note that you may construct self-loops also or ignore them. If there is any cycle of length greater than 1(excluding self loops) then we say there exists a cycle in permutation. You may also refer to this: Cyclic permutation - Wikipedia
Now second question : Cyclic permutation of length ‘n’. Note that I am assuming that permutation is build using elements 1 to ‘n’. In that case you need to arrange all elements in a circle. Number of ways of doing so is (n-1)!.
The question you are referring is a bit different since the graph is built in a different way. In this case, we find number of permutations such that there is no cycle. Also observe that permutation should first increase and then decrease so that there is no cycle(try to prove that there exists a cycle if this is not the case).
Now we need to place n at some position. Let’s Place it at i, on the left of n there are (i-1) positions left to be occupied which can be filled out of any (n-1) elements, Therefore we have the sum:
\sum\limits_{i=1}^{n}{{n-1} \choose {i-1}} = 2^{n-1}
Just subtract this from n!.
5 Likes
thanks for your help