Enumerating alternating trees

Authors
Chauve, C Dulucq, S Rechnitzer, A
Citation
C. Chauve et al., Enumerating alternating trees, J COMB TH A, 94(1), 2001, pp. 142-151
Citations number
6
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165 → ACNP
Volume
94
Issue
1
Year of publication
2001
Pages
142 - 151
Database
ISI
SICI code
0097-3165(200104)94:1<142:EAT>2.0.ZU;2-Z
Abstract
In this paper we examine the enumeration of alternating trees. We give a bi jective proof of the fact that the number of alternating unrooted trees wit h n vertices is given by (1/n2(n-1)) Sigma (n)(k=1) ((n)(k))k(n-1), a probl em first posed by A. Postnikov (1997. J. Combin. Theory Ser. A 79, 360-366) . We also show that the number of alternating ordered trees with n vertices is 2(n - 1)(n-1). (C) 2001 Academic Press.