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

Fingerprint

Odd
Correspondence
Parity
Generating Function
Explicit Formula
Proof by induction
Leaves

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this

Odd or even on plane trees. / Eu, Sen Peng; Liu, Shu Chung; Yeh, Yeong Nan.

In: Discrete Mathematics, Vol. 281, No. 1-3, 28.04.2004, p. 189-196.

Research output: Contribution to journalArticle

Eu, SP, Liu, SC & Yeh, YN 2004, 'Odd or even on plane trees', Discrete Mathematics, vol. 281, no. 1-3, pp. 189-196. https://doi.org/10.1016/j.disc.2003.07.011
Eu, Sen Peng ; Liu, Shu Chung ; Yeh, Yeong Nan. / Odd or even on plane trees. In: Discrete Mathematics. 2004 ; Vol. 281, No. 1-3. pp. 189-196.
@article{7ba2fde9097d4a53a06b8fa7572d3057,
title = "Odd or even on plane trees",
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.",
keywords = "Catalan numbers, Odd and even nets, Outdegree, Plane trees",
author = "Eu, {Sen Peng} and Liu, {Shu Chung} and Yeh, {Yeong Nan}",
year = "2004",
month = "4",
day = "28",
doi = "10.1016/j.disc.2003.07.011",
language = "English",
volume = "281",
pages = "189--196",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "1-3",

}

TY - JOUR

T1 - Odd or even on plane trees

AU - Eu, Sen Peng

AU - Liu, Shu Chung

AU - Yeh, Yeong Nan

PY - 2004/4/28

Y1 - 2004/4/28

N2 - 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.

AB - 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.

KW - Catalan numbers

KW - Odd and even nets

KW - Outdegree

KW - Plane trees

UR - http://www.scopus.com/inward/record.url?scp=1842615983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1842615983&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2003.07.011

DO - 10.1016/j.disc.2003.07.011

M3 - Article

AN - SCOPUS:1842615983

VL - 281

SP - 189

EP - 196

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -