Over the weekend, in connection with a research project on semigroups (which I will write about shortly), I needed to know the distribution of the size of the image of a random mapping from the set {1,…,*n*} to itself.

I was at home in St Andrews, without access to the University’s journal and MathSciNet subscriptions. I thought it would be in the 800+ page *Analytic Combinatorics* by Flajolet and Sedgewick; but my copy of the book was in London. However, I had the PDF of the book on my laptop. (I don’t know how they did it, but the authors got Cambridge University Press to agree that the published version of the book could be given away free!)

So I looked in there. First problem: do they call them functions, maps, mappings, transformations, or something else? I searched all likely index entries and found nothing. So I decided to look for the formula which I believed to be correct for the mean of the distribution. But how do you search a PDF file for a mathematical formula? YOu can try; sometimes it will work, at other times it won’t.

So in the end I drew a blank. I’ve been too busy this week to get back to this.

In principle, searching for formulae is a chancy business, since the same formula can use different variables, and present a very different appearance to a search engine. In this case, the mean should be (1-1/e)*n* (the distribution is top-heavy, unlike the binomial coefficients), and e and *n* are fairly standard, so it should be possible.

I think there is a serious problem here, if anyone is thinking about tools to help mathematicians use the internet in their research.

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

Pingback: Tools for mathematicians | Linda Art

It’s really a problem in lambda abstraction, how to capture the form of a formula shorn of the fabula of arbitrary labels. It comes up constantly in writing theorem provers, especially if you try to cache previously proved results in a robust invariant way.

You can find this kind of stuff in Peter Higgins book on techniques of finite semigroups.

To return to your original problem.

The probability that the image has size k is $(n!/(n-k)!) S(n,k)/n^n$

where $S(n,k)$ is a Stirling number of of the second kind. The

mean size of an image is exactly $n(1-(n-1)^n/n^n)$

(n times the probability the image contains $1$).

Similar arguments give exact formulas for the variance etc.

To return to your original problem.

The probability that the image has size k is

where is a Stirling number of of the second kind. The

mean size of an image is exactly

(n times the probability the image contains ).

Similar arguments give exact formulas for the variance etc.

Asymptotic normality?

Good question … if is the size of the image,

then where

is the indicator function for the event that

lies in the image of the function. The

are Bernoulli variables with mean approximately

but are only approximately independent. I would have to

swot up on my probability theory to see if there’s a version

of the central limit theorem liberal enough to apply here,

but it does seem plausible that asymptotic normality holds.