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

preprint2022arXivOpen access

Abstract

Recently, Defant and Propp [2020] defined the degree of noninvertibility of a function f ⁣:X→Yf\colon X\to Y between two finite nonempty sets by deg(f)=1∣X∣∑x∈X∣f−1(f(x))∣\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 tt functions for every t∈Nt\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.