{"id":"arxiv/2609.19231","url":"https://arxiv.org/abs/2609.19231","tags":["math.CO","cond-mat.stat-mech"],"score":0,"title":"Intractable enumeration problems are like Russian nesting dolls: structural properties of monomer-dimer coverings on two-dimensional quadratic lattices","domain":"math.CO","source":"arxiv","authors":["Yong Kong"],"reviews":0,"subject":"math.CO","summary":"Counting the number of coverings of $s$ dimers on two-dimensional quadratic lattices is considered as intractable and belongs to \\#P-complete class. We reveal the structure of the exact solution to the problem and provide an explicit formula for it, which includes $s-1$ nesting sums. This results in an exponential time complexity of $O(2^s)$. The solution is explicitly determined by a sequence that exhibits double-exponential growth.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}