16
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
6
  • 1
    $\begingroup$ I think you misunderstood. Here is what Stanley meant by alternating permutations: www-math.mit.edu/~rstan/papers/altperm.pdf $\endgroup$
    – Igor Pak
    Jan 21, 2012 at 6:57
  • $\begingroup$ @I.Pak: I forgot about this other usage. "Even permutations" and "up-down / zigzag permutations" would be unambiguous, but "alternating" can mean either one. @Richard: which did you mean? $\endgroup$ Jan 21, 2012 at 7:04
  • $\begingroup$ @Noam: Even though I can't look into Richard's mind, the fact that Igor linked to a paper on Richard's own website (and by himself) strongly suggest that Igor is right. $\endgroup$ Jan 21, 2012 at 12:01
  • $\begingroup$ Yes, Igor is correct about what I meant by alternating permutations. I would call an element of $A_n$ an even permutation. $\endgroup$ Jan 21, 2012 at 15:48
  • $\begingroup$ OK, I'll edit it out later today (and also add something about enumerating rational functions). Do zigzag permutations satisfy the full $1/(j!e)$ rule (= Poisson distribution with parameter 1)? $\endgroup$ Jan 21, 2012 at 16:07
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.