Derangement Recurrence Relation Proof Doesn't Seem To Make Sense

[golmschenk]

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.

"ttp://planetmath.org/?op=getobj&from=objects&id=11991"[/URL]

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?

 

[JSuarez]

(6, 2, 1, 5, 4, 3)

This seems a derangement to me.

 

[golmschenk]

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.

 

[awkward]

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.

"ttp://planetmath.org/?op=getobj&from=objects&id=11991"[/URL]

So in this proof the part I'm not understanding is:
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?[/QUOTE]

I don't understand that step either. It seems to me that it is incorrect.

[edit] P.S. Your link did not work for me. Maybe this one will work better:

[PLAIN]http://planetmath.org/encyclopedia/ProofOfRecurrencesForDerangementNumbers.html

[/edit]

 

[JSuarez]

But the 2 is in the correct place so that it's not a derangement isn't it?

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).

I don't understand that step either. It seems to me that it is incorrect.

No, it isn't.

 

[golmschenk]

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?

 

[JSuarez]

I'm sorry, I didn't meant to put it in cycle notation.

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.

 

[golmschenk]

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.

 

[JSuarez]

What?