Asymptotic number of certain functions without fixed points

Question

Terry Tao's question Non-enumerative proof that there are many derangements? suggests the following. What classes $C_n$ of functions $f\colon \lbrace 1,2,\dots,n\rbrace \to \lbrace 1,2,\dots,n\rbrace$ have the property that if $a(n)$ is the number of functions in $C_n$ and $b(n)$ is the number without fixed points, then $\lim_{n\to\infty} a(n)/b(n) = e$? Examples include all functions, permutations, and alternating permutations. (I don't know a simple proof for alternating permutations.) Rather than lots of examples, a general theorem that includes all (or most) of these examples would be more interesting.

Answer 1

For $j=0,1,2,\ldots$ let $b_n(j)$ be the number of functions in $C_n$ with exactly $j$ fixed points. At least in some cases when $b_n(0) / a_n \rightarrow 1/e$ (including permutations, functions, and also even permutations and two further examples given below), we have the more general result for each $j$ that $b_n(j) / a_n \rightarrow 1/(j!e)$. That is, if we construct a random variable $j$ by choosing $f \in C_n$ uniformly at random and counting its fixed points, then the distribution of $j$ approaches the Poisson distribution with parameter $1$.

For this distribution, not only does $j$ have expected value $1$, but more generally for each $i$ the expected number of $i$-tuples of distinct fixed points approaches $$ \sum_{j=i}^\infty \frac{j!}{(j-i)!} \frac1{j!e} = \frac1e \sum_{j=i}^\infty \frac1{(j-i)!} = 1. $$ Since the Poisson distribution is determined by its moments [what's a standard reference for this?], it follows that conversely

Suppose for each $n$ in a sequence with $n \rightarrow \infty$ we have a set $C_n$ of functions $f : \lbrace 1,2,\ldots,n \rbrace \rightarrow \lbrace 1,2,\ldots,n \rbrace$. If for each $i$ the average number over $f \in C_n$ of $i$-tuples of distinct points of $f$ approaches $1$ as $n \rightarrow \infty$ then $b_n(j) / a_n \rightarrow 1/(j!e)$ for each $j$.

The hypothesis is reasonably natural in contexts where we expect that the $i$-tuples $\bigl(f(x_1),f(x_2),\ldots f(x_i)\bigr)$ are nearly equidistributed for most $i$-tuples $(x_1,x_2,\ldots,x_i)$ of distinct elements of $\lbrace 1,2,\ldots,n \rbrace$.

This equidistribution holds exactly for all $i \leq n$ if $C_n$ is the set of all functions; if $C_n$ is the permutations then we have exact equidistribution among $i$-tuples of distinct elements of $\lbrace 1,2,\ldots,n \rbrace$, which is sufficient as $n \rightarrow \infty$; likewise for even permutations once $n \geq i+2$, which can be assumed since in each case we fix $i$ and let $n \rightarrow \infty$.

A further example: let $n$ be a prime power $q$, identify $\lbrace 1,2,\ldots,n \rbrace$ with a finite field $F$, and let $C_n$ consist of the $n^d$ polynomials of degree less than $d$. Then equidistribution holds exactly for each $i \leq d$. Once $d>1$, the distribution of $j$ is the same as the distribution of the number of roots of a random polynomial of degree $<d$ (namely $f(X)-X$). It is well known that there is a close link between the distribution of cycle structures of random permutations, and of degrees of irreducible factors of a random polynomial over a finite field (e.g. this is a manifestation of the Čebotarev density theorem); fixed points are 1-cycles, which correspond to linear factors, i.e. roots in $F$.

To conclude, a similar but more exotic example: if $n=q+1$ we can identify $\lbrace 1,2,\ldots,n \rbrace$ with the finite projective line $F \cup \lbrace \infty \rbrace$, fix $d < n/2$, and let $C_n$ be the set of rational functions of given degree $d>1$. Here $a_n = q^{2d+1} - q^{2d-1}$. (See the bottom of page 8 of my STOC'01 paper for a bijective proof that there are exactly $q^{2d+1}$ rational functions of degree at most $d$.) The number of fixed points is at most $d+1$, and for each $i \leq d+1$ the expected number of fixed $i$-tuples behaves correctly. So this example works as long as $d \rightarrow\infty$.

Answer 2

Here is a generalization of the derangements case.

Take a Latin rectangle with $n$ columns and $k\le n^{1-\epsilon}$ rows, such that, for each $i$, the value $i$ does not appear in the $i$-th column. Now consider the set of all permutations that extend this rectangle to $k+1$ rows; i.e., the permutations which are derangements of each of the given $k$ rows. Then this set of permutations has the fraction $e^{-1}(1+o(1))$ of derangements in it.

This follows from Theorem 6.2 of my paper on Latin rectangles with Chris Godsil.