Here we have to construct solution for larger problem using smaller problems i.e. first we consider n=2 , then n=3, based on the observation we can conclude for higher value of 'n'..
For n = 2,
Say the initial ordering is { 1 , 2 } , then the instances of 2 tosses where this order will be preserved are : { HH , HT , TT } and violated for { TH } ..
Hence P(order is preserved for n = 2) = 3 / 4
Now for n = 3 , we have to ignore those instances which end in "TH" as we have seen in previous subproblem that "TH" creates the violation and hence adding either head or tail before it wont help..
Hence instances remaining = 8 - 2 = 6..
Now out of these 6 instances , we cannot add tail to "HH" and "HT" because it will put the first element at the last preserving the last 2 elements (2 and 3) thereby disturbing the overall order..However , tail can be added to "TT" because if we perform the second operation as mentioned in question to {1,2,3} , then we will get back {1,2,3} only..Also as "HH" and "HT" are already valid as shown in previous subproblem , adding head wont create a problem..
Hence favorable outcomes = 6 - 2 = 4
Hence P(order remains same for n = 3) = 4 / 8
Now these 4 favorable outcomes will be considered for n = 4..
As similar to approach described for n = 3 , except the instance "TTT" , for all other 3 valid instances , we can have head in front not tail..For "TTT" , we can have either head or tail..
Hence P(order remains same for n = 4) = 5 / 16
This way for any general integer 'n' , we can generalise as :
P(order remains same after n tosses) = (n + 1) / 2n
Hence the required probability should be (n + 1) / 2n