=4in

The Expected Degree of Noninvertibility
of Compositions of Functions Sela Fried¹
Department of Computer Science
Ben-Gurion University of the Negev
David Ben-Gurion Blvd 1
Be'er Sheva
Israel
friedsela@gmail.com

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}{\vert X\vert}\sum_{x\in X}\vert f^{-1}(f(x))\vert$. We obtain an exact formula for the expected degree of noninvertibility of the composition of $t$ functions for every $t\in \mathbb{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.