\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{epsf}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{psfig}

\usepackage{float}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand*\Bell{\ensuremath{\boldsymbol\ell}}
\newcommand{\MC}{\textnormal{mult}}

\newcounter{relctr} 
\renewcommand*\therelctr{\alph{relctr}} 
\newcommand{\genstirlingI}[3]{
  \genfrac{[}{]}{0pt}{#1}{#2}{#3}
}
\newcommand{\genstirlingII}[3]{
  \genfrac{\{}{\}}{0pt}{#1}{#2}{#3}
}
\newcommand{\stirlingI}[2]{\genstirlingI{}{#1}{#2}}
\newcommand{\stirlingII}[2]{\genstirlingII{}{#1}{#2}}

\newcommand\labelrel[2]{
  \begingroup
    \refstepcounter{relctr}
    \stackrel{\textnormal{(\alph{relctr})}}{\mathstrut{#1}}
    \originallabel{#2}
  \endgroup
}
\AtBeginDocument{\let\originallabel\label}

\allowdisplaybreaks

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Expected Degree of Noninvertibility \\
\vskip .1in
of Compositions of Functions}
\vskip 1cm
\large
Sela Fried\footnote{The author is a postdoctoral fellow in the Department of Computer Science at the Ben-Gurion University of the Negev and a teaching fellow in the Department of Computer Science at the Israel Academic College in Ramat Gan.}\\
Department of Computer Science \\
Ben-Gurion University of the Negev\\
David Ben-Gurion Blvd 1 \\
Be'er Sheva \\
Israel \\
\href{mailto:friedsela@gmail.com}{\tt friedsela@gmail.com} \\
\end{center}

\vskip .2in

\begin{abstract}
Recently, Defant and Propp defined the degree of noninvertibility of a function $f\colon X\to Y$ between two finite nonempty sets by $\deg(f)=\frac{1}{|X|}\sum_{x\in X}|f^{-1}(f(x))|$. We obtain an exact formula for the expected degree of noninvertibility of the composition of $t$ functions for every $t\in \N$. Subsequently, we use the expected value to quantify a strengthening of a sort of a submultiplicativity property of the degree of noninvertibility. Finally, we generalize an equivalent formulation of the degree of noninvertibility and obtain a combinatorial identity involving the Stirling numbers of the first and second kind.
\end{abstract}
	
\section{Introduction}
Recently, Defant and Propp \cite{DP} defined the \emph{degree of noninvertibility} of a function $f\colon X\to Y$ between two finite nonempty sets by $$\deg(f)=\frac{1}{|X|}\sum_{x\in X}|f^{-1}(f(x))|,$$ as a measure of how far $f$ is from being injective. For example, if $f$ is $k$-to-$1$ for $1\leq k\leq |X|$, then $\deg(f)=k$. In particular, if $f$ is injective (resp., constant), then $\deg(f)=1$ (resp., $\deg(f)=|X|$). A major part of their work was devoted to the computation of the degrees of noninvertibility of specific discrete dynamical systems (i.e., functions $f\colon X\to X$), such as the Carolina solitaire map and the bubble sort map, to name a few. Turning their attention to arbitrary functions, they studied, from an extremal point of view, the connection between the degrees of noninvertibility of functions and those of their iterates. 

The main objective of this work is the calculation of the expected degree of noninvertibility of a random function, or, more generally, of the composition of $t$ random functions, for every $t\in\N$, thereby providing a probabilistic perspective on this new notion. The expected value is subsequently used to quantify a strengthening of a sort of a submultiplicativity property of the degree of noninvertibility. Additionally, an equivalent formulation of the degree of noninvertibility is generalized, yielding a combinatorial identity involving the Stirling numbers of the first and second kind.

We begin with a detailed presentation of our results. Section~\ref{sec;3} contains their proofs. In Section \ref{sec;444} we show how the degrees of noninvertibility of several specific dynamical systems, considered by Defant and Propp \cite{DP}, compare with the expected value. All the sets in this work are tacitly assumed to be nonempty and of finite sizes.

\section{Main results}
Let $t\in\N$ to be used throughout this work. 
\begin{definition}
Let $X_1,\ldots,X_{t+1}$ be $t+1$ sets of sizes $n_1,\ldots,n_{t+1}$, respectively. We denote the expected degree of noninvertibility of the composition of $t$ functions between $X_1,\ldots,X_n$ by $\mathcal{D}(X_1,\ldots,X_{t+1})$, i.e., $$\mathcal{D}(X_1,\ldots,X_{t+1}) = \frac{1}{\prod_{s=1}^{t}n_{s+1}^{n_{s}}}\sum_{\substack{f_s\colon X_{s}\to X_{s+1}\\1\leq s\leq t}}\deg(f_t\circ\cdots\circ f_1).$$
\end{definition}

Our first main result is an exact formula for the expected degree of noninvertibility of the composition of $t$ random functions.
\begin{theorem}\label{hsg}
Let $X_1,\ldots,X_{t+1}$ be $t+1$ sets of sizes $n_1,\ldots,n_{t+1}$, respectively. Then $$\mathcal{D}(X_1,\ldots,X_{t+1}) =\frac{\prod_{s=1}^{t+1}n_s-\prod_{s=1}^{t+1}(n_s-1)}{\prod_{s=2}^{t+1}n_s}.$$
\end{theorem}

In particular, if all the sets are equal, we obtain the following result.
\begin{corollary}\label{mbs}
Let $X$ be a set of size $n$. Then $$\mathcal{D}(\,\overbrace{X,\ldots,X}^{t+1\textnormal{ times}} \, ) =\frac{n^{t+1}-(n-1)^{t+1}}{n^t}.$$ Thus, $$\lim_{n\to\infty}\mathcal{D}(\, \overbrace{X,\ldots,X}^{t+1\textnormal{ times}} \,) =t+1.$$
\end{corollary}

Our second main result is concerned with a sort of a submultiplicativity property of the degree of noninvertibility \cite[Theorem 3.4]{DP}, according to which, if $X$ is a set of size $n$ and $f,g\colon X\to X$ are two functions, then \begin{equation}\label{eq;990}\deg(f\circ g)\leq \sqrt{n}\sqrt{\deg(f)}\deg(g).\end{equation} This inequality is strengthened in the following theorem. Subsequently, Corollary~\ref{mbs} is used to quantify the improvement.
\begin{theorem}\label{tha}
Let $X, Y,$ and $Z$ be three sets and let $g\colon X\to Y$ and $f\colon Y\to Z$ be two functions. Then \begin{equation}\label{eq;991}\deg(f\circ g)\leq \max_{z\in Z}|f^{-1}(z)|\deg(g).\end{equation}
\end{theorem}

That Theorem~\ref{tha} is a strengthening of (\ref{eq;990}), in the case that $X=Y=Z$, follows from the following Lemma.
\begin{lemma}\label{l; 22}
Let $X$ be a set of size $n$ and let $Y$ be an additional set. Let $f\colon X\to Y$ be a function. Then $$\max_{y\in Y}|f^{-1}(y)|\leq \sqrt{n}\sqrt{\deg(f)}.$$
\end{lemma}

To quantitatively compare between (\ref{eq;990}) and (\ref{eq;991}) (still assuming $X=Y=Z$), we notice that, by Corollary~\ref{mbs}, the order of the expectation of $\sqrt{n}\sqrt{\deg(f)}$ is $\Theta(\sqrt{n})$. On the other hand, the order of the expectation of $\max_{x\in X}|f^{-1}(x)|$ is $\Theta\left(\frac{\log (n)}{\log(\log(n))}\right)$, a result due to Gonnet \cite{Gon} (see also the references in \seqnum{A208250} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{OL}).

\bigskip

To motivate our last main result, notice that, if $f\colon X\to Y$ is a function between two sets $X$ and $Y$, then $$\deg(f)=\frac{1}{|X|}\sum_{y\in Y}|f^{-1}(y)|^2.$$ This identity, which is easy to prove and which we shall freely use throughout this work, opens the door for a generalization: For $p\in\N$, let $$\deg(f, p)=\frac{1}{|X|}\sum_{y\in Y}|f^{-1}(y)|^p.$$ We obtain an exact formula for the expected value of $\deg(f,p)$. It involves the Stirling numbers of the first and second kind, denoted by $\stirlingI{n}{k}$ and $\stirlingII{n}{k}$, respectively (e.g., \cite[pp.\ 243--253]{G}).
\begin{theorem}\label{dse}
Let $p\in\N$ and let $X$ and $Y$ be two sets of sizes $n$ and $m$, respectively. Then 
$$\frac{1}{m^n}\sum_{f\colon X\to Y}\deg(f,p)=\frac{1}{m^{p-1}}\sum_{k=1}^p\stirlingII{p}{k}\left(\sum_{j=1}^{k}(-1)^{k-j}\stirlingI{k}{j}n^{j-1}\right)m^{p-k}.$$
\end{theorem}

\section{The proofs}\label{sec;3}

Before we begin, let us introduce some notation to reduce clutter. We denote the set of nonnegative integers by $\N_0$. Let $m,n\in\N$. Bold face letters stand for vectors, i.e., $\mathbf{k}=(k_1,\ldots,k_n)$. We define $O(m, n) = \{\mathbf{k}\in \N_0^n\,:\,\sum_{i=1}^nk_i=m\}$. If $\mathbf{k}, \Bell\in\N_0^n$, we let $\mathbf{k}^{\Bell}$ stand for $\prod_{i=1}^n k_i^{\ell_i}$. We denote by $\MC(\mathbf{k})$ the multinomial coefficient corresponding to $\mathbf{k}\in O(m,n)$, i.e., $\MC(\mathbf{k})=\binom{m}{k_1,\ldots, k_n}$. Finally, if $p\in\N$ and $\mathbf{k}\in\N_0^n$, then the $p$-norm of $\mathbf{k}$ is denoted by $||\mathbf{k}||_p$, i.e., $||\mathbf{k}||_p^p=\sum_{i=1}^n k_i^p$. We set $||\mathbf{k}||_0^0 = n$.

The proof of Theorem~\ref{hsg} relies on the following lemma.
\begin{lemma}\label{iy}
Let $X_1,\ldots,X_{t+1}$ be $t+1$ sets of sizes $n_1,\ldots,n_{t+1}$, respectively. Then
$$\mathcal{D}(X_1,\ldots,X_{t+1}) =\frac{1}{n_1\prod_{s=1}^{t}n_{s+1}^{n_{s}}}\sum_{\substack{\mathbf{k}^{(s)}\in O(n_s, n_{t+1})\\1\leq s\leq t}}
\left(\prod_{r=1}^t\MC(\mathbf{k}^{(r)})(\mathbf{k}^{(r+1)})^{\mathbf{k}^{(r)}}\right)||\mathbf{k}^{(1)}||_2^2,$$ where $\mathbf{k}^{(t+1)}=(\overbrace{1,\ldots,1}^{n_{t+1}\textnormal{ times}})$.
\end{lemma}
\begin{proof} 
Assume that $X_{t+1}=\{x_1,\ldots,x_{n_{t+1}}\}$, and, for every $1\leq s\leq t$, let $f_s\colon X_s\to X_{s+1}$. For every $1\leq i\leq n_{t+1}$, we define iteratively: $X^{(t)}_{i} = f_t^{-1}(x_i), k^{(t)}_{i}= |X^{(t)}_{i}|$ and, for $1\leq s\leq t-1$, we set $X^{(s)}_{i} =  f_{s}^{-1}(X^{(s+1)}_{i}),  k^{(s)}_{i}=|X^{(s)}_{i}|$.
Then $(f_t\circ\cdots \circ f_1)^{-1}(x_i) = X^{(1)}_{i}$. Thus, $|(f_t\circ\cdots \circ f_1)^{-1}(x_i)| = k^{(1)}_{i}$. Now, for every $1 \leq s\leq t-1$, there are exactly 
$\MC(\mathbf{k}^{(s)})(\mathbf{k}^{(s+1)})^{\mathbf{k}^{(s)}}$ functions $g\colon X_s\to X_{s+1}$ such that $|g^{-1}(X^{(s+1)}_{i})|=k^{(s)}_{i}, 1\leq i\leq n_{t+1}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{hsg}]
We proceed by induction on $t$. For the induction step we shall need the following identity, from which we shall also deduce the case $t=1$: Let $m,n\in\N$ and $\mathbf{k}\in\N_0^n$. Put $r=\sum_{i=1}^nk_i$. We claim that \begin{equation}\label{en}\sum_{\Bell\in O(m,n)}\MC(\Bell)\mathbf{k}^{\Bell}||\Bell||_2^2=m(m-1)r^{m-2}||\mathbf{k}||_2^2+mr^m.\end{equation} Indeed,
\begin{align}
&\sum_{\Bell\in O(m,n)}\MC(\Bell)\mathbf{k}^{\Bell}||\Bell||_2^2\nonumber\\&=\sum_{i=1}^n\sum_{\Bell\in O(m,n)}\MC(\Bell)\mathbf{k}^{\Bell}\ell_{i}^{2}\nonumber\\&=\sum_{i=1}^n\Bigg(\sum_{\substack{\Bell\in O(m,n)\\ \ell_i=1}}\MC(\Bell)\mathbf{k}^{\Bell}\ell_{i}^{2}+\sum_{\substack{\Bell\in O(m,n)\\ \ell_i\geq 2}}\MC(\Bell)\mathbf{k}^{\Bell}\ell_{i}^{2}\Bigg)\nonumber\\&=\sum_{i=1}^n\Bigg(mk_{i}(r-k_{i})^{m-1}+m\sum_{\substack{\Bell\in O(m,n)\\ \ell_i\geq 2}}\binom{m-1}{\ell_{1},\ldots,\ell_i-1,\ldots,\ell_{n}}\mathbf{k}^{\Bell}(\ell_{i}-1+1)\Bigg)\nonumber\\&=\sum_{i=1}^n\Bigg(mk_{i}(r-k_{i})^{m-1}+k_{i}^{2}m(m-1)\sum_{\Bell\in O(m-2,n)}\MC(\Bell)\mathbf{k}^{\Bell}+mk_i\sum_{\substack{\Bell\in O(m-1,n)\\ \ell_i\geq 1}}\MC(\Bell)\mathbf{k}^{\Bell}\Bigg)\nonumber\\
&=m\sum_{i=1}^nk_i\Bigg((r-k_i)^{m-1}+k_i(m-1)r^{m-2}+\sum_{\Bell\in O(m-1,n)}\MC(\Bell)\mathbf{k}^{\Bell}-\sum_{\substack{\Bell\in O(m-1,n)\\\ell_i=0}}\MC(\Bell)\mathbf{k}^{\Bell}\Bigg)\nonumber\\
&=m\sum_{i=1}^nk_i\left((r-k_i)^{m-1}+k_i(m-1)r^{m-2}+r^{m-1}-(r-k_i)^{m-1}\right) \nonumber \\  &=m(m-1)r^{m-2}||\mathbf{k}||_2^2+mr^m.\nonumber
\end{align}
Let $t=1$. Then, using Lemma~\ref{iy}, \begin{align}\mathcal{D}(X_1,X_2) &= \frac{1}{n_1n_2^{n_1}}\sum_{\mathbf{k}^{(1)}\in O(n_1, n_2)}\MC(\mathbf{k}^{(1)})||\mathbf{k}^{(1)}||_2^2\nonumber\\&\overset{(\ref{en})}{=}\frac{n_1(n_1-1)n_2^{n_1-2}n_2+n_1n_2^{n_1}}{n_1n_2^{n_1}}\nonumber\\
&=\frac{n_1+n_2-1}{n_2}\nonumber\nonumber\\
&=\frac{n_1n_2-(n_1-1)(n_2-1)}{n_2}\nonumber.\end{align} 
Suppose that the claim holds for $t\in\N$. Using Lemma~\ref{iy} and the induction hypothesis, we have
\begin{align}
&\mathcal{D}(X_1,\ldots,X_{t+2})\nonumber \\ 
&= \frac{1}{n_1\prod_{s=1}^{t+1}n_{s+1}^{n_{s}}}\sum_{\substack{\mathbf{k}^{(s)}\in O(n_s, n_{t+2})\\1\leq s\leq t+1}}
\left(\prod_{r=1}^{t+1}\MC(\mathbf{k}^{(r)})(\mathbf{k}^{(r+1)})^{\mathbf{k}^{(r)}}\right)||\mathbf{k}^{(1)}||_2^2\nonumber\\
&=\frac{1}{n_1\prod_{s=1}^{t+1}n_{s+1}^{n_{s}}}\sum_{\substack{\mathbf{k}^{(s)}\in O(n_s, n_{t+2})\\2\leq s\leq t+1}}
\left(\prod_{r=2}^{t+1}\MC(\mathbf{k}^{(r)})(\mathbf{k}^{(r+1)})^{\mathbf{k}^{(r)}}\right)\sum_{\mathbf{k}^{(1)}\in O(n_1, n_{t+2})}
\MC(\mathbf{k}^{(1)})(\mathbf{k}^{(2})^{\mathbf{k}^{(1)}}||\mathbf{k}^{(1)}||_2^2\nonumber\\
&\overset{(\ref{en})}{=}\frac{1}{n_1\prod_{s=1}^{t+1}n_{s+1}^{n_{s}}}\sum_{\substack{\mathbf{k}^{(s)}\in O(n_s, n_{t+2})\\2\leq s\leq t+1}}
\left(\prod_{r=2}^{t+1}\MC(\mathbf{k}^{(r)})(\mathbf{k}^{(r+1)})^{\mathbf{k}^{(r)}}\right)\left(n_1(n_1-1)n_2^{n_1-2}||\mathbf{k}^{(2)}||_2^2+n_1n_2^{n_1}\right)\nonumber\\
&=\frac{n_1n_2^{n_1}\prod_{s=2}^{t+1}n_{s+1}^{n_{s}}}{n_1\prod_{s=1}^{t+1}n_{s+1}^{n_{s}}}+\frac{n_1-1}{n_{2}^2\prod_{s=2}^{t+1}n_{s+1}^{n_{s}}}\sum_{\substack{\mathbf{k}^{(s)}\in O(n_s, n_{t+2})\\2\leq s\leq t+1}}
\left(\prod_{r=2}^{t+1}\MC(\mathbf{k}^{(r)})(\mathbf{k}^{(r+1)})^{\mathbf{k}^{(r)}}\right)||\mathbf{k}^{(2)}||_2^2\nonumber\\
&=1+(n_1-1)\frac{\prod_{s=2}^{t+2}n_s-\prod_{s=2}^{t+2}(n_s-1)}{n_2\prod_{s=3}^{t+2}n_s}\nonumber\\
&=\frac{\prod_{s=1}^{t+2}n_{s}-\prod_{s=1}^{t+2}(n_{s}-1)}{\prod_{s=2}^{t+2}n_{s}}.\nonumber\qedhere
\end{align}
\end{proof}

\begin{proof}[Proof of Corollary~\ref{mbs}]
We have
\begin{align}
    \mathcal{D}(\, \overbrace{X,\ldots,X}^{t+1\textnormal{ times}} \, ) &=\frac{n^{t+1}-(n-1)^{t+1}}{n^t}\nonumber\\&=\frac{1}{n^t}\sum_{s=0}^{t}(-1)^{s}\binom{t+1}{s+1}n^{t-s}\nonumber\\&=t+1+\sum_{s=1}^{t}(-1)^{s}\binom{t+1}{s+1}\frac{1}{n^s}\nonumber
\end{align} and the assertion follows.
\end{proof}

\begin{remark}
The coefficients in the sum $\sum_{s=0}^{t}(-1)^{s}\binom{t+1}{s+1}n^{t-s}$ correspond to the $t+1$th row of Pascal's triangle with alternating signs, omitting the first $1$. For example, for $t=1,2$, and $3$, the sum has the form
\begin{align}
    & 2n-1,\nonumber\\
    & 3n^2-3n+1, \textnormal{ and}\nonumber\\
    & 4n^3-6n^2+4n-1,\nonumber
\end{align} respectively.
\end{remark}

Only a small modification of the proof of  \cite[Theorem 3.4]{DP} is necessary to prove Theorem~\ref{tha}. We give the full proof for completeness.
\begin{proof}[Proof of Theorem~\ref{tha}]
Let $z_1,\ldots,z_r\in Z$ be such that $f(g(X)) = \{z_1,\ldots,z_r\}$. For every $1\leq i\leq r$, let $k_i = |f^{-1}(z_i)|$ and let $y_{i1},\ldots, y_{ik_i}\in Y$ be such that $f^{-1}(z_i)=\{y_{i1},\ldots, y_{ik_i}\}$. Furthermore, for $1\leq i\leq r$ and $1\leq j\leq k_i$, let $\ell_{ij}=|g^{-1}(y_{ij})|$. We have \begin{align}
    \deg(f\circ g)&=\frac{1}{n}\sum_{i=1}^r |g^{-1}(f^{-1}(z_i))|^2\nonumber\\&=\frac{1}{n}\sum_{i=1}^r \left(\sum_{j=1}^{k_i}\ell_{ij}\right)^2\nonumber\\&\labelrel\leq{myeq:equality99}\frac{1}{n}\sum_{i=1}^rk_i \sum_{j=1}^{k_i}\ell_{ij}^2\nonumber\\&\leq\max_{z\in Z}|f^{-1}(z)|\overbrace{\frac{1}{n}\sum_{i=1}^r \sum_{j=1}^{k_i}\ell_{ij}^2}^{\labelrel={myeq:equality100}\deg(g)}\nonumber\\&=\max_{z\in Z}|f^{-1}(z)|\deg(g),\nonumber
\end{align} where in \eqref{myeq:equality99} we used the Cauchy-Schwarz inequality and \eqref{myeq:equality100} is due to the fact that \[g(X)\subseteq f^{-1}(f(g(X))) = \{y_{ij} \,:\, 1\leq i\leq r, 1\leq j\leq k_i\}.\qedhere\]
\end{proof}

\begin{proof}[Proof of Lemma~\ref{l; 22}]
Assume that $Y$ is of size $m$. Applying the inequality $||x||_\infty \leq ||x||_2$, which holds for every $x\in\R^m$, on the vector in $\R^m$, whose entries correspond to the sizes of the preimages under $f$ of all the elements of $Y$, we obtain
\[\max_{y\in Y}|f^{-1}(y)|\leq \sqrt{\sum_{y\in Y}|f^{-1}(y)|^2} =\sqrt{n}\sqrt{\frac{1}{n}\sum_{y\in Y}|f^{-1}(y)|^2}= \sqrt{n}\sqrt{\deg(f)}.\qedhere\]
\end{proof}

\begin{proof}[Proof of Theorem~\ref{dse}] 
We proceed by induction on $p$ and prove that, for every $m,n\in\N$ and $p\in\N_0$, we have 
\begin{align}
&\sum_{\mathbf{k}\in O(n,m)}\MC(\mathbf{k})||\mathbf{k}||_p^p\nonumber\\&=
\begin{cases}
nm^{n-(p-1)}\sum_{k=1}^p\stirlingII{p}{k}\left(\sum_{j=1}^{k}(-1)^{k-j}\stirlingI{k}{j}n^{j-1}\right)m^{p-k},& \text{if } p\geq 1;\\ m^{n+1}, &\text{otherwise.}
\end{cases}\nonumber
\end{align} The cases $p=0,1$ or $n=1$ are immediate. Suppose that the assertion holds for every $m,n\in\N$ and every $0\leq r\leq p$. Assume that $n\geq 2$. We have
\begin{align}
&\sum_{\mathbf{k}\in O(n,m)}\MC(\mathbf{k})||\mathbf{k}||_{p+1}^{p+1}\nonumber\\
&=n\sum_{i=1}^m\sum_{\substack{\mathbf{k}\in O(n,m)\\k_i\geq 1}}\binom{n-1}{k_{1},\dots,k_{i}-1,\dots,k_m}(k_{i}-1+1)^p\nonumber\\
&=n\sum_{r=0}^p\binom{p}{r}\sum_{i=1}^m\sum_{\substack{\mathbf{k}\in O(n,m)\\k_i\geq 1}}\binom{n-1}{k_{1},\dots,k_{i}-1,\dots,k_m}(k_{i}-1)^r\nonumber\\
&=n\sum_{r=0}^p\binom{p}{r}\sum_{\mathbf{k}\in O(n-1,m)}\MC(\mathbf{k})||\mathbf{k}||_r^r\nonumber\\&\labelrel={myeq:equality}n\sum_{r=1}^p\binom{p}{r} (n-1)m^{n-r}\sum_{k=1}^{r}\stirlingII{r}{k} \left(\sum_{j=1}^{k}(-1)^{k-j}\stirlingI{k}{j}(n-1)^{j-1}\right)m^{r-k}+nm^n\nonumber\\
&=nm^{n-t}\sum_{k=1}^p\overbrace{\sum_{r=k}^p\binom{p}{r} \stirlingII{r}{k}}^{\labelrel={myeq:equality1}\stirlingII{p+1}{k+1} } \left(\sum_{j=1}^{k}(-1)^{k-j}\stirlingI{k}{j}\overbrace{(n-1)^j}^{=\sum_{l=0}^j\binom{j}{l}(-1)^ln^{j-l}}\right)m^{p-k}+nm^n\nonumber\\
&=nm^{n-p}\sum_{k=1}^p\stirlingII{p+1}{k+1} \left(\overbrace{\sum_{j=1}^{k}\sum_{l=0}^j(-1)^{k+l-j}\binom{j}{l}\stirlingI{k}{j}n^{j-l}}^{\labelrel={myeq:equality2}\sum_{j=0}^{k}(-1)^{k-j}\stirlingI{k+1}{j+1}n^{j}}\right)m^{p-k}+nm^{n-p}m^p\nonumber\\
&=nm^{n-p}\left(\sum_{k=1}^p\stirlingII{p+1}{k+1} \left(\sum_{j=0}^{k}(-1)^{k-j}\stirlingI{k+1}{j+1}n^{j}\right)m^{p-k}+m^p\right)\nonumber\\
&=nm^{n-p}\sum_{k=1}^{p+1} \stirlingII{p+1}{k} \left(\sum_{j=1}^{k}(-1)^{k-j}\stirlingI{k}{j}n^{j-1}\right)m^{p+1-k},\nonumber
\end{align} where, in \eqref{myeq:equality}, we used the induction hypothesis,  \eqref{myeq:equality1} is due to \cite[Eq.~(6.15)]{G}, and \eqref{myeq:equality2} follows after several algebraic manipulations, together with \cite[Eq.~(6.16)]{G}.
\end{proof}
 
\section{The limiting behavior of the degrees of noninvertibility of several specific dynamical systems}\label{sec;444}
Let $X$ be a set of size $n$. By Corollary~\ref{mbs}, the expected degree of noninvertibility of a dynamical system $f\colon X\to X$ tends to $2$, as $n\to\infty$. Defant and Propp \cite{DP} established the degrees of noninvertibility of several specific dynamical systems. Table \ref{t;1} below summarizes their limiting behavior. Interestingly, in the cases where the limit is finite, it is not far from the expected value. 

\section{Acknowledgments}
We thank the anonymous referee for the careful reading of the manuscript and for the helpful suggestions. We are also grateful to J.~Propp for suggesting us the consideration of compositions of functions.

\begin{table}[H]
\begin{center}
\begin{tabular}{| c| c| c |c|}
\hline
 The dynamical system $f$ & The set $X$ & $\lim_{n\to\infty}\deg(f)$& Remarks \\ 
 \hline
 Bubble sort (for permutations) & $\text{Sym}(n)$ & $\infty$ &\\ 
 Stack-sorting & $\text{Sym}(n)$ & $\infty$ &\\ 
 Nibble sort (for permutations) & $\text{Sym}(n)$ & $4e-9$ & $\approx 1.873$\\
 Nibble sort (for binary words) & $\{0,1\}^n$ & $3/2$&   \\
 Binary chip-firing on an $n+1$-cycle & $\{0,1\}^n$ & $3/2$&   \\
  Bulgarian solitaire & partitions of $n$ & $3$ & conjectured  \\
  Carolina solitaire & compositions of $n$ & $\infty$ &  \\
 \hline
\end{tabular}
\caption{The limiting behavior of the degrees of noninvertibility of several specific dynamical systems, established by Defant and Propp \cite{DP}.}
\label{t;1}
\end{center}
\end{table}

\begin{thebibliography}{9}
	\bibitem{DP}
	C.~Defant and J.~Propp,
	Quantifying noninvertibility in discrete dynamical systems,
	{\it Electron.~J.~Combin.}
	{\bf 27} (2020),
	Article P3.51.
        \bibitem{Gon}
        G.~H.~Gonnet, Expected length of the longest probe sequence in hash code searching, {\it J.\ ACM}
        {\bf 28} (1981), 289--304.        
	\bibitem{G}
	R.~L.~Graham, D.~E.~Knuth, O.~Patashnik, and S.~Liu,
        {\it Concrete {M}athematics}, Addison-Wesley, 1989.        
        \bibitem{OL}
        N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS  Foundation  Inc., \url{https://oeis.org}. 
\end{thebibliography}

	
	
\bigskip
\hrule
\bigskip
	
\noindent 
2010 \emph{Mathematics Subject Classification}:~Primary 05A99; 
Secondary 37A99.	
	
\medskip
	
\noindent 
\emph{Keywords}:~degree of noninvertibility, dynamical system, Stirling number. 	
	
\bigskip
\hrule
\bigskip
	
\noindent 
(Concerned with sequences 
\seqnum{A074909} and
\seqnum{A208250}.)
	
\bigskip
\hrule
\bigskip
	
\vspace*{+.1in}
\noindent
Received September 8 2022; 
revised version received October 10 2022; October 12 2022; October 21 2022.
Published in {\it Journal of Integer Sequences}, October 25 2022.
	
\bigskip
\hrule
\bigskip
	
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
 


\end{document}

