The generalization of Lagrange's expansion and the enumeration of trees
Published online by Cambridge University Press: 24 October 2008
Extract
In a previous paper ((8)), the joint probability generating function was written down for the sizes of the generations in a tree consisting of c distinct species or colours. It was pointed out in (12) that a generalization of Lagrange's expansion could be applied in order to obtain explicit formulae in some circumstances. The techniques have received new application, to polymer chemistry, in (16), (15), and (17). This application should not be confused with the application of the enumeration of trees to that of isomers ((4), (2), (26)). It was further pointed out in (12) that the technique could be applied to some problems concerning the enumeration of ‘ordered’ (planar) trees. This idea is here developed further, and is applied also to ‘labelled’ trees ‘ordered within colours’. One of our objectives is to specify some circumstances in which iterated generating functions, and consequently also the generalization of Lagrange's expansion, are applicable. The examples show how the techniques can be applied almost automatically in order to deduce results, both old and new. The number of labelled ‘chromatic’ trees with c colours is found: Scoins gave the result for c = 2.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 61 , Issue 2 , April 1965 , pp. 499 - 517
- Copyright
- Copyright © Cambridge Philosophical Society 1965
References
REFERENCES
- 40
- Cited by