Problem

Source: III International Festival of Young Mathematicians Sozopol 2012, Theme for 10-12 grade

Tags: combinatorics, Fibonacci sequence



Let $M=\{1,2,...,n\}$. Prove that the number of pairs $(A,a)$, where $A\subset M$ and $a$ is a permutation of $M$, for which $a(A)\cap A=\emptyset $, is equal to $n!.F_{n+1}$, where $F_{n+1}$ is the $n+1$ member of the Fibonacci sequence.