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

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,k0n,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.

Sources & referencesView supporting material

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.