- #1

mr_coffee

- 1,629

- 1

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?