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

Derangement Recurrence Relation Proof Doesn't Seem To Make Sense

  1. Oct 23, 2010 #1
    So I was reading up about the derangement recurrence relation proven in a combinatorical way. The proof I was looking at is at this webpage. The combinatorical proof is at the bottom of the page below the algebraic proofs.


    So in this proof the part I'm not understanding is:[QUOTE]Adding n before any of the n−1 elements of produces a derangement of [n] .[/QUOTE]
    It seems to me this doesn't always lead to a derangement of [n]. Such in the case of (2, 1, 5, 4, 3). If you add 6 before 2 then you get (6, 2, 1, 5, 4, 3), which is no longer a derangement. What am I missing that I'm not understanding this?
    Last edited by a moderator: Apr 25, 2017
  2. jcsd
  3. Oct 23, 2010 #2
    This seems a derangement to me.
  4. Oct 23, 2010 #3
    But the 2 is in the correct place so that it's not a derangement isn't it? Or how else is it considered a derangement if it's not about the number being in the position of equivalent to it's number? If you're saying that it's because the 2 used to be in the first position then what if you place the six farther down the line? According to the equation you're suppose to be able to. Or are you? I don't know. I know I'm doing something wrong, but I was hoping someone could tell me what I'm doing wrong and not just repeat to me that I was doing something wrong.
  5. Oct 24, 2010 #4
    Last edited by a moderator: May 5, 2017
  6. Oct 24, 2010 #5
    You don't understand the cycle notation for permutations: (6, 2, 1, 5, 4, 3) means 6->2->1->5->4->3->6, which, in extension form is the permutation: 1->5, 2->1, 3->6, 4->3, 5->4, 6->2. This is a permutation without fixed points (a derangement).

    No, it isn't.
  7. Oct 24, 2010 #6
    I'm sorry, I didn't meant to put it in cycle notation. I just meant to put it into set notation. Even just as a set does it still make sense? If so could you explain why?
  8. Oct 24, 2010 #7
    Well, you may not meant it, but the proof you're studying only works with cycle notation. If you have a n - 1 size derangement, then prefixing it with n cannot create an n-permutation with a 1-cycle, because n then goes to the first element of the n-cycle and the last element of it goes to n.
  9. Oct 26, 2010 #8
    Making fun of the fact that I mistakenly added a t to the end of a word when it shouldn't have been there was a bit uncalled for. Physics forums seems to be lacking a little in people who are willing to answer questions without telling the people who asked them that they don't know how to do things. That just doesn't seem to promote learning very well in my opinion.
  10. Oct 26, 2010 #9
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook