codemode's blog

By codemode, history, 4 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

can you give the problem link plz

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it
Hint 1
Hint 2
Hint 3
  • »
    »
    4 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    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_5
    Now, 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          All good permutations belong to a form of the first or the second type.