?
Об образах и прообразах в графе композиции независимых равновероятных случайных отображений
We study the probability characteristics of the random mapping graph $ f_{\left[k\right]} $ --- the composition $k\in \mathbb{N}$ of independent equiprobable random mappings $ f_1, \ldots, f_k $, where $f_i\colon \left\{1,\ldots,n\right\}\to \left\{1,\ldots,n\right\}$, $n\in\mathbb{N}$, $i=1,\ldots,n$. The following results are obtained.
Let $k\in \mathbb{N}$ and random mappings $f_1,\ldots,f_k$ be independent with the equiprobable distribution on $\mathfrak{S}$. Then for any fixed $x,y\in S,\, x\ne y$,
\begin{equation}\notag
\mathbf{P}\left\{f_{\left[k\right]}\left(x\right)=f_{\left[k\right]}\left(y\right)\right\}=\sum\limits_{\begin{smallmatrix}s_1,\ldots,s_{k-1}\colon\\2\geqslant s_1\geqslant\ldots\geqslant s_{k-1}
\end{smallmatrix}}\frac{q\left(2,s_{1}\right)}{n^{s_{k-1}-1}}\prod\limits_{i=1}^{k-2}q\left(s_i,s_{i+1}\right),
\end{equation}
where $q\left(a,b\right)=C_{n}^{n-b} \left(\frac{b}{n}\right)^a
\sum_{l=0}^{b}C_{b}^l(-1)^l\left(1-\frac{l}{b}\right)^a$.
For any fixed $x\in S$
\begin{multline}\notag
\mathbf{P}\left\{ x\in f_{\left[k\right]}\left(S\right)\right\}=\frac1{n}\sum\limits_{l=1}^{n}{\left(\frac{\left(n\right)_l}{n^l} \right)^k}+\\
+\sum\limits_{l=1}^{n-2}\sum\limits_{t=1}^{n-l-1}\sum\limits_{m=1}^{n-t-l}\left(-1\right)^{m-1}C_{n-1}^m\sum\limits_{\begin{smallmatrix}s_1,\ldots,s_{k-1}\colon\\m\geqslant s_1\geqslant\ldots\geqslant s_{k-1}
\end{smallmatrix}}\frac{q\left(m,s_{1}\right)}{n^{s_{k-1}}}\prod\limits_{i=1}^{k-2}q\left(s_i,s_{i+1}\right)V^{\left\{k,m\right\}}_{s_1,\ldots,s_{k-1}},
\end{multline}
where $q\left(a,b\right)=C_{n}^{n-b} \left(\frac{b}{n}\right)^a
\sum_{l=0}^{b}C_{b}^l(-1)^l\left(1-\frac{l}{b}\right)^a$, $V^{\left\{k,m\right\}}_{s_1,\ldots,s_{k-1}}$ is determined by the ratio~\eqref{V{k,m}} and $(n)_z=n(n-1)\dots(n-z+1)$.
For any fixed $x\in S\backslash S'$ and for any $r\in \{1,\ldots,n-1\}$, $S'\subseteq S\colon |S'|=r$, $z\in \{1,\ldots,n\}$
\begin{multline}\notag
\mathbf{P}\left\{\tau_{f_{\left[k\right]}}\left(x\right)=z,\mathcal{R}_{f_{\left[k\right]}}\left(x\right)\cap S'=\varnothing \right\}=\\
=\left(1-\left(1-\frac{z}{n}\right)\left( 1-\frac{z-1}{n} \right)^{k-1}\right)\left(\frac{\left(n\right)_{z-1}}{n^{z-1}} \right)^{k-1}\frac{\left(n\right)_{r+z}}{n^{z-1}\left(n\right)_{r+1}},
\end{multline}
where $\mathcal{R}_{f_{\left[k\right]}}\left(x\right)$ is the aperiodicity segment of vertex $x$ in the graph of mapping $f_{\left[k\right]}$ (see def.~\ref{D-tau_f}), $\tau_{f_{\left[k\right]}}\left(x\right)=\min\left\{ t\in \mathbb{N}\colon {f_{\left[k\right]}}^t\left(x\right)\in \left\{ x,{f_{\left[k\right]}}\left(x\right),\dots,{f_{\left[k\right]}}^{t-1}\left(x\right) \right\} \right\}.$
For any fixed $x,y\in S,\, x\ne y$, and for any $r\in\{1,\ldots,n\}$
\begin{equation}\notag
\mathbf{P}\left\{y \in \left(f_{\left[k\right]}\right)^{-r}\left(x\right)\right\}=\frac1n\left(1-\frac1{n-1}\sum\limits_{z\in Q_r\backslash\{1\}}\left(\frac{\left(n\right)_z}{n^z}\right)^k\right),
\end{equation}
where $Q_r$ is determined by the equality~\eqref{Q^j_i}.