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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Confusing Permutation Problem
  1. Permutation problem (Replies: 1)

  2. Permutation problem (Replies: 2)