Journal of Integer Sequences, Vol. 25 (2022), Article 22.8.6

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


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A074909 A208250.)

Received September 8 2022; revised version received October 10 2022; October 12 2022; October 21 2022. Published in Journal of Integer Sequences, October 25 2022.

Return to Journal of Integer Sequences home page