Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Confusing Permutation Problem

  1. Feb 10, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove that the number of permutations p on the set {1,2,3,...,n} with the property that |p(k)-k| [tex]\leq[/tex] 1, for all 1[tex]\leq[/tex]k[tex]\leq[/tex]n, is the fibonacci number f[tex]_{n}[/tex]

    3. The attempt at a solution
    I guess I don't understand what it's asking. I thought I knew what a permutation was... but now I'm really confused. Can someone please restate this problem in a way that maybe I could understand? Thanks a lot!
  2. jcsd
  3. Feb 10, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Consider constructing one of those permutations, to pick the first number I need to satisfy |p(1)-1|<=1. So p(1) can only be 1 or 2. Similarly p(2) can only be 1,2 or 3. p(3) can be 2,3 or 4. Etc.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook