Блог пользователя codemode

Автор codemode, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

can you give the problem link plz

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Hint 1
Hint 2
Hint 3
  • »
    »
    5 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

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