Notation: $ [m] := \{1, 2, \dots, m \}$ .

How many functions are there $ f: [a] \to [b]$ ? The answer is easily seen to be $ b^a$ .

How many $ 1$ -to-$ 1$ functions are there $ f: [a] \to [b]$ ? Again the answer is well known, and it is sometimes called the falling factorial: $ $ b(b-1) \dots (b-a+1).$ $

How many functions are there $ f: [a] \to [b]$ that are no more than $ c$ -to-$ 1$ ?

I don’t expect that there is an exact formula, and I am more interested in the asymptotics. For example, can we give “reasonable” upper and lower bounds, in the case that $ c \ge 2$ and $ |A| / |B|$ are fixed, and $ |A| \to \infty$ ?

For a concrete example, roughly how many functions are there $ [5n] \to [n]$ that are at most $ 8$ -to-$ 1$ ? Call this function $ g(n)$ .

Clearly we have $ $ \frac{(5n)!}{5!^n} \le g(n) \le n^{5n}.$ $ The function $ {(5n)!}/{5!^n}$ counts functions that are exactly 5-to-1 (which all satisfy the criterion that they are at most 8-to-1), and the function $ n^{5n}$ counts all functions.

Applying Stirling’s approximation to the first function gives something like $ $ \alpha^n n^{5n} \le g(n) \le n^{5n},$ $ for some small constant $ \alpha > 0$ .

It seems like there is room for improvement. Is it true, for example, that $ $ \log g(n) = 5n \log n + C n + o(n) $ $ for some constant $ C > 0$ ?