How many surjections are there from a set of size n? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T20:46:06Z http://mathoverflow.net/feeds/question/29490 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n How many surjections are there from a set of size n? gowers 2010-06-25T10:34:19Z 2010-06-28T20:27:51Z <p>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$.</p> <p>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$. </p> <p>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.</p> <p><strong>Update.</strong> 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.</p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29493#29493 Answer by Andrey Rekalo for How many surjections are there from a set of size n? Andrey Rekalo 2010-06-25T10:52:48Z 2010-06-25T12:12:15Z <p>This looks like the Stirling numbers of the second kind (up to the $m!$ factor). </p> <p><a href="http://www.emis.de/journals/INTEGERS/papers/i27/i27.pdf" rel="nofollow">This</a> and <a href="http://www.math.dartmouth.edu/~carlp/PDF/rod7.pdf" rel="nofollow">this</a> papers are specifically devoted to the maximal Striling numbers. It seems that for large $n$ the relevant asymptotic expansion is $$k! S(n,k)= (e^r-1)^k \frac{n!}{r^n}(2\pi k B)^{-1/2}\left(1-\frac{6r^2\theta^2 +6r\theta+1}{12re^r}+O(n^{-2})\right),$$ where $$e^r-1=k+\theta,\quad \theta=O(1),$$ $$B=\frac{re^{2r}-(r^2+r)e^r}{(e^r-1)^2}.$$ </p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29502#29502 Answer by Michael Burge for How many surjections are there from a set of size n? Michael Burge 2010-06-25T11:40:32Z 2010-06-25T12:45:48Z <p>If f is an arbitrary surjection from N onto M, then we can think of f as partitioning N into m different groups, each group of inputs representing the same output point in M. The Stirling Numbers of the second kind count how many ways to partition an N element set into m groups. But this undercounts it, because any permutation of those m groups defines a different surjection but gets counted the same. There are m! such permutations, so our total number of surjections is</p> <p>m! S(n,m)</p> <p>To look at the maximum values, define a sequence S_n = n - M_n where M_n is the m that attains maximum value for a given n - in other words, S_n is the "distance from the right edge" for the maximum value. Computer-generated tables suggest that this function is constant for 3-4 values of n before increasing by 1. If this is true, then the m coordinate that maximizes m! S(n,m) is bounded by n - ceil(n/3) - 1 and n - floor(n/4) + 1.</p> <p>I have no proof of the above, but it gives you a conjecture to work with in the meantime.</p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29510#29510 Answer by Pietro Majer for How many surjections are there from a set of size n? Pietro Majer 2010-06-25T13:14:55Z 2010-06-25T13:31:29Z <p>I don't have a precise reference for your problem (given $n$ find "the most surjected" $m$); waiting for a precise one, I can say that I think the standard starting point should be as follows. To avoid confusion I modify slightly your notation for the surjections from an $n$ elements set to an $m$ elements set into $\mathrm{Sur}(n,m).$ One has the generating function (coming e.g. from the analogous g.f. for Stirling numbers of second kind)</p> <p>$$(e^x-1)^m\,=\sum_{n\ge m}\ \mathrm{Sur}(n,m)\ \frac{x^n}{n!}\ ,$$</p> <p>whence by the Cauchy formula with a simple integration contour around 0 ,</p> <p>$$\frac{\mathrm{Sur}(n,m)}{n!}={1 \over 2\pi i} \oint \frac{(e^z-1)^m}{z^{n+1}}dz$$</p> <p>For a circular path $re^{it}$ we find</p> <p>$$\frac{\mathrm{Sur}(n,m)}{n!}={1 \over 2\pi } \int_{-\pi}^{\pi}\left(\exp(re^{it})-1\right)^m e^{-int} dt\ .$$</p> <p>This holds for any number $r>0$, and the most convenient one should be chosen according to the stationary phase method; here a change of variable followed by dominated convergence may possibly give a convergent integral, producing an asymptotics: this is e.g. how one can derive the Stirling asymptotics for n!.</p> <p>In your case, the problem is: for a given $n$ (large) maximize the integral in $m$, and give asymptotic expansions for the maximal $m$ (the first order should be $\lambda n + O(1)$ with $2/3\leq \lambda\leq 3/4$ according to Michael Burge's exploration). This seems to be tractable; for the moment I leave this few hints hoping they are useful, but I'm very curious to see the final answer.</p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29564#29564 Answer by Richard Stanley for How many surjections are there from a set of size n? Richard Stanley 2010-06-26T00:15:19Z 2010-06-26T16:55:38Z <p>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, <em>Ann. Math. Stat.</em> <strong>35</strong> (1964), 1317-1321. See also J. Pitman, <em>J. Combinatorial Theory, Ser. A</em> <strong>77</strong> (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.</p> <p><strong>Update.</strong> 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.</p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29632#29632 Answer by Terry Tao for How many surjections are there from a set of size n? Terry Tao 2010-06-26T18:49:20Z 2010-06-26T19:41:21Z <p>I found <a href="http://www.ams.org/mathscinet-getitem?mr=1223774" rel="nofollow">this paper</a> of Temme (available <a href="http://oai.cwi.nl/oai/asset/2304/2304A.pdf" rel="nofollow">here</a>) that gives an explicit but somewhat complicated asymptotic for the Stirling number S(n,m) of the second kind, by the methods alluded to in previous answers (generating functions -> contour integral -> steepest descent)</p> <p>Here's the asymptotic (as copied from that paper). One first sets</p> <p>$t_0 := \frac{n-m}{m}$</p> <p>and finds the positive real number $x_0$ solving the transcendental equation</p> <p>$\frac{1-e^{-x_0}}{x_0} = \frac{m}{n}$</p> <p>(one has the asymptotics $x_0 \approx 2(1-m/n)$ when $m/n$ is close to 1, and $x_0 \approx n/m$ when $m/n$ is close to zero.) One then defines</p> <p>$A := \phi(x_0) - m t_0 + (n-m) t_0$</p> <p>where</p> <p>$\phi(x) := - n \ln x + m \ln(e^x - 1).$</p> <p>(Note: $x_0$ is the stationary point of $\phi(x)$.) One has an integral representation</p> <p>$S(n,m) = \frac{n!}{m!} \frac{1}{2\pi i} \int e^{\phi(x)} \frac{dx}{x}$</p> <p>where the integral is a small contour around the origin. The saddle point method then gives</p> <p>$S(n,m) = (1+o(1)) e^A m^{n-m} f(t_0) \binom{n}{m}$</p> <p>where</p> <p>$f(t_0) := \sqrt{\frac{t_0}{(1+t_0)(x_0-t_0)}}$</p> <p>and o(1) goes to zero as $n \to \infty$ (uniformly in m, I believe). </p> <p>In principle, one can now approximate $m! S(n,m)$ to within o(1) and compute its maximum in finite time, but this seems somewhat tedious. It does seem though that the maximum is attained when $m/n = c+o(1)$ for some explicit constant $0 &lt; c &lt; 1$.</p> <p>EDIT: Actually, it's clear that the maximum is going to be obtained in the range $n/e \leq m \leq n$ asymptotically, because $m! S(n,m)$ equals $n! \approx (n/e)^n$ when $m=n$, and on the other hand we have the trivial upper bound $m! S(n,m) \leq m^n$. Among other things, this makes $x_0$ and $t_0$ bounded, and so the f(t_0) term is also bounded and not of major importance to the asymptotics. The other terms however are still exponential in n...</p> <p>EDIT: There is also the identity</p> <p>$\sum_{k=1}^n (k-1)! S(n,k) = (-1)^n Li_{1-n}(2)$</p> <p>where $Li_s$ is the <a href="http://en.wikipedia.org/wiki/Polylogarithm" rel="nofollow">polylogarithm</a> function. So, up to a factor of n, the question is the same as that of obtaining an asymptotic for $Li_{1-n}(2)$ as $n \to -\infty$. This seems quite doable (presumably from yet another contour integration and steepest descent method) but a quick search of the extant asymptotics didn't give this immediately.</p> http://mathoverflow.net/questions/29490/how-many-surjections-are-there-from-a-set-of-size-n/29827#29827 Answer by Terry Tao for How many surjections are there from a set of size n? Terry Tao 2010-06-28T20:15:35Z 2010-06-28T20:27:51Z <p>Richard's answer is short, slick, and complete, but I wanted to mention here that there is also a "real variable" approach that is consistent with that answer; it gives weaker bounds at the end, but also tells a bit more about the structure of the "typical" surjection. I'll write the argument in a somewhat informal "physicist" style, but I think it can be made rigorous without significant effort.</p> <p>Tim's function $Sur(n,m) = m! S(n,m)$ obeys the easily verified recurrence $Sur(n,m) = m ( Sur(n-1,m) + Sur(n-1,m-1) )$, which on expansion becomes</p> <p>$Sur(n,m) = \sum m_1 ... m_n = \sum \exp( \sum_{j=1}^n \log m_j )$</p> <p>where the sum is over all paths $1=m_1 \leq m_2 \leq \ldots \leq m_n = m$ in which each $m_{i+1}$ is equal to either $m_i$ or $m_i+1$; one can interpret $m_i$ as being the size of the image of the first $i$ elements of ${1,\ldots,n}$. If we make the ansatz $m_j \approx n f(j/n)$ for some nice function $f: [0,1] \to {\bf R}^+$ with $f(0)=0$ and $0 \leq f'(t) \leq 1$ for all $t$, and use standard entropy calculations (Stirling's formula and Riemann sums, really), we obtain a contribution to $Sur(n,m)$ of the form</p> <p>$\exp( n \int_0^1 \log(n f(t))\ dt + n \int_0^1 h(f'(t))\ dt + o(n) )$ (*)</p> <p>where $h$ is the entropy function $h(\theta) := -\theta \log \theta - (1-\theta) \log (1-\theta)$. So, heuristically at least, the optimal profile comes from maximising the functional</p> <p>$\int_0^1 \log(f(t)) + h(f'(t))\ dt$</p> <p>subject to the boundary condition $f(0)=0$. (The fact that $h$ is concave will make this maximisation problem nice and elliptic, which makes it very likely that these heuristic arguments can be made rigorous.) The Euler-Lagrange equation for this problem is</p> <p>$-\frac{f''}{f'(1-f')} = \frac{1}{f}$</p> <p>while the free boundary at $t=1$ gives us the additional Neumann boundary condition $f'(1)=1/2$. The translation invariance of the Lagrangian gives rise to a conserved quantity; indeed, multiplying the Euler-Lagrange equation by $f'$ and integrating one gets</p> <p>$\log(1-f') = \log f + C$</p> <p>which is easily solved as</p> <p>$f = \frac{1}{A} (1 - B e^{-At} )$</p> <p>for some constants A, B. The Dirichlet boundary condition $f(0)=0$ gives $B=1$; the Neumann boundary condition $f'(1)=1/2$ gives $A=\log 2$, thus</p> <p>$f(t) = (1 - 2^{-t}) / \log 2$.</p> <p>In particular $f(1)=1/(2 \log 2)$, which matches Richard's answer that the maximum occurs when $m/n \approx 1/(2 \log 2)$. To match up with the asymptotic for $Sur(n,m)$ in Richard's answer (up to an error of $\exp(o(n))$, I need to have</p> <p>$\int_0^1 \log f(t) + h(f'(t))\ dt = - 1 - \log \log 2.$</p> <p>And happily, this turns out to be the case (after a mildly tedious computation.)</p> <p>This calculation reveals more about the structure of a "typical" surjection from n elements to m elements for m free, other than that $m/n \approx 1/(2 \log 2)$; it shows that for any $0 &lt; t &lt; 1$, the image of the first $tn$ elements has cardinality about $f(t) n$. If one fixes $m$ rather than lets it be free, then one has a similar description of the surjection but one needs to adjust the A parameter (it has to solve the transcendental equation $(1-e^{-A})/A = m/n$).</p> <p>With a bit more effort, this type of computation should also reveal the typical distribution of the preimages of the surjection, and suggest a random process that generates something that is within o(n) edits of a random surjection. </p> <p>It's also interesting to note that the answer $m/n \approx 1/(2\log 2) = 0.72134\ldots$ fits extremely well with Kevin's numerical computation $f(1000)=722$, so we now have several independent confirmations that this is the correct answer...</p>