## Tools for mathematicians

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. ## About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics and tagged , . Bookmark the permalink.

### 7 Responses to Tools for mathematicians

1. Pingback: Tools for mathematicians | Linda Art

2. Jon Awbrey says:

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.

3. Benjamin Steinberg says:

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

4. Robin Chapman says:

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.

5. Robin Chapman says:

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.

• Peter Cameron says:

Asymptotic normality?

• Robin Chapman says:

Good question … if $X_n$ is the size of the image,
then $X_n = Y_{1,n} + \cdots + Y_{n,n}$ where $Y_{j,n}$ is the indicator function for the event that $j$ lies in the image of the function. The $Y_{j,n}$
are Bernoulli variables with mean approximately $1-e^{-1}$
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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.