Probability problem involving mappings of a finite set into itself.

Question

One mapping is selected at random from all the mappings of the set $\{1,2,\ldots,n\}$ into itself. What is the probability that

$(i)$ a specified element $i$ is transformed into another specified element $j$?

$(ii)$ the elements $i_1,i_2,\ldots,i_h$ are transformed into the elements $j_1,j_2,\ldots,j_h$ respectively?

Answer 1

For (ii) suppose that the $i_k$ are all distinct, and the $j_k$ are all distinct. There are $n(n-1)(n-2)\cdots(n-h+1)=n!/(n-h)!$ $h$-tuples of distinct elements from $\{1,2,\ldots,n\}$. It is equally likely that your first $h$-tuple is taken to any one of them, so the probability you seek is $(n-h)!/n!$.

Answer 2

i) the probability is simply $\frac1{n}$, since only one $j$ will work out of $n$ of them.

ii) there are $n!$ ways to arrange an injective function. Only $\binom nh$ works. Therefore the probability is $\frac{h!}{n!}$.

Answer 3

Since there are no restrictions on these maps $f:\>[n]\to[n]$ there are $n^n$ of them.

(i) Given $i$, $j\in[n]$ the probability that $f(i)=j$ is $\>{1\over n}$.

(ii) Given a subset $A=\{i_1,i_2,\ldots, i_h\}\subset [n]$ with $|A|=h$ and values $j_k\in [n]$ $(1\leq k\leq h)$ the probability that $f(i_k)=j_k$ for $1\leq k\leq h$ is $\ n^{-h}\>$.