The quadratic formula conjecture for two non-bonding dominoes

At least 1 year old · documented by 2024

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The formula has computational support, and a complete proof has now been proposed, but that proof has not been independently checked.

Richard J. Mathar’s 2024 preprint conjectures the displayed formula for $D(r,c,2)$ when $r,c\ge 3$ , based on transfer-matrix data, interpolation, and symmetry. It explicitly leaves the required polynomiality proof open.

Known results

Mathar, 2024: rational generating functions are derived for boards with at most six rows or columns.
Mathar, 2024: computed data support the formula, but no proof of its validity for all $r,c\ge 3$ is given.

Posted attempt

A complete proof is claimed by identifying placements with induced matchings in the cell-adjacency grid and applying a counting identity for triangle-free graphs. The claim has not been independently verified, and therefore does not establish the conjecture.

Current status (as of August 2026): The conjecture has computational support but no independently verified proof; a complete-proof claim is recorded and remains unconfirmed.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

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.