The average size of ordered binary subgraphs t

To analyse the demands made on the garbage collector in a graph reduction system, the change in size of an average graph is studied when an arbitrary edge is removed. In ordered binary trees the average number of deleted nodes as a result of cutting a single edge is equal to the average size of a subtree. Under the assumption that all trees with n nodes are equally likely to occur, the expected size of a subtree is found to be approximately ~'~n-n. The enumeration procedure can be applied to graphs by considering spanning trees in which the nodes that were shared in the graph are marked in the spanning tree. A correction to the calculation of the average is applied by ignoring subgraphs that have a marked root. Under the same assumption as above the average size of a subgraph is approximately- 2 (m + 1), where m represents the number of shared nodes and m <<n. Key words: binary graphs Catalan statistics combinator graph reduction subgraphs 1. I n t roduct ion The L-calculus 1 can be viewed as a universal programming language. Its simplicity makes ~,-expressions (programmes) amenable to direct mechanical evaluation. 2 Funct ional programmin