The visibility parameter for words and permutations

Ligia Cristea; Helmut Prodinger

Open Mathematics (2013)

  • Volume: 11, Issue: 2, page 283-295
  • ISSN: 2391-5455

Abstract

top
We investigate the visibility parameter, i.e., the number of visible pairs, first for words over a finite alphabet, then for permutations of the finite set {1, 2, …, n}, and finally for words over an infinite alphabet whose letters occur with geometric probabilities. The results obtained for permutations correct the formula for the expectation obtained in a recent paper by Gutin et al. [Gutin G., Mansour T., Severini S., A characterization of horizontal visibility graphs and combinatorics on words, Phys. A, 2011, 390 (12), 2421–2428], and for words over a finite alphabet the formula obtained in the present paper for the expectation is more precise than that obtained in the cited paper. More importantly, we also compute the variance for each case.

How to cite

top

Ligia Cristea, and Helmut Prodinger. "The visibility parameter for words and permutations." Open Mathematics 11.2 (2013): 283-295. <http://eudml.org/doc/269708>.

@article{LigiaCristea2013,
abstract = {We investigate the visibility parameter, i.e., the number of visible pairs, first for words over a finite alphabet, then for permutations of the finite set \{1, 2, …, n\}, and finally for words over an infinite alphabet whose letters occur with geometric probabilities. The results obtained for permutations correct the formula for the expectation obtained in a recent paper by Gutin et al. [Gutin G., Mansour T., Severini S., A characterization of horizontal visibility graphs and combinatorics on words, Phys. A, 2011, 390 (12), 2421–2428], and for words over a finite alphabet the formula obtained in the present paper for the expectation is more precise than that obtained in the cited paper. More importantly, we also compute the variance for each case.},
author = {Ligia Cristea, Helmut Prodinger},
journal = {Open Mathematics},
keywords = {Words; Permutations; q-enumeration; words; permutations; -enumeration},
language = {eng},
number = {2},
pages = {283-295},
title = {The visibility parameter for words and permutations},
url = {http://eudml.org/doc/269708},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Ligia Cristea
AU - Helmut Prodinger
TI - The visibility parameter for words and permutations
JO - Open Mathematics
PY - 2013
VL - 11
IS - 2
SP - 283
EP - 295
AB - We investigate the visibility parameter, i.e., the number of visible pairs, first for words over a finite alphabet, then for permutations of the finite set {1, 2, …, n}, and finally for words over an infinite alphabet whose letters occur with geometric probabilities. The results obtained for permutations correct the formula for the expectation obtained in a recent paper by Gutin et al. [Gutin G., Mansour T., Severini S., A characterization of horizontal visibility graphs and combinatorics on words, Phys. A, 2011, 390 (12), 2421–2428], and for words over a finite alphabet the formula obtained in the present paper for the expectation is more precise than that obtained in the cited paper. More importantly, we also compute the variance for each case.
LA - eng
KW - Words; Permutations; q-enumeration; words; permutations; -enumeration
UR - http://eudml.org/doc/269708
ER -

References

top
  1. [1] Flajolet Ph., Martin G.N., Probabilistic counting algorithms for data base applications, J. Comput. System Sci., 1985, 31(2), 182–209 http://dx.doi.org/10.1016/0022-0000(85)90041-8 Zbl0583.68059
  2. [2] Graham R.L., Knuth D.E., Patashnik O., Concrete Mathematics, 2nd ed., Addison-Wesley, Reading, 1994 
  3. [3] 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 
  4. [4] Prodinger H., Combinatorics of geometrically distributed random variables: left-to-right maxima, In: 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, June 21–25, 1993, Discrete Math., Elsevier, Amsterdam, 1996, 153(1–3), 253–270 
  5. [5] Prodinger H., A q-analogue of the path length of binary search trees, Algorithmica, 2001, 31(3), 433–441 http://dx.doi.org/10.1007/s00453-001-0058-y Zbl0989.68035
  6. [6] 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 Zbl0994.05012
  7. [7] Pugh W., Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, 1990, 33(6), 668–676 http://dx.doi.org/10.1145/78973.78977 

NotesEmbed ?

top

You must be logged in to post comments.