Odd or even on plane trees

Sen Peng Eu*, Shu Chung Liu, Yeong Nan Yeh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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
Issue number1-3
Publication statusPublished - 2004 Apr 28
Externally publishedYes


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this