Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

11
  • 2
    $\begingroup$ I would like to point out that this is (a special case of) exactly the same bijection provided in FindStat's answer. For the casual reader, it is helpful to note that here an initial north step is prepended and a trailing east step appended to the original path, so that NNENEE is $2$-Gorenstein. Moreover, $d_k$ is the usual area sequence (and $c_k$ the column version), instead of adding $1$ to every entry. $\endgroup$ Commented Aug 17, 2017 at 19:31
  • $\begingroup$ Thanks for the suggestions. Yeah, I see that it's the same bijection. Now I see how to extend it to a bijection from all Dyck paths to red-blue Motzkin paths. Simply mark positions of double rises and double falls. Then go from left to right. If you see double rise put U. If double fall put D. Both put red F, none put blue F. I think it's much easier if you skip the 321 permutations altogether. $\endgroup$ Commented Aug 17, 2017 at 20:07
  • $\begingroup$ Well, what you describe is exactly Billey-Jockusch-Stanley and Foata-Zeilberger, except that you describe a special case of the latter and you do not mention the underlying permutation, which makes it clear why they work. The general case of both maps is described by a single picture, or six lines of text for Billey-Jockusch-Stanley and six lines of text for Foata-Zeilberger. $\endgroup$ Commented Aug 17, 2017 at 21:01
  • $\begingroup$ (I should add: Sergi's paper which is cited in FindStats answer is of course a description of the Foata-Zeilberger map, which makes the properties obvious which we need. So proving the three lemmas in FindStats answer is essentially equivalent to your proof.) $\endgroup$ Commented Aug 17, 2017 at 21:19
  • $\begingroup$ What's the general case of Foata-Zeilberger map? $\endgroup$ Commented Aug 17, 2017 at 21:57