- #1
mr_coffee
- 1,629
- 1
Hello everyone. I'm not sure what the recurance relationship of this would be becuase, it doesn't seem liek the answer you want requires calculation of any of the previous terms...here it is:
For each integer n >= 2, let a_n be the number of permutations of {1,2,3,...n} in which no number is more than one palce removed from its "natural" position. Thus a_1 = 1; since the on permutation of {1}, namely 1, does not move 1 from its natural postion. Also a_2 = 2 since neither of the two permutations of {1,2}, namely, 12 and 21, moves either number more than one place from its natural positon.
a. find a_3 = 3
THe 3 permutations that do not move more than one place from their natural postions are 213, 132, and 123.
Find the recurrance relation for a_1, a_2, a_3...
Okay so I started to figure out more terms...but it said n >= 2, so why would they say find a_1 if they siad, n must be 2 or greater?
well anyways
a_4 = 4 because
1234, 2134, 1324 1243
a_5 = 5 because
12345, 21345, 13245, 12435, 12354
so as you see, if i go to
a_n, would a_n just be n?
For each integer n >= 2, let a_n be the number of permutations of {1,2,3,...n} in which no number is more than one palce removed from its "natural" position. Thus a_1 = 1; since the on permutation of {1}, namely 1, does not move 1 from its natural postion. Also a_2 = 2 since neither of the two permutations of {1,2}, namely, 12 and 21, moves either number more than one place from its natural positon.
a. find a_3 = 3
THe 3 permutations that do not move more than one place from their natural postions are 213, 132, and 123.
Find the recurrance relation for a_1, a_2, a_3...
Okay so I started to figure out more terms...but it said n >= 2, so why would they say find a_1 if they siad, n must be 2 or greater?
well anyways
a_4 = 4 because
1234, 2134, 1324 1243
a_5 = 5 because
12345, 21345, 13245, 12435, 12354
so as you see, if i go to
a_n, would a_n just be n?