Confusing Permutation Problem

  • Thread starter alec_tronn
  • Start date
  • #1
29
0

Homework Statement


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]


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!
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619
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.
 

Related Threads on Confusing Permutation Problem

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
922
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
16
Views
2K
Replies
1
Views
1K
  • Last Post
Replies
0
Views
745
  • Last Post
Replies
11
Views
2K
Top