𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A correspondence between ordered trees and noncrossing partitions

✍ Scribed by Helmut Prodinger

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
54 KB
Volume
46
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The Narayana numbers n appear twice in Volume 31 of Discrete Mathematics: They count the ordere0 trees with n edges (i.e. n+l nodes) and k leaves [1] and the noncrossing partitions of {1 ..... n} into k blocks . (In such a partition the existence of four numbers a<b<c<d such that a and c are in one block and b and d are in another block is forbidden.) The aim of this note is to exhibit a bijection between these combinatorial objects.

πŸ“œ SIMILAR VOLUMES

On trees and noncrossing partitions
On trees and noncrossing partitions
✍ Martin Klazar πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 426 KB

We give a simple and natural proof of (an extension of) the identity P(X. 1. )I ) = t-'2( X I. I -I. II --I ). The number P(li, I, 17) counts noncrossing partitions of { I, 2. I} unto II parts such that no part contains two numbers .Y and J'. O<.v --.v<k. The lower index 2 indicate\ partitions with

Ordered trees and non-crossing partition
Ordered trees and non-crossing partitions
✍ Nachum Dershowitz; Shmuel Zaks πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 229 KB

of non-crossing partitions.

Heap-ordered Trees, 2-Partitions and Con
Heap-ordered Trees, 2-Partitions and Continued Fractions
✍ Wen-Chin Chen; Wen-Chun Ni πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 139 KB

This paper studies the enumerations and some interesting combinatorial properties of heap-ordered trees (HOTs). We first derive analytically the total numbers of \(n\)-node HOTs. We then show that there exists a 1-1 and onto correspondence between any two of the following four sets: the set of \((n+