Odd or even on plane trees

Sen Peng Eu, Shu Chung Liu, Yeong Nan Yeh

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

Over all plane trees with n edges, the total number of vertices with odd degree is twice the number of those with odd outdegree. Deutsch and Shapiro posed the problem of finding a direct two-to-one correspondence for this property. In this article, we give three different proofs via generating functions, an inductive proof and a two-to-one correspondence. Besides, we introduce two new sequences which enumerate plane trees according to the parity of the number of leaves. The explicit formulae for these sequences are given. As an application, the relation provides a simple proof for a problem concerning colored nets in Stanley's Catalan Addendum.

Original languageEnglish
Pages (from-to)189-196
Number of pages8
JournalDiscrete Mathematics
Volume281
Issue number1-3
DOIs
Publication statusPublished - 2004 Apr 28

Keywords

  • Catalan numbers
  • Odd and even nets
  • Outdegree
  • Plane trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Odd or even on plane trees'. Together they form a unique fingerprint.

  • Cite this