论文标题
计数混乱的比赛
Counting Deranged Matchings
论文作者
论文摘要
令$ \ mathrm {pm}（g）$表示图形$ g $的完美匹配数，然后$ k_ {r \ times 2n/r} $表示完整的$ r $ - 明确图，每个零件的大小$ 2N/r $。约翰逊（Johnson），凯尔（Kayll）和帕尔默（Palmer）指出，对于任何完美匹配的$ m $ $ k_ {r \ times times 2n/r} $，我们有$ 2N $的$ 2N $可将$ r $ \ \ [\ frac {\ frac {\ mathrm {pm {pm}（k_ {r \ times times 2n/r} -m} -m} -m） 2n/r}）}} \ sim e^{ - r/（2r-2）}。\ \ \ \ \]可以将其视为计算$ n $字母上的扰动数量的常见概括，并计算$ k_ {2n} $的distanded匹配次数。我们证明了这个猜想。实际上，我们证明，如果$ r $是$ k_ {r \ times 2n/r} $的均匀随机完美匹配，那么$ r $的边数与$ m $ commisting to poisson分配具有参数$ \ frac $ \ frac {r} {r} {2r-2} $。
Let $\mathrm{pm}(G)$ denote the number of perfect matchings of a graph $G$, and let $K_{r\times 2n/r}$ denote the complete $r$-partite graph where each part has size $2n/r$. Johnson, Kayll, and Palmer conjectured that for any perfect matching $M$ of $K_{r\times 2n/r}$, we have for $2n$ divisible by $r$ \[\frac{\mathrm{pm}(K_{r\times 2n/r}-M)}{\mathrm{pm}(K_{r\times 2n/r})}\sim e^{-r/(2r-2)}.\] This conjecture can be viewed as a common generalization of counting the number of derangements on $n$ letters, and of counting the number of deranged matchings of $K_{2n}$. We prove this conjecture. In fact, we prove the stronger result that if $R$ is a uniformly random perfect matching of $K_{r\times 2n/r}$, then the number of edges that $R$ has in common with $M$ converges to a Poisson distribution with parameter $\frac{r}{2r-2}$.
