Yes, sometimes a permutation is defined exactly as a bijection $a : \{1,2,\dots,n\}\to \{1,2,\dots,n\}$. To the problem. Clearly $|A|\leq n/2$, since $a(A)\cap A = \emptyset$. Let $|A|=k\le 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.