codemode's blog

How to count the number of permutations?
By codemode, history, 6 years 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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

can you give the problem link plz

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it
Hint 1
Hint 2
Hint 3
→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply