Associated Hermite matching-generating-function conjecture

About 19 years old · traced to 2007

Let $n_1,n_2,\dots,n_k$ be positive integers. For each $i$ , let $[n_i]=\{1,2,\dots,n_i\}$ , and arrange the sets in the disjoint union below in weakly increasing order by size. Let $H_{n_i}(x;c)$ be the associated Hermite polynomials and let $\L_c$ denote the corresponding integral functional. A matching is inhomogeneous when it contains the inhomogeneous edges specified by the model, and the rightmost-choice moment weighting assigns weight $c$ to every edge with no right crossing.

Associated Hermite matching-generating-function conjecture. The integral

\L_c \left( \prod_{i=1}^k H_{n_i}(x;c) \right)

is the generating function for inhomogeneous matchings on $\bigsqcup_{i=1}^k [n_i]$ , with the vertex sets arranged in weakly increasing order by size and the edges weighted using the rightmost-choice moment weighting.

The conjecture is motivated by computational evidence after the other orderings and moment or polynomial weightings fail in small examples. The supplied material does not establish a proof or a disproof, so its resolution remains open.

References

Primary source

Dan Drake, “The combinatorics of associated Hermite polynomials”, arXiv:0709.0987 (2008).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written computation claims a ten-vertex counterexample disproves the conjecture, but nobody has independently verified it.

Dan Drake formulated the conjecture in 2007: the associated-Hermite integral $\mathcal{L}_c\!\left(\prod_i H_{n_i}(x;c)\right)$ should count the specified inhomogeneous matchings under the weakly increasing block ordering. The paper reports computational motivation but neither proves nor disproves the claim.

Known results

Drake (2007) gives matching, complete-matching, oscillating-tableau, and rooted-map interpretations for moments of associated Hermite polynomials.
Drake (2007) proves orthogonality, including $\mathcal{L}_c(H_nH_m)=0$ for $n\ne m$ and $\mathcal{L}_c(H_n^2)=(c+1)^n$ .
Drake (2007) derives linearization formulas for products of two associated Hermite polynomials, but not the multi-factor conjecture.

Posted counterexample

A reader-written calculation claims that $(n_1,\ldots,n_6)=(1,1,1,1,3,3)$ gives $\mathcal{L}_c(H_1^4H_3^2)-F_1(\varnothing)=3c(c-1)(c+1)(c+2)$ , hence disagreement at $c=2$ . It claims a complete disproof, but the computation has not been independently verified.

Current status (as of August 2026): The conjecture is supported by Drake's original computational evidence, while a claimed ten-vertex counterexample would settle it negatively but remains unverified.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

The conjecture is false. Take six blocks of weakly increasing sizes

(n_1,n_2,n_3,n_4,n_5,n_6)=(1,1,1,1,3,3).

The associated-Hermite recurrence

H_{r+1}(x;c)=xH_r(x;c)-(r-1+c)H_{r-1}(x;c)

gives $H_1=x$ and $H_3=x^3-(2c+1)x$ . Let $\mu_j=\mathcal L_c(x^j)$ . The Dyck-path moment rule gives

\begin{aligned} \mu_6&=3c+7c^2+5c^3,\\ \mu_8&=15c+39c^2+37c^3+14c^4,\\ \mu_{10}&=105c+296c^2+326c^3+176c^4+42c^5. \end{aligned}

These follow directly from $D_{0,0}=1$ and the transitions

D_{t+1,h+1}\mathrel{+}=D_{t,h},\qquad D_{t+1,h-1}\mathrel{+}=(h-1+c)D_{t,h}\quad(h>0),

with $\mu_t=D_{t,0}$ . Therefore

\begin{aligned} \mathcal L_c(H_1^4H_3^2) &=\mu_{10}-2(2c+1)\mu_8+(2c+1)^2\mu_6\\ &=78c+177c^2+141c^3+48c^4+6c^5. \end{aligned}

For an independently checkable enumeration of the proposed matching side, write the ordered block-label word as

b=(1,2,3,4,5,5,5,6,6,6).

Process vertices from left to right and let $L=(\ell_1,\ldots,\ell_h)$ be the ordered list of block labels of currently open edges. If $F_p(L)$ is the weighted generating function for completions starting at vertex $p$ , then

F_p(L)=F_{p+1}(L,b_p) +\sum_{\substack{1\le j\le h\\ell_j\ne b_p}} c^{[j=h]}F_{p+1}(\ell_1,\ldots,\widehat{\ell_j},\ldots,\ell_h),

with $F_{11}(\varnothing)=1$ and $F_{11}(L)=0$ for $L\ne\varnothing$ . The restriction $\ell_j\ne b_p$ enforces inhomogeneity. An edge has no right crossing exactly when its opening vertex is the most recently opened edge still present at its closing vertex, giving the factor $c^{[j=h]}$ .

The recurrence yields

F_1(\varnothing)=84c+180c^2+135c^3+45c^4+6c^5.

Thus the 450 admissible matchings split into $84,180,135,45,6$ according to their number of edges without a right crossing. Consequently,

\mathcal L_c(H_1^4H_3^2)-F_1(\varnothing) =3c(c-1)(c+1)(c+2).

For the admissible value $c=2$ , the two sides are respectively $2952$ and $2880$ . Therefore the conjectured identity fails already on ten vertices.