Counting fixed-point-free Cayley permutations

Abstract

Two-sort species yield differential equations for functional digraphs of Cayley permutations. From these we obtain an explicit formula for fixed-point-free Cayley permutations and prove that their proportion tends to $1/e$, as for permutations and endofunctions. Our approach also yields counting formulas when the functional digraph is a tree, forest, or connected.

31 pages, 6 figures, 4 tables