Let A={1, 2, 3, ..., n}
Find the number of functions f : A → A having the property that f(f(x)) = f(x).
P.S. Edited a bit.
1If 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 {a1,a2,.....,an}
The idea is to divide the set into subsets {b1,b2,......,bk} 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 Rk{a1,a2,.....,ak} This can be done in \begin{pmatrix} n\\k \end{pmatrix} ways.
Now we have to map the numbers of D to Rk in such a manner that ai in D always maps to ai in Rk. 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.
1i think this is the ans (may not be so)
reqd no = [C(n,n)]n + [C(n-1,n-2)](n-1)(P1) + [C(n-1,n-3)](n-2)(P2) + [C(n-1,n-4)](n-3)(P3) + ...
to get px , substitute x in place of n in all the terms preceeding the one where px occurs
ex: P1 = [C(1,1)](1)=1
and P2 = [C(2,2)](2) + [C(2-1,2-2)](2-1)(p1) = 3
the meaning of Px is no of reqd functions from the set {1,2,3,...,x} to itself
ie P2 = no of functions f:A→A such that f(f(x))=f(x) where A={1,2}
1select 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, ( nCr rn-r)
cheers!!
66Yes the correct answer is indeed
\sum_{k=1}^n \binom{n}{k}k^{n-k}
Basically we need to find the number of such functions which map each of the elements of set A to a fixed point of the function.