Accession Number : AD0696672

Title :   COUNTING BINARY, ROOTED TREES ARBOREAL NUMBERS OF THE FIRST AND SECOND KIND. II. A RECURSIVE FORMULA FOR COUNTING N-ARY ROOTED TREES,

Corporate Author : ILLINOIS UNIV URBANA BIOLOGICAL COMPUTER LAB

Personal Author(s) : Weston,Paul ; Ryan,Hollis F.

Report Date : 31 OCT 1966

Pagination or Media Count : 58

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.

Descriptors :   (*TOPOLOGY, RECURSIVE FUNCTIONS), NUMBER THEORY, COMBINATORIAL ANALYSIS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE