Complete non-ambiguous trees and associated permutations: new enumerative results
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912771465019392 |
|---|---|
| author | Selig, Thomas Zhu, Haoyue |
| author_facet | Selig, Thomas Zhu, Haoyue |
| contents | We study a link between complete non-ambiguous trees (CNATs) and permutations exhibited by Daniel Chen and Sebastian Ohlig in recent work. In this, they associate a certain permutation to the leaves of a CNAT, and show that the number of $n$-permutations that are associated with exactly one CNAT is $2^{n-2}$. We connect this to work by the first author and co-authors linking complete non-ambiguous trees and the acyclic orientation number of the associated permutation graph. This allows us to prove a number of conjectures by Chen and Ohlig on the number of $n$-permutations that are associated with exactly $k$ CNATs for various $k > 1$, via various bijective correspondences between such permutations. We also exhibit a new bijection between $(n-1)$-permutations and CNATs whose permutation is the decreasing permutation $n(n-1)\cdots1$. This bijection maps the left-to-right minima of the permutation to dots on the top row of the corresponding CNAT, and descents of the permutation to empty rows of the CNAT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_15756 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complete non-ambiguous trees and associated permutations: new enumerative results Selig, Thomas Zhu, Haoyue Combinatorics 05A19 (Primary), 05A05, 05A15, 05C30 (Secondary) We study a link between complete non-ambiguous trees (CNATs) and permutations exhibited by Daniel Chen and Sebastian Ohlig in recent work. In this, they associate a certain permutation to the leaves of a CNAT, and show that the number of $n$-permutations that are associated with exactly one CNAT is $2^{n-2}$. We connect this to work by the first author and co-authors linking complete non-ambiguous trees and the acyclic orientation number of the associated permutation graph. This allows us to prove a number of conjectures by Chen and Ohlig on the number of $n$-permutations that are associated with exactly $k$ CNATs for various $k > 1$, via various bijective correspondences between such permutations. We also exhibit a new bijection between $(n-1)$-permutations and CNATs whose permutation is the decreasing permutation $n(n-1)\cdots1$. This bijection maps the left-to-right minima of the permutation to dots on the top row of the corresponding CNAT, and descents of the permutation to empty rows of the CNAT. |
| title | Complete non-ambiguous trees and associated permutations: new enumerative results |
| topic | Combinatorics 05A19 (Primary), 05A05, 05A15, 05C30 (Secondary) |
| url | https://arxiv.org/abs/2303.15756 |