Counting formulas for tree growth plans

We present counting formulas for the number of different ways to grow a given rooted tree, over a specified number of intervals. We call these growth plans, or simply plans. This problem arises, for example, in analog toll-connect networks in which it is desired to introduce digital technology to serve increasing circuit requirements, in the cheapest way. Each circuit in such a network extends from a particular node called the toll center to one of the other nodes. The toll center corresponds to the root, and the portion of the network containing digital equipment corresponds to the rooted subtree whose growth we study. Even for networks of modest size and few growth intervals, the number of plans is too large to permit finding the cheapest by an exhaustive search. We observe that plans differing only in their growth pattern in the neighborhood of some particular node have cost differences that depend principally on their local growth patterns. It is therefore often possible to eliminate at a single stroke a large class of plans having a specified local growth plan at a particular node. By repetition, the number of remaining plans that must have their individual total costs computed can often be reduced to a number sufficiently small for an exhaustive search. We describe two types of local growth behavior appropriate for eliminating classes of plans in this network problem, and give corresponding counting formulas for the number of tree growth plans under these restrictions. A generalized counting formula with arbitrary local restrictions at each node is presented; this general formula contains the prior results as special cases. Finally, an example illustrates the great reduction in number of plans that can sometimes be obtained.