Strong Wilf-equivalence is characterized by trivial equivalence for binary words

About 15 years old · traced to

Let pp and qq be binary words. They are strongly Wilf-equivalent if Bn,p(k)=Bn,q(k)B_{n,p}(k)=B_{n,q}(k) for all n,k≥0n,k\geq 0, and they are trivially equivalent when they are related by the trivial equivalence defined earlier in the paper.

Strong Wilf-equivalence conjecture. Two binary words pp and qq are strongly Wilf-equivalent if and only if they are trivially equivalent.

Strong Wilf-equivalence refines ordinary Wilf-equivalence, since words of the same length are Wilf-equivalent. The paper notes that strong Wilf-equivalence forces pp and qq to have the same length and the same number of runs of each size, while computations suggest that trivial equivalence gives all such equivalences.

References

Primary source

Krishna Menon and Anurag Singh, “Subsequence frequency in binary words”, arXiv:2306.07870 (2023).

Additional references

3 papers in this index state this conjecture (2011–2023). The statement above is taken from the most recent of them; the others are arXiv:1904.02694, arXiv:1102.2480.

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.