- #1
golmschenk
- 36
- 0
First I'd like to mention I don't want the answer, I'd just like a hint in the direction which I should start working in. I just don't know how to begin the problem.
How many permutations of 1, 2, . . . , n are there in which i is never immediately
followed by i + 1, i = 1, 2, . . . , n − 1? Show your answer is equal to D[tex]_{n}[/tex] + D[tex]_{n-1}[/tex]. (superscripts should be subscripts, I'm not sure why they aren't)
D[tex]_{n}[/tex] being the number of derangements of a set with n elements.
D[tex]_{n}[/tex] = [tex]^{n}_{k=0}[/tex][tex]\sum[/tex](-1)[tex]^{k}[/tex]([tex]\stackrel{n}{k}[/tex])(n-k)!
(also, if someone wouldn't mind telling me how to get the conditions around the sigma for the sum correctly that would be great)
3. The Attempt at a Solution [/bn]
Again, it's the beginning I've been having problems with. I started counting cases, but that definitely seems like the long and difficult way of solving this. I've tried to simplify D[tex]_{n}[/tex] + D[tex]_{n-1}[/tex] to see if it might give me some hint into what I should be doing, but haven't gotten anything out of it. Any hints? Maybe all it will take would even just be a one word hint. I just need to get a push in the right direction. Thanks!
Homework Statement
How many permutations of 1, 2, . . . , n are there in which i is never immediately
followed by i + 1, i = 1, 2, . . . , n − 1? Show your answer is equal to D[tex]_{n}[/tex] + D[tex]_{n-1}[/tex]. (superscripts should be subscripts, I'm not sure why they aren't)
D[tex]_{n}[/tex] being the number of derangements of a set with n elements.
Homework Equations
D[tex]_{n}[/tex] = [tex]^{n}_{k=0}[/tex][tex]\sum[/tex](-1)[tex]^{k}[/tex]([tex]\stackrel{n}{k}[/tex])(n-k)!
(also, if someone wouldn't mind telling me how to get the conditions around the sigma for the sum correctly that would be great)
3. The Attempt at a Solution [/bn]
Again, it's the beginning I've been having problems with. I started counting cases, but that definitely seems like the long and difficult way of solving this. I've tried to simplify D[tex]_{n}[/tex] + D[tex]_{n-1}[/tex] to see if it might give me some hint into what I should be doing, but haven't gotten anything out of it. Any hints? Maybe all it will take would even just be a one word hint. I just need to get a push in the right direction. Thanks!
Last edited: