The box parameter for words counts how often two letters w j and w k define a “box” such that all the letters w j+1; ..., w k−1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n − 2n H M/M, for fixed M and n → ∞.
@article{bwmeta1.element.doi-10_2478_s11533-013-0277-x,
author = {Helmut Prodinger},
title = {The box parameter for words and permutations},
journal = {Open Mathematics},
volume = {12},
year = {2014},
pages = {167-174},
zbl = {1290.05006},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0277-x}
}
Helmut Prodinger. The box parameter for words and permutations. Open Mathematics, Tome 12 (2014) pp. 167-174. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0277-x/
[1] Blümlein J., Hasselhuhn A., Schneider C., Evaluation of multi-sums for large scale problems, In: Proceedings of RADCOR 2011, DESY, 2012, available at http://arxiv.org/abs/1202.4303
[2] Cristea L.L., Prodinger H., The visibility parameter for words and permutations, Cent. Eur. J. Math., 2013, 11(2), 283–295 http://dx.doi.org/10.2478/s11533-012-0135-2 | Zbl 1258.05001
[3] Flajolet P., Salvy B., Euler sums and contour integral representations, Experiment. Math., 1998, 7(1), 15–35 http://dx.doi.org/10.1080/10586458.1998.10504356 | Zbl 0920.11061
[4] Gutin G., Mansour T., Severini S., A characterization of horizontal visibility graphs and combinatorics on words, Phys. A, 2011, 390(12), 2421–2428 http://dx.doi.org/10.1016/j.physa.2011.02.031
[5] Prodinger H., Combinatorics of geometrically distributed random variables: inversions and a parameter of Knuth, Ann. Comb., 2001, 5(2), 241–250 http://dx.doi.org/10.1007/s00026-001-8010-z | Zbl 0994.05012
[6] Prodinger H., A q-analogue of the path length of binary search trees, In: Mathematical Analysis of Algorithms, Algorithmica, 2001, 31(3), 433–441 17 | Zbl 0989.68035