  Given a finite set $X$ and a function $f:X\to X$, we define the degree of
noninvertibility of $f$ to be
$\displaystyle\text{deg}(f)=\frac{1}{|X|}\sum_{x\in X}|f^{-1}(f(x))|$. This is
a natural measure of how far the function $f$ is from being bijective. We
compute the degrees of noninvertibility of some specific discrete dynamical
systems, including the Carolina solitaire map, iterates of the bubble sort map
acting on permutations, bubble sort acting on multiset permutations, and a map
that we call "nibble sort." We also obtain estimates for the degrees of
noninvertibility of West's stack-sorting map and the Bulgarian solitaire map.
We then turn our attention to arbitrary functions and their iterates. In order
to compare the degree of noninvertibility of an arbitrary function $f:X\to X$
with that of its iterate $f^k$, we prove that \[\max_{\substack{f:X\to X\\
|X|=n}}\frac{\text{deg}(f^k)}{\text{deg}(f)^\gamma}=\Theta(n^{1-1/2^{k-1}})\]
for every real number $\gamma\geq 2-1/2^{k-1}$. We end with several conjectures
and open problems.
