COUNTING BINARY, ROOTED TREES ARBOREAL NUMBERS OF THE FIRST AND SECOND KIND. II. A RECURSIVE FORMULA FOR COUNTING N-ARY ROOTED TREES,
Abstract
The report is in two parts. The first part, that considers counting binary rooted trees, examined the question of how many distinct functions of n inputs can be realized by varying the connection pattern in a network of two-input elements. In assuming free interconnectability of elements, it is implied that all input and output signals in the network lie in the same domain. Accordingly, all functions computed by network elements can be treated as equivalent to binary operations in this domain, and vice versa. The numbers of functionally distinct binary rooted trees, computed vs. the number of terminals, for each of three function classes, and the arboreal numbers of the second kind for n up to 40 are tabulated. In the second part, a recursive formula is derived for counting n-ary rooted trees. Formulas are given for counting the number of unlabeled rooted trees of k vertices, the number of unlabeled binary trees of k vertices, the number of unlabeled n-ary rooted trees as a function of the number of terminal vertices rather than the total number of vertices, and the number of unlabeled binary trees of t terminal vertices.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 31, 1966
- Accession Number
- AD0696672
Entities
People
- Hollis F. Ryan
- Paul Weston
Organizations
- University of Illinois Urbana–Champaign