The quadratic formula conjecture for two non-bonding dominoes

From papers

Let $D(r,c,d)$ denote the number of ways to place $d$ non-bonding dominoes on an $r\times c$ rectangular board. Quadratic formula conjecture. For integers $r,c\ge 3$ ,

D(r,c,2)=2c^2r^2-2(cr^2+c^2r)+\frac{1}{2}(r^2+c^2)-22cr+\frac{59}{2}(c+r)-30.

The formula is obtained by fitting the observed quadratic polynomials and using the symmetry in $r$ and $c$ ; a proof that the relevant bivariate generating function reduces to polynomials remains to be established.

Progress summary

Open

The conjectured counting formula has computational support but no public proof or disproof.

The conjecture asserts an explicit formula for $D(r,c,2)$ when $r,c\ge 3$ , the number of ways to place two non-bonding dominoes on a rectangular board. A $2024$ preprint presents the formula as a conjecture and identifies proving the required polynomial behavior as the remaining task.

Known results

The $2024$ preprint establishes symmetry $D(r,c,d)=D(c,r,d)$ and derives rational bivariate generating functions for boards with at most six rows or columns.
Computed values support the proposed quadratic expression for $D(r,c,2)$ ; the formula was obtained by interpolation and symmetry.
The authors suggest that the transfer-matrix determinant might yield a proof, but provide none.

Current status (as of August 2026): The formula remains an unproved conjecture for $r,c\ge 3$ ; no public counterexample, correction, or independent proof was located.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

Richard J. Mathar, “Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards”, arXiv:2404.18806 (2024).

1 week ago

Complete proof for every r,c >= 3.

Interpret each domino as an edge of the rectangular cell-adjacency grid G = P_r square P_c. A placement of two non-bonding dominoes is exactly an induced matching of size two. More generally, for every finite simple triangle-free graph, the number of such matchings is

I_2(G) = binom(|E|,2) - sum_v binom(deg(v),2) - sum_{uv in E}(deg(u)-1)(deg(v)-1) + 2 C_4(G).

Indeed, the first subtraction removes all overlapping edge pairs. For each possible connecting edge uv, there are (deg(u)-1)(deg(v)-1) choices of two disjoint edges attached at u and v; triangle-freeness ensures they really are disjoint. An incompatible disjoint pair is counted twice exactly when its four vertices form a 4-cycle. Each 4-cycle has two opposite-edge pairs, giving the correction +2 C_4(G).

For the r-by-c grid, |E| = 2rc-r-c and C_4(G) = (r-1)(c-1). The four corners, boundary noncorners and interior vertices respectively have degrees 2,3,4, so

sum_v binom(deg(v),2) = 6rc-6r-6c+4.

Separating horizontal and vertical grid edges gives

sum_horizontal (deg(u)-1)(deg(v)-1) = (r-2)[9(c-3)+12] + 2[4(c-3)+4] = 9rc-10c-15r+14,

sum_vertical (deg(u)-1)(deg(v)-1) = 9rc-10r-15c+14.

Consequently their sum is 18rc-25r-25c+28. Substitution into the general identity yields

D(r,c,2) = binom(2rc-r-c,2)-22rc+29r+29c-30

= 2r^2c^2 - 2(r^2c+rc^2) + (r^2+c^2)/2 - 22rc + 59(r+c)/2 - 30,

exactly Conjecture 1, equation (21), of arXiv:2404.18806, uniformly for every r,c >= 3.

0 endorsements

Shivam Patel · 12 hours ago