Estimating the number of functions which are at most $c$-to-$1$ for some constant $c \ge 2$

Question

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$?

Answer 1

Let us just consider $g(n)$, and the general problem admits a similar treatment.
Note that $g(n)$ equals $$ \sum_{\substack{a_1, \ldots, a_n \\ a_i \le 8 \\ a_1+\ldots +a_n = 5n}} \frac{(5n)!}{a_1! a_2! \cdots a_n!}. $$ We may see this by thinking of the inverse image of $1$ (a set of size $a_1$) etc.

Here is a simple way to get an upper bound: For any $x>0$ we must have $$ g(n) \le (5n)! x^{-5n} \sum_{\substack{a_1,\ldots, a_n \\ a_i \le 8} } \prod_{i=1}^{n} \frac{x^{a_i}}{a_i!} = (5n)! x^{-5n} \Big( \sum_{a=0}^{8} \frac{x^a}{a!}\Big)^n. $$ Now choose $x$ so as to make $x^{-5} \sum_{a=0}^{8} x^a/a!$ a minimum. This is attained for $x \approx 5.535$, and its value is $\approx 0.0434797 \ldots$. We conclude that $$ g(n) \le (5n)! (0.0434797\ldots)^n, $$ which is about $(0.9155\ldots)^n n^{5n}$ using Stirling. In other words, an improvement over the $n^{5n}$ bound you state.

Now one might expect this to be the right answer -- it often is in many similar situations. The idea now would be to use Cauchy's theorem to write $$ g(n) = \frac{(5n)!}{2\pi i} \int_{|z|=r} \Big( \sum_{a=0}^{8} \frac{z^a}{a!}\Big)^n \frac{dz}{z^{5n+1}}, $$ and to choose $r \approx 5.535\ldots $ as above. This is the saddle point method, and typically one would get that the contribution to the integral around $z= r$ is dominant, and that there is an arc (probably of length about $1/\sqrt{n}$ around $r$) which will give fine asymptotics for the integral.

Answer 2

This is closely related to Lucia's answer.

For parameter $t$, let $X_t$ be the random variable with probability generating function $$ p_t(x) = \sum_{i=0}^c \mathrm{P}(X_t=i)\, x^i = \sum_{i=0}^c \frac{x^it^i}{i!}\biggm/ \sum_{i=0}^c \frac{t^i}{i!}. $$ Adjust $t$ so that the expectation of $X_t$ is $b/a$, and let $\sigma^2$ be its variance for that $t$.

Then the number of desired functions is asymptotically $$\frac{a!\,t^{-b}}{\sigma\,\sqrt{2\pi a}} \biggl(\sum_{i=0}^c \frac{t^i}{i!}\biggr)^a.$$

This assumes that $X_t$ is suitable for applying the central limit theorem to the sum of $a$ independent copies.