The equivalence of avoiding and enumerating generating functions for binary tree patterns

From papers

Let ss and tt be binary tree patterns. They are avoiding-equivalent if their avoiding generating functions satisfy

Avs(x)=Avt(x),\operatorname{Av}_s(x)=\operatorname{Av}_t(x),

and they are enumerating-equivalent if

EnL,s(x,y)=EnL,t(x,y).\operatorname{En}_{L,s}(x,y)=\operatorname{En}_{L,t}(x,y).

Avoiding-enumerating equivalence conjecture. If ss and tt are avoiding-equivalent, then they are also enumerating-equivalent.

This conjecture asserts that equality of the numbers of binary trees avoiding two patterns forces equality of the refined generating functions recording the number of pattern copies. The paper reports computational evidence for binary tree patterns with at most 77 leaves, but does not establish the assertion in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Eric S. Rowland, “Pattern avoidance in binary trees”, arXiv:0809.0488 (2010).

Solutions 0

No solutions have been posted yet.