The Expected Degree of Noninvertibility of Compositions of Functions
Department of Computer Science
Ben-Gurion University of the Negev
David Ben-Gurion Blvd 1
Recently, Defant and Propp defined the degree of noninvertibility of a function
between two finite nonempty sets by
. We obtain an exact formula for the expected degree of noninvertibility of the composition of
functions for every
. 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,
(Concerned with sequences
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.
Journal of Integer Sequences home page