Abstract
We consider the bargraph representation of geometrically distributed words, which we use to define the water capacity of such words. We first find a bivariate capacity generating function for all geometrically distributed words, from which we compute the generating function for the mean capacity. Thereafter, by making extensive use of Rice’s method (Rice’s integrals) we derive an asymptotic formula for the average capacity of random words of length n as n tends to infinity.
Similar content being viewed by others
References
Blecher, A., Brennan, C., Knopfmacher, A.: Capacity of words. J. Combin. Math. Combin. Comput. 107, 249–258 (2018)
Blecher, A., Brennan, C., Knopfmacher, A.: The water capacity of integer compositions. Online J. Anal. Combin. 13, 6 (2018)
Blecher, A., Brennan, C., Knopfmacher, A., Shattuck, M.: Water capacity of permutations. Annales Mathematicae et Informaticae 50, 39–56 (2019)
Blecher, A., Brennan, C., Knopfmacher, A.: Water capacity of Dyck paths. Adv. Appl. Math. 112, 101945 (2020)
Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and Rice��s integrals. Theor. Comput. Sci. 144, 101–124 (1995)
Knopfmacher, A., Prodinger, H.: Combinatorics of geometrically distributed random variables: value and position of the r-th left-to-right maximum. Discrete Math. 226, 255–267 (2001)
Mansour, T., Shattuck, M.: Counting water cells in bargraphs of compositions and set partitions. Appl. Anal. Discrete Math. 12, 413–438 (2018)
Prodinger, H.: On the m-enumeration of maximum and left-to-right maxima in geometrically distributed words. Pure Math. Appl. 23(2), 143–154 (2012)
Prodinger, H.: Combinatorics of geometrically distributed random variables: value and position of large left-to-right maxima. Discrete Math. 254, 459–471 (2002)
Prodinger, H.: Combinatorics of geometrically distributed random variables: left-to-right maxima. Discrete Math. 153, 253–270 (1996)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This material is based upon work supported by the National Research Foundation under Grant Numbers 89147 and 81021.
Rights and permissions
About this article
Cite this article
Archibald, M., Knopfmacher, A. The water capacity of geometrically distributed words. Aequat. Math. 95, 777–796 (2021). https://doi.org/10.1007/s00010-021-00785-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00010-021-00785-y