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

At least 17 years old · documented by

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

Av⁡s(x)=Av⁡t(x),\operatorname{Av}_s(x)=\operatorname{Av}_t(x),

and they are enumerating-equivalent if

En⁡L,s(x,y)=En⁡L,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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.