<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 2" %>
Combinatorics of Geometrically Distributed Random Variables: Inversions and a Parameter of Knuth
Helmut Prodinger
The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P.O. Wits, 2050 Johannesburg, South Africa
Annals of Combinatorics 5 (2) p.241-250 June, 2001
AMS Subject Classification: 05A15
For words of length n, generated by independent geometric random variables, we consider the mean and variance of the number of inversions and of a parameter of Knuth from permutation in situ. In this way, q--analogues for these parameters from the usual permutation model are obtained.
Keywords: geometric distribution, inversions, permutations, harmonic numbers, q-analogues


1.  G. Andrews, D. Crippa, and K. Simon, q-Series arising from the study of random graphs, SIAM J. Discrete Math. 10 (1997) 41–56.

2.  G. Andrews and K. Uchimura, Identities in combinatorics, IV: differentiation and harmonic numbers, Utilitas Math. 28 (1985) 265–269.

3.  L. Devroye, A limit theory for random skip lists, Adv. Appl. Probab. 2 (1992) 597–609.

4.  P. Flajolet and G.N. Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences 31 (1985) 182–209.

5.  P. Grabner, A. Knopfmacher, and H. Prodinger, Combinatorics of Geometrically Distributed Random Variables: Run Statistics, Lecture Notes in Computer Science, 2000, pp. 457–462.

6.  R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Second Edition, Addison Wesley, 1994.

7.  D.H. Greene and D.E. Knuth, Mathematics for the Analysis of Algorithms, Second Edition, Birkhäuser, Boston, 1982.

8.  P. Kirschenhofer, H. Prodinger, and R.F. Tichy, A contribution to the analysis of in situ permutation, Glasnik Mathematicki 22 (42) (1987) 269–278.

9.  P. Kirschenhofer, C. Martínez, and H. Prodinger, Analysis of an optimized search algorithm for skip lists, Theoret. Comput. Sci. 144 (1995) 199–220.

10.  P. Kirschenhofer and H. Prodinger, On the analysis of probabilistic counting, In: Number- Theoretic Analysis, E. Hlawka and R.F. Tichy, Eds., Vol. 1452 of Lecture Notes in Mathematics, 1990, pp. 117–120.

11.  P. Kirschenhofer and H. Prodinger, A result in order statistics related to probabilistic counting, Computing 51 (1993) 15–27.

12.  P. Kirschenhofer and H. Prodinger, The path length of random skip lists, Acta Informatica 31 (1994) 775–792.

13.  P. Kirschenhofer, H. Prodinger, and W. Szpankowski, Analysis of a splitting process arising in probabilistic counting and other related algorithms, Random Structures and Algorithms 9 (1996) 379–401.

14.  A. Knopfmacher and H. Prodinger, Combinatorics of geometrically distributed random variables: value and position of the rth left-to-right maximum, Discrete Math. 226 (2001) 255– 267.

15.  D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison- Wesley, 1968, Third Edition, 1997.

16.  D.E. Knuth, Mathematical analysis of algorithms, In: Information Processing 71, pp. 19–27, North Holland Publishing Company, 1972, Proceedings of IFIP Congress, Ljubljana, 1971.

17.  D.E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison- Wesley, 1973, Second Edition, 1998.

18.  T. Papadakis, I. Munro, and P. Poblete, Average search and update costs in skip lists, BIT 32 (1992) 316–332.

19.  H. Prodinger, Combinatorial problems of geometrically distributed random variables and applications in computer science, In: Publications de l'IRMA (Straßbourg), Vol. 30, V. Strehl and R. König, Eds., 1993, pp. 87–95.

20.  H. Prodinger, Combinatorics of geometrically distributed random variables: left-to-right maxima, Discrete Math. 153 (1996) 253–270.

21.  W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Comm. ACM 33 (1990) 668–676.

22.  R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison- Wesley, 1996.

23.  R. Stanley, Enumerative Combinatorics. Vol. 2, Cambridge University Press, Cambridge, 1999.

24.  R. Stanley, A generalized riffle shuffle and quasisymmetric functions, Ann. Combin., to appear.