# Finding recurrence relations

• Feb 24th 2008, 01:04 PM
Eclyps19
Finding recurrence relations
Could anyone explain how I would solve these?

I need to find a recurrence relation for the number of permutations of a set with n elements, and I need to use that recurrence relation to find the number of permutations of a set with n elements using iteration.

Thank you.
• Feb 24th 2008, 01:20 PM
angel.white
Quote:

Originally Posted by Eclyps19
Could anyone explain how I would solve these?

I need to find a recurrence relation for the number of permutations of a set with n elements, and I need to use that recurrence relation to find the number of permutations of a set with n elements using iteration.

Thank you.

if I understand correctly:

2 elements: 2 permutations
a,b
b,a

3 elements: 6 permutations
a, b, c
a, c, b
b, a, c
b, c, a
c, a, b
c, b, a

You can see that each element takes a turn out front, then the remaining 2 elements go through their 2 permutations.

So it follows that if we add a fourth element, then each will take a turn out front, and the remaining three will go through their 6 permutations.

So it is basically

f(n) = n*f(n-1)

where f(1)=1