MathDB

SMT 2007 Team #9

Source:

June 30, 2012

countingderangement

Problem Statement

Let

d_n

denote the number of derangements of the integers

1, 2, \ldots n

so that no integer

i

is in the

i^{th}

position. It is possible to write a recurrence relation

d_{n}=f(n)d_{n-1}+g(n)d_{n-2}

; what is

f(n)+g(n)