Number of functions:

If the function is one-to-one we have only one case. f(x)=x

If not:

Let us consider a permutation of the set A({1,2,......,n}) to be {a₁,a₂,.....,a_n}

The idea is to divide the set into subsets {b₁,b₂,......,b_k} such

f(b_1)=f(b_2)=.....=f(b_i)=.....=f(b_k)=b_i

see that the condition f(f(x))=f(x) is satisfied.

To evaluate this we consider the sets D{1,2,3,......,n} and R{1,2,3,......,n}

When we have k subsets(following the conditions mentioned above):

We choose k numbers from R.We obtain R_k{a₁,a₂,.....,a_k} This can be done in \begin{pmatrix} n\\k \end{pmatrix} ways.

Now we have to map the numbers of D to R_k in such a manner that a_i in D always maps to a_i in R_k. This can be done in k^{n-k} ways(?).

So for dividing into k groups we have {\begin{pmatrix} n\\k \end{pmatrix}k^{n-k}} ways.

Total number of ways= \sum_{1}^{n}{\begin{pmatrix} n\\k \end{pmatrix}k^{n-k}}

Don't know how to simplify this.
Is it correct?...

P.S. Recurrence relation may be used but I could not get any.

i think this is the ans (may not be so)

reqd no = [C(n,n)]n + [C(n-1,n-2)](n-1)(P₁) + [C(n-1,n-3)](n-2)(P₂) + [C(n-1,n-4)](n-3)(P₃) + ...

to get p_x , substitute x in place of n in all the terms preceeding the one where p_x occurs

ex: P₁ = [C(1,1)](1)=1
and P₂ = [C(2,2)](2) + [C(2-1,2-2)](2-1)(p₁) = 3

the meaning of P_x is no of reqd functions from the set {1,2,3,...,x} to itself
ie P₂ = no of functions f:A→A such that f(f(x))=f(x) where A={1,2}

select any r of the n numbers to have f(x) to be x,
in nCr ways, rest of the (n-r) have to select one of the r numbers discussed in the first selection, in r^(n-r) ways
so the answer is

summation from r=1 to n, ( ⁿC_r r^n-r)

cheers!!