Recherche et téléchargement d’archives de revues mathématiques numérisées

  Table des matières de ce fascicule | Article précédent | Article suivant
Grabner, P. J.; Prodinger, H.; Tichy, R. F.
Asymptotic analysis of a class of functional equations and applications. Journal de théorie des nombres de Bordeaux, 5 no. 2 (1993), p. 365-381
Texte intégral djvu | pdf | Analyses MR 1265911 | Zbl 0797.39008

URL stable:

Voir cet article sur le site de l'éditeur


Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for $z \rightarrow \infty$ by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of $N$ people is computed, where each person advances one step or dies with equal probabilities, and an additional “killer” can kill at any level up to $d$ survivors, according to his probability distribution.


[1] T.M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984.  MR 434929 |  Zbl 0335.10001
[2] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoret. Comput. Sci. (to appear).  MR 1256203 |  Zbl 0788.44004
[3] P. Flajolet and L.B. Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305-320.  MR 1164843 |  Zbl 0758.60015
[4] P. Flajolet, M. Régnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer, New York, 1985.  MR 815343 |  Zbl 0582.68015
[5] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216-240.  MR 1039294 |  Zbl 0712.05004
[6] P. Flajolet and J. Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A "Algorithms and Complexity" North-Holland, 1990, 431-524.  MR 1127175 |  Zbl 0900.68251
[7] D.E. Knuth, The Art of Computer Science Vol. 3, Addison Wesley, Reading, MA, 1973.
[8] H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992.  MR 1140708 |  Zbl 0762.68033
[9] J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad. 59 (1983), 441-444.
Article |  MR 732606 |  Zbl 0541.10040
[10] H. Prodinger, How to, Advance on a Staircase by Coin Flippings,, Proceedings "Fibonacci Numbers and Applications 5" (1992) (to appear).  Zbl 0807.68056
[11] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927.  JFM 53.0180.04
Copyright Cellule MathDoc 2016 | Crédit | Plan du site