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.

anyonehas a question of the form "what is this function f:N-->N" then one very natural thing to do is to compute the first 10 values or so and then type it in to Sloane. research.att.com/~njas/sequences/index.html . If it's there then there will be references where you can read further. If it's not then this is evidence that little is known about it. I tried it with this sequence and got "ceiling of (n/sqrt(2))". Given that this is not the answer (e.g. f(1000)=722 and n/sqrt(2)=707.10678...) one might suspect that no exact formula is known but that n/sqrt(2) is close. $\endgroup$ – Kevin Buzzard Jun 25 '10 at 12:231more comment