Abstract
This paper presents some preliminary observations relating in many cases structural definitions of combinatorial structures to statistical properties of their characteristic parameters.
The developments are based on two observations: (i) for a large family of classes of combinatorial structures, one can compile structural descriptions into functional equations over counting generating functions; (ii) general analytical patterns arise from the study of these functional equations.
As a consequence, statistical evaluations of a large number of parameters of combinatorial structures can be automated using symbolic manipulation systems.
The approach taken also suggests the existence of general theorems concerning statistical properties of combinatorial structures that may be used to analyse combinatorial structures of a complex form.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
N. G. DE Bruijn: Asymptotic Methods in Analysis, North Holland P.C. (1957); reprinted by Dover (1981).
S. Eilenberg: Automata, Languages and machines, Academic Press, New-York (1974).
P. Flajolet: Mathematical Analysis of Algorithms and Data Structures, in A Graduate Course in Computation Theory, Computer Science Press, (1985, to appear).
P. Flajolet: Ambiguity and Transcendence, in Proc. I.C.A.L.P., Nafplion (July 1985). To appear in Lecture Notes in Comp. Science.
P. Flajolet and A. Odlyzko: The Average Height of Binary Trees and Other Simple Trees, J. of Computer and System Sc. 25 (1983), pp. 345–369.
P. Flajolet and J-M. Steyaert: A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures, in Proc., 22nd IEEE Sump. on Found. of Comp. Theory (FOCS), Nashville (1982), pp. 386–393.
G. Gonnet: Expected Length of the Longest Probe Sequence in Hashing, J.A.C.M. 28 (1981), pp. 289–304.
I. Goulden and D. Jackson: Combinatorial Enumerations, J. Wiley (1983).
P. Henrici: Applied Computational and Complex Analysis, J. Wiley, New-York (1977).
A. Meir and J. W. Moon: On the Altitude of Nodes in Random Trees, Canad. J. of Math. 30 (1978), pp. 997–1015.
A. Odlyzko: Periodic Oscillations of Coefficients of Power Series That Satisfy Functional Equations, Adv. in Math 44 (1982), pp. 180–205.
J-M. Steyaert and P. Flajolet: Patterns and Pattern-Matching in Trees: An Analysis, Inf. and Control 58 (1983), pp. 19–58.
A. Salomaa and M. Soittola: Automata-Theoretic Aspects of Formal Power Series, Springer Verlag (1978).
J-M. Steyaert: Complexite et Structure des Algorithmes, Thesis, University of Paris VII (1984), 215p.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flajolet, P. (1985). Elements of a general theory of combinatorial structures. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol 199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028797
Download citation
DOI: https://doi.org/10.1007/BFb0028797
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15689-5
Online ISBN: 978-3-540-39636-9
eBook Packages: Springer Book Archive