Visits to Level r by Dyck Paths

• Autorzy: Brennan C. , Mavhungu S.
• Języki publikacji: EN

Abstrakty

EN

A Dyck path is a non-negative lattice path in N2 starting at the origin, where only two types of steps are allowed: the diagonal up step (1, 1) and the diagonal down step (1,-1). The length of the path is the total number of unit steps. We consider paths of length n, ending at the point (n, i). A path is considered to be closed if i = 0 and open if i . 0. This aim of this paper is to find asymptotic expressions for the first and second moments of the number of visits to a certain level r a Dyck path makes. We investigate open and closed paths separately where we investigate the two different cases r > 0 and r = 0. We use generating functions which are found using recursions. These recursions are solved using matrix algebra. Asymptotic expressions for the expected value and variance are obtained using singularity analysis where the generating functions are expanded around the dominant singularities.

Słowa kluczowe

EN

Dyck path

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 127--145
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Brennan C.

autor

Mavhungu S.

• The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics University of the Witwatersrand, P.O. Wits 2050, Johannesburg, South Africa,

Bibliografia

• [1] Callen, D.: Bijections for the identity 4n[…] , 2004, http://www.stat.wisc.edu/ callan/papersother/.
• [2] Deutsch, E.: A bijection on Dyck paths and its consequences, Discrete Mathematics, 179, 1998, 253-256.
• [3] Deutsch, E.: Dyck path enumeration, Discrete Mathematics, 204, 1999, 167-202.
• [4] Dwass, M.: Simple random walk and rank order statistics, Annals of Mathematical Statistics, 38, 1967, 1042-1053.
• [5] Elizalde, S.: Statistics on Pattern-avoiding Permutations, Ph.D. Thesis, MIT, 2004.
• [6] Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions, SIAM Journal on Discrete Mathematics, 3:2, 1990, 216-240.
• [7] Flajolet, P., Sedgewick, R.: An introduction to the Analysis of Algorithms, AddisonWesley, 2001.
• [8] Flajolet, P., Sedgewick, R.: Analytic Combinatorics, Cambridge University Press, 2009.
• [9] Katzenbeisser, W., Hackl, P.: An alternative to the Kolmogorov-Smirnov two-sample test. Communications in Statistics - Theory and Methods, 15, 1986, 1163-1177.
• [10] Katzenbeisser, W., Panny, W.: A note on the higher moments of the random variable T associated with the number of returns of a simple random walk. Advances in Applied Probability, 18, 1986, 279-282.
• [11] Katzenbeisser, W., Panny, W.: On the number of times a simple random walk reaches a nonnegative height, Journal of Applied Probability, 29, 1992, 305-312.
• [12] Katzenbeisser,W., Panny,W.: Simple random walk statistics. Part I: Discrete time results, Journal of Applied Probability, 33, 1996, 311-330.
• [13] Kemp, A.: The moments of the randomvariable for the number of returns of a simple random walk, Advances in Applied Probability, 19, 1987, 505-507.
• [14] Kirschenhofer, P., Prodinger, H.: Return statistics of simple random walks, Journal of Statistical Planning and Inference, 54, 1996, 67-74.
• [15] Krattenthaler, C.: Permutations with restricted patterns and Dyck paths, Advances in Applied Mathematics, 27, 2001, 510-530.
• [16] Mansour, T.: Counting peaks at height k in a Dyck path, Journal of Integer Sequences, 5, 2002, Article 02.1.1.
• [17] Mansour, T.: Statistics on Dyck paths, Journal of Integer Sequences, 9, 2006, Article 06.1.5.
• [18] McGilchrist, C., Woodyer, K.: Note on a distribution-free CUSUM technique, Technometrics, 17, 1975, 321-325.
• [19] Mohanty, G.: Lattice path counting and applications, Probability and Mathematical statistics: Monographs and Textbooks, Academic Press, 1979, New York.
• [20] Moon, J.: Counting labelled trees, Canadian Mathematical Congress, Montreal, 1970.
• [21] Panayotopoulos, A., Sapounakis, A.: On the prime decomposition of Dyck words, Journal of Combinatorial Mathematics and Combinatorial Computing, 40, 2002, 33-39.
• [22] Peart, P., Woan, W. J.: Dyck paths with no peaks at height k, Journal of Integer Sequences, 4, 2001, Article 01.1.3.
• [23] Saran, J.: Joint distributions based on the number of runs and some other two-sample rank order statistics for arbitrary sample sizes, Journal of Statistical Planning and Inference, 47, 1995, 257-275.