codemode's blog

By codemode, history, 4 months ago, , We are given a sequence : [1,2,...N]. Lets consider all the permutations of the above sequence. Now, a good permutation is defined as the one in which there is atleast one pair of numbers such that a[i]+1=a[i+1]. How to count the number of good permutations ? This problem is from some old contest.  Comments (7)
 » can you give the problem link plz
•  » » I've solved the problem :-)
 » Hint 1You may try to count sequences that contains $12$, or $23$ etc, but you should soon realize that these contain many common sequences and subtracting them is hard. So try finding different approach. Hint 2Almost all counting problems that has a "atleast one" in it can be solved by solving the reverse problem and subtracting that from the total number of ways. Here the answer is $n!$ minus the number of permutations that don't have any $p_i +1 = p_{i +1}$ Hint 3The later part can be calculated by a recurrence. Let $f_n$ be the number of permutation with no $[k, k+1]$ as sub-string. You can get a valid permutation of $n-1$ elements and insert $n$ in any of $n - 1$ spaces to get a valid permutation of $n$ elements. Or, you can get a permutation of $n-2$ elements and insert $[n, n-1]$ in any of $n - 2$ spaces to get a valid permutation. So, $f_n = (n-1)f_{n-1} + (n-2)f_{n-2}$. Final answer is $n! - f_n$.
•  » » 4 months ago, # ^ | ← Rev. 5 →   I have a doubt : how can we be sure that permutations from (n-1)f_n-1 and (n-2)f_n-2 will not repeat.example let say we need f_5Now, one of the possible solution of f_4 be {3, 2, 1, 4}from this we will have more (n-1) permutations for f_5 , which are:{3, 2, 1, 5, 4} , {3, 2, 5, 1, 4}, so on.. and let one of the possible solution of f_3 be {3, 2, 1}than new (n-2) solution for f_5 generated from this would be:{3, 2, 1, 5, 4}, {3, 2, 5, 4, 1} , so on..but they are counting the same permutations {3, 2, 1, 5, 4}Please help if i am wrong.
•  » » » Yes there will be exactly one overlap for each of the permutation ins $f_{n - 2}$, that is why I am multiplying with $(n-2)$ instead of $(n-1)$, excluding the position where it will overlap.Try expanding your 'so on..' in the last paragraph. You'll see that there are $5-2=3$ valid permutations.
•  » » » » Yes, you are right thank you.But can you please tell, how did you figured out that you will need two terms in recurrence, like why not go with three terms, f(n) = (n-1)f(n-1) + (n-2)f(n-2) + (n-3)f(n-3). I know it sounds funny but i want to know the approach you used
•  » » » » » All good permutations belong to a form of the first or the second type.