𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Enumeration of trees by inversions

✍ Scribed by Ira M. Gessel; Bruce E. Sagan; Yeong-Nan Yeh

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
749 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 define inversion polynomials for ordered, plane, and cyclic trees, and find their values at q = 0, Β± 1. Our techniques involve the use of generating functions (including Lagrange inversion), hypergeometric series, and binomial coefficient identities, induction, and bijections. We also derive asymptotic formulae for those results for which we do not have a closed form. Β© 1995 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

Computer enumeration and generation of p
Computer enumeration and generation of physical trees
✍ J. V. Knop; W. R. MΓΌller; K. Szymanski; H. W. Kroto; N. TrinajstiΔ‡ πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 336 KB

A computer-oriented method for the enumeration and generation of physical trees is presented. Physical trees depict acyclic chemical structures, but the term physical is used to stress the process by which the structures are produced.

Enumeration of Labelled (k, m)-Tree
Enumeration of Labelled (k, m)-Trees
✍ Oleg Pikhurko πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 78 KB

A k-graph is called a (k, m)-tree if it can be obtained from a single edge by consecutively adding edges so that every new edge contains k&m new vertices while its remaining m vertices are covered by an already existing edge. We prove that there are (e(k&m)+m)!(e( k m )&e+1) e&2 e!m!((k&m)!) e disti

The enumeration of trees with and withou
The enumeration of trees with and without given limbs
✍ Taojun Lu πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 720 KB

A limb of a tree is the union of one or more branches at a vertex in the tree, where a branch of a tree at a vertex is a maximal subtree containing the given vertex as an end-vertex. In this note, we first consider the enumeration of trees (undirected, oriented or mixed) with forbidden limbs. The en