The box parameter for words and permutations

• Autorzy: Helmut Prodinger
• Języki publikacji: EN

Abstrakty

EN

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 → ∞.

Słowa kluczowe

EN

Words; Permutations; q-enumeration

Kategorie tematyczne

• 05A05: Permutations, words, matrices
• 05A30: q -calculus and related topics

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2014
• Tom: 12
• Numer: 1
• Strony: 167-174

Daty

wydano

2014-01-01

online

2013-10-30

Twórcy

autor

Helmut Prodinger

• Stellenbosch University

Bibliografia

• [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
• [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
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-013-0277-x