### div24ever's blog

By div24ever, history, 4 years ago, ,

Why is the answer 2 ^ ( n — 1 ) ?

• 0

 » 4 years ago, # |   0 Suppose the correct answer for f(n) = k and we want to find out f(n+1)One could either place the highest number i.e. (n+1) either towards the rightmost end in the permutation or towards the leftmost end to satisfy constraints "maximum element between the indices [i..j] is either present at index i, or at index j" to satisfy for [1...n]. The other inner constraints would automatically be satisfied as we know f(n) is true. So there are 2 possible choices. f(n+1) = 2*f(n)Now the base case n = 1. There is only 1 choice so f(1) = 1. Kind of Mathematical Induction Proof :PSo a recurrence relation f(n) = 2*f(n-1) when n > 1. Solving this recurrence f(n) = 2**n-1
•  » » 4 years ago, # ^ |   0 I cannot understand why is f(n+1) = 2*f(n) ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Emm. Suppose the ans for n = 3 has these possibilities: 1 2 3 3 1 2 2 1 3 3 2 1 4 possible answersNow i need to find ans for n = 4. So _ _ _ _. I can either place it at 1st index or 4th index to satisfy the property "maximum element between the indices [i..j] is either present at index i, or at index j" for range [1..4]So the ans will be: 1 2 3 4 3 1 2 4 2 1 3 4 3 2 1 4 4 1 2 3 4 3 1 2 4 2 1 3 4 3 2 1 4 + 4 = 8 possible answers
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 excuse me , why did you not count these possibles in your answer??4 2 3 14 1 3 21 3 2 42 3 1 4 ???
•  » » » » » 4 years ago, # ^ |   0 4 2 3 1i=2,j=4 the maximum number is 3 which is neither in the ith nor in the jth position.4 1 3 2 i=2,j=41 3 2 4 i=1,j=32 3 1 4 i=1,j=3
•  » » » » » » 4 years ago, # ^ |   0 I got it, Thank you.