✦ LIBER ✦

Enumerating Alternating Trees

✍ Scribed by Cedric Chauve; Serge Dulucq; Andrew Rechnitzer

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 164 KB
Volume: 94
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.2000.3121

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we examine the enumeration of alternating trees. We give a bijective proof of the fact that the number of alternating unrooted trees with n vertices is given by (1Ân2 n&1 ) n k=1 ( n k ) k n&1 , a problem 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 .

📜 SIMILAR VOLUMES

Enumerating k-trees

✍ Dominique Foata 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 256 KB

AMUacL k functtonal dicf~mition of rooted k-trees is given, enabling k-trees with n labeled points m be enumerated without any calculation.

Enumerating phylogenetic trees with mult

Enumerating phylogenetic trees with multiple labels

✍ L.R. Foulds; R.W. Robinson 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 524 KB

## Evolutionary trees are used in biology to illustrate postulated ancestral relationships between species and are often called phylogenetic trees. They can be characterized in graph theoretic terms by certain classes of labelled trees. Disjoint subsets of the labelling set are assigned to tree ve

On enumerating the trees of a ladder net

On enumerating the trees of a ladder network

✍ D. E. Johnson; J. R. Johnson 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 307 KB

Enumeration of alternating sequences

✍ J.C. Parnami; K.C. Prasad 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 143 KB

Enumeration of trees by inversions

✍ Ira M. Gessel; Bruce E. Sagan; Yeong-Nan Yeh 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 749 KB

## Abstract Mallows and Riordan “The Inversion Enumerator for Labeled Trees,” __Bulletin of the American Mathematics Society__, vol. 74 [1968] pp. 92‐94) first defined the inversion polynomial, __J~n~(q)__ for trees with __n__ vertices and found its generating function. In the present work, we defi

Generalized m series in tree enumeration

✍ P.V. O'Neil 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 241 KB

## Introduction Let Kt denote the complete graph with t vertices. In (l), Bedrosian defined four classes of graphs, the p, s, r and m series, each formed by deleting certain branches of Kt. Formulas for the r and p series were first obtained by Weinberg (2) and are special cases of a formula due t