Abstract
A class of diamond-shaped combinatorial structures is studied whose enumerating generating functions satisfy differential equations of the form \(f'' = G(f)\), for some function G. In addition to their own interests and being natural extensions of increasing trees, the study of such DAG-structures was motivated by modelling executions of series-parallel concurrent processes; they may also be used in other digraph contexts having simultaneously a source and a sink, and are closely connected to a few other known combinatorial structures such as trees, cacti and permutations. We explore in this extended abstract the analytic-combinatorial aspect of these structures, as well as the algorithmic issues for efficiently generating random instances.
This research was partially supported by the ANR MetACOnc project ANR-15-CE40-0014.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We limit our discussion in this paper to the situation when \(f'(0)=1\) for simplicity.
References
Abramowitz, M., Stegun, I.: Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables. Dover Publications, New York (2012)
Ando, E., Nakata, T., Yamashita, M.: Approximating the longest path length of a stochastic DAG by a normal distribution in linear time. J. Discrete Algorithms 7(4), 420–438 (2009)
Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: Raoult, J.-C. (ed.) CAAP ’92. LNCS, vol. 581, pp. 24–48. Springer, Heidelberg (1992)
Bodini, O.: Autour de la génération aléatoire sous modèle de Boltzmann. Habilitation thesis, UPMC (2010)
Bodini, O., Roussel, O., Soria, M.: Boltzmann samplers for first-order differential specifications. Discrete Appl. Math. 160(18), 2563–2572 (2012)
Chern, H.-H., Fernández-Camacho, M.-I., Hwang, H.-K., Martínez, C.: Psi-series method for equality of random trees and quadratic convolution recurrences. Random Struct. Algorithms 44(1), 67–108 (2014)
Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Comb. Prob. Comput. 13(4–5), 577–625 (2004)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Knuth, D.E.: The Art of Computer Programming, volume 1 (3rd ed.): Fundamental Algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA (1997)
Kuba, M., Panholzer, A.: A combinatorial approach to the analysis of bucket recursive trees. Theor. Comput. Sci. 411(34–36), 3255–3273 (2010)
Kuba, M., Panholzer, A.: Bilabelled increasing trees and hook-length formulae. Eur. J. Combin. 33(2), 248–258 (2012)
Kuba, M., Panholzer, A.: Combinatorial families of multilabelled increasing trees and hook-length formulas. Discrete Math. 339, 227–254 (2016)
Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Can. J. Math. 30(5), 997–1015 (1978)
Stanley, R.: Catalan Numbers. Cambridge University Press, Cambridge (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodini, O., Dien, M., Fontaine, X., Genitrini, A., Hwang, HK. (2016). Increasing Diamonds. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)