1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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