# Confusing Permutation Problem

1. Feb 10, 2008

### alec_tronn

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| $$\leq$$ 1, for all 1$$\leq$$k$$\leq$$n, is the fibonacci number f$$_{n}$$

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. Feb 10, 2008

### Dick

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.