Yes, sometimes a permutation is defined exactly as a bijection a:{1,2,…,n}→{1,2,…,n}. To the problem. Clearly |A|≤n/2, since a(A)∩A=∅. Let |A|=k≤n/2. It's possible to choose the elements of A in \binom{n}{k} ways. For each option of A, the set a(A) can be chosen in \binom{n-k}{k} ways, thus there are \binom{n-k}{k}\cdot k! options for the restriction of a on the set A and (n-k)! options for the restriction of a on M\setminus A.
Hence, there are \binom{n}{k}\cdot \binom{n-k}{k}\cdot k!\cdot (n-k)!=n!\binom{n-k}{k} ways to choose (A,a) knowing that |A|=k\le n/2. Finally, for the number of all such pairs (A,a) we get
\displaystyle n!\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k} But, it's (well) known
F_{n+1}=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}hence, the result follows.