Trees associated with the Motzkin numbers
type: Item
instance of: scholarly article
title: Trees associated with the Motzkin numbers
zbMATH Open document ID: 0860.05003
author: Igor Pak
author: Alexander Postnikov
author: Alexander Kuznetsov
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-11-24T00:00:00Z
review text: \({\mathcal P}_n\) is the set of all plane rooted trees on \(n+1\) unlabeled vertices with edges oriented from the root. \({\mathcal E}_n\) is the set of trees in \({\mathcal P}_n\) with all vertices with an odd distance to the root having at least two outgoing edges. \({\mathcal M}_n\) is the set of trees in \({\mathcal P}_n\) with no vertex having more than two outgoing edges. The Motzkin number \(M_n\) is the size of set \({\mathcal M}_n\). It is shown that \({\mathcal E}_n\) has also size \(M_n\). The number of trees in \({\mathcal E}_n\) with exactly \(k+1\) vertices that have even distance to the root is shown to be \(C_k\).
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 934997
zbMATH Keywords: plane rooted trees
zbMATH Keywords: Motzkin number
zbMATH Keywords: number of trees
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
full work available at URL: jcta.1996.0094
OpenAlex ID: W1972922307
DOI: 10.1006/JCTA.1996.0094
description: scientific article; zbMATH DE number 934997