The expected degree of noninvertibility of compositions of functions and a related combinatorial identity

Abstract

Recently, Defant and Propp [2020] defined the degree of noninvertibility of a function $f:X\to Y$ between two finite nonempty sets by $\text{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 \mathbb{N}$. An equivalent formulation for the definition of the degree of noninvertibility is then the starting point for a generalization yielding a seemingly new combinatorial identity involving the Stirling transform of the signed Stirling numbers of the first kind.

7 pages