Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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

share|improve this answer
1  
I think you misunderstood. Here is what Stanley meant by alternating permutations: www-math.mit.edu/~rstan/papers/altperm.pdf –  Igor Pak Jan 21 '12 at 6:57
    
@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? –  Noam D. Elkies Jan 21 '12 at 7:04
    
@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. –  Marc van Leeuwen Jan 21 '12 at 12:01
    
Yes, Igor is correct about what I meant by alternating permutations. I would call an element of $A_n$ an even permutation. –  Richard Stanley Jan 21 '12 at 15:48
    
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)? –  Noam D. Elkies Jan 21 '12 at 16:07
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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