By a Narayana-enumerated object I mean an object whose count is given by the Narayana number $N(n,k)=\frac{1}{n} {n \choose k} {n \choose k-1}$. Can you give me a reference to some good big list of Narayana-enumerated objects? I have found two Narayana-enumerated objects (the two objects being closely related one to another) and would like to see whether my two objects are in the list.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Some examples are given in Wokipedia: en.wikipedia.org/wiki/… $\endgroup$– Max AlekseyevCommented May 7, 2022 at 11:44
-
$\begingroup$ Narayana's original interpretation (see jstor.org/stable/25048410) was: pairs $\alpha,\beta$ of compositions of $n$ into $k$ parts, with $\alpha \leq \beta$ in dominance order. There is a straightforward way to transform these into Dyck paths with $k$ peaks, but thought it was worth mentioning that. $\endgroup$– Sam HopkinsCommented May 7, 2022 at 13:30
-
$\begingroup$ Max Alekseyev and Sam Hopkins, thank you for additional information. In the meantime, I downloaded "Joint distributions of three descriptive parameters of bridges", a 1985 conference paper by Germain Kreweras. In that paper, the author says: "More recently it was discovered that two other descriptive parameters, the consideration of which may appear as slightly less natural, also follow the same Narayana distribution." The first of the just-mentioned two parameters are ascents in even positions, but Kreweras is not quite explicit as to who made that then-recent discovery. $\endgroup$– Svjetlan FereticCommented May 7, 2022 at 14:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Elements of the sets enumerated by super-Catalan numbers contains many Narayana-enumerated objects. (The super-Catalan number $s_n$ is related to the Narayana numbers by $s_n=\sum_{k=1}^n 2^{k-1}N_{n,k}$.)
Some examples:
The following five parameters of Dyck paths are enumerated by Narayana numbers:
(i) number of high peaks;
(ii)number of valleys;
(iii)number of doublerises;
(iv) number of rises at an even level;
(v) number of nonfinal ascents and descents of length greater than 1.
132-avoiding permutations with given number excedances ($a_i > i$) are counted by Narayana numbers, as well as those with given number descents ($a_i<i$).
answered May 7, 2022 at 10:06
-
$\begingroup$ Thank you for the quick and detailed answer. In fact, my two Narayana-enumerated objects are: 1) Dyck paths with $2n$ steps and $k$ rises at even level, and 2) Dyck paths with $2n$ steps and $k-1$ rises at odd level. Now it remains to find a proper reference for those two objects. (In fact, I could also write that those two objects are classical.) In "Elements of the sets enumerated by super-Catalan numbers", the authors cite a 1999 paper by Bob Sulanke [32], who (in [32]) already says that my object 2) is one of the better-known Narayana-enumerated objects. $\endgroup$ Commented May 7, 2022 at 11:53