Narayana distribution conjecture for path lengths of 231-avoiding permutations

About 16 years old · traced to

Let Sn(231)S_n(231) denote the set of 231231-avoiding permutations of [n][n]. For π∈Sn(231)\pi\in S_n(231), let pathlen⁡(π)\operatorname{pathlen}(\pi) be the length of the path corresponding to π\pi under the construction above, and let N(n,k)N(n,k) be a Narayana number.

Narayana distribution conjecture. The path lengths have the Narayana distribution:

∑π∈Sn(231)qpathlen⁡(π)=q2n∑k≥0N(n,k)q2k.\sum_{\pi \in S_n(231)} q^{\operatorname{pathlen}(\pi)} = q^{2n} \sum_{k \ge 0} N(n,k)q^{2k}.

Moreover,

∑n≥0∑π∈Sn(231)qpathlen⁡(π)=1−q2+q4−1−2q2−q4−2q6+q82q4.\sum_{n \ge 0}\sum_{\pi \in S_n(231)}q^{\operatorname{pathlen}(\pi)} = \frac{1-q^2+q^4-\sqrt{1-2q^2-q^4-2q^6+q^8}}{2q^4}.

The conjecture identifies the length statistic arising from the bijective construction with the Narayana distribution and gives its bivariate generating function. The paper presents this as an observed pattern supported by computations; no proof or resolution is supplied here.

References

Primary source

Dan Drake, “Bijections from weighted Dyck paths to Schroeder paths”, arXiv:1006.1959 (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.