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.
Asymptotic number of certain functions without fixed points
Richard Stanley
- 50.8k
- 14
- 155
- 279