It is well-known that the number of surjections from a set of size n to a set of size m is quite a bit harder to calculate than the number of functions or the number of injections. (Of course, for surjections I assume that n is at least m and for injections that it is at most m.) It is also well-known that one can get a formula for the number of surjections using inclusion-exclusion, applied to the sets $X\_1,...,X\_m$, where for each $i$ the set $X\_i$ is defined to be the set of functions that never take the value $i$. This gives rise to the following expression: $m^n-\binom m1(m-1)^n+\binom m2(m-2)^n-\binom m3(m-3)^n+\dots$.


Let us call this number $S(n,m)$. I'm wondering if anyone can tell me about the asymptotics of $S(n,m)$. A particular question I have is this: for (approximately) what value of $m$ is $S(n,m)$ maximized? It is a little exercise to check that there are more surjections to a set of size $n-1$ than there are to a set of size $n$. (To do it, one calculates $S(n,n-1)$ by exploiting the fact that every surjection must hit exactly one number twice and all the others once.) So the maximum is not attained at $m=1$ or $m=n$. 


I'm assuming this is known, but a search on the web just seems to lead me to the exact formula. A reference would be great. A proof, or proof sketch, would be even better.


**Update.** I should have said that my real reason for being interested in the value of m for which S(n,m) is maximized (to use the notation of this post) or m!S(n,m) is maximized (to use the more conventional notation where S(n,m) stands for a Stirling number of the second kind) is that what I care about is the rough size of the sum. The sum is big enough that I think I'm probably not too concerned about a factor of n, so I was prepared to estimate the sum as lying between the maximum and n times the maximum.



How many surjections are there from a set of size n?
It seems to be the case that the polynomial $P\_n(x) =\sum\_{m=1}^n
m!S(n,m)x^m$ has only real zeros. (I know it is true that $\sum\_{m=1}^n
S(n,m)x^m$ has only real zeros.) If this is true, then the value of $m$ 
maximizing $m!S(n,m)$ is within 1 of $P'\_n(1)/P\_n(1)$ by a theorem of 
J. N. Darroch, *Ann. Math. Stat.* **35** (1964), 1317-1321. See also 
J. Pitman, *J. Combinatorial Theory, Ser. A* **77** (1997), 279-303. 
By standard combinatorics
 $$ \sum\_{n\geq 0} P\_n(x) \frac{t^n}{n!} = \frac{1}{1-x(e^t-1)}. $$
Hence 
 $$ \sum\_{n\geq 0} P\_n(1)\frac{t^n}{n!} = \frac{1}{2-e^t} $$
 $$ \sum\_{n\geq 0} P'\_n(1)\frac{t^n}{n!} = \frac{e^t-1}{(2-e^t)^2}. $$
Since these functions are meromorphic with smallest singularity at $t=\log 2$, 
it is routine to work out the asymptotics, though I have not bothered to 
do this.


**Update.** It is indeed true that $P\_n(x)$ has real zeros. This is because
$(x-1)^nP\_n(1/(x-1))=A\_n(x)/x$, where $A\_n(x)$ is an Eulerian polynomial. It 
is known that $A\_n(x)$ has only real zeros, and the operation $P\_n(x) 
\to (x-1)^nP\_n(1/(x-1))$ leaves invariant the property of having real
zeros.


