The Component Counts of Random Injections

  • Dudley Stark


A model of random injections is defined which has domain $A\cup B$ and codomain $A\cup C$, where $A$, $B$ and $C$ are mutually disjoint finite sets such that $|B|\leqslant |C|$. The model encompasses both random permutations, which is the case $B=C=\varnothing$, and random maximum matchings of a complete bipartite graph, which is the case $A=\varnothing$. The possible components of random injections are cycles and paths. Results on the counts of cycles and paths of different sizes are obtained for this model.

Article Number