填字网格上车摆放的一致稀疏渐近式
Uniform Sparse Asymptotics for Crossword Rook Placements
研究概述
完整车摆放在每行、每列的每个极大连续白格区间中恰好选取一个格子。对于均匀选取 k 个黑格的 n×n 网格,当 k 的增长慢于 n 的平方根时,摆放数量的平均值渐近于 n!(n/36)^k。当 k/sqrt(n) 趋于有限值 lambda 时,归一化平均值趋于 exp(-27 lambda^2/50)。连通分支分析还给出均匀网格与摆放配对的空间分布规律,以及均匀网格的摆放存在性界。
原文摘要(英文)
A complete rook placement on a crossword grid meets every maximal horizontal and vertical white word exactly once. For a uniformly chosen n-by-n grid with k black cells, we prove the proposed mean n!(n/36)^k uniformly when k=o(sqrt(n)), with relative error O(k^2/n). The same estimate extends the classical fixed-defect asymptotic for alternating sign matrices to a growing number of negative entries. When k/sqrt(n) tends to a finite nonnegative value lambda, both normalized counts converge to exp(-27 lambda^2/50). The proof uses uniform connected-component bounds for a marked row-column graph and controls the contribution of boundary and adjacent black cells. At this critical scale, the number of connected size-five components with two negative entries has a Poisson limit of mean 99 lambda^2/25. In the smaller sparse regime, almost all uniformly chosen grid-placement pairs consist of disjoint elementary crosses and a permutation remainder; their black coordinates have an explicit median law with independent beta(2,2) limits for fixed k. Uniform sparse grids admit a complete placement with high probability, while at fixed positive black and white densities the existence probability decays exponentially in the area.
数学审核
稿件已完成内部审核,当前公开版本尚未完成完整形式化。
审核标准