5. Call a function f : X - Y doubly surjective if, for each y E Y, there exist at least two distinct elements 21, $2 E X such that f(x1) = y = f(12). Count the number F(m, n) (with m 2 2n and n 2 1) of doubly surjective functions from an m-element set X = {X1, . .., Im) to an n-element set Y = {y1, ...,Un}, in terms of the Stirling numbers of the second kind, as follows. (Recall that the Stirling numbers of the second kind S(a, b) count the number of set partitions of an a-element set into exactly b parts). (a) Explain why the total number of surjective f : X -> Y is exactly n!S(m, n). (b) For i E {1, ..., m}, let F; be the set of surjetive functions f : X - Y such that ; is the only pre-image in X of f(xi) E Y. Show that for any choice of k different indices {21, ..., ix} C {1, ..., m} (with 1 (-1)k m k S(m - k, n - k). k=0