Knopfmacher, Arnold; Munagi, Augustine; Wagner, Stephan Successions in words and compositions. (English) Zbl 1256.05006 Ann. Comb. 16, No. 2, 277-287 (2012). Summary: We consider words over the alphabet \([k] = \{1, 2, \ldots, k\}\), \(k \geq 2\). For a fixed nonnegative integer \(p\), a \(p\)-succession in a word \(w _{1} w _{2} \dots w _{n }\) consists of two consecutive letters of the form (\(w _{i }, w _{i } + p\)), \(i = 1, 2, \ldots , n - 1\). We analyze words with respect to a given number of contained \(p\)-successions. First we find the mean and variance of the number of \(p\)-successions. We then determine the distribution of the number of \(p\)-successions in words of length \(n\) as \(n\) (and possibly \(k\)) tends to infinity; a simple instance of a phase transition (Gaussian-Poisson-degenerate) is encountered. Finally, we also investigate successions in compositions of integers. Cited in 9 Documents MSC: 05A05 Permutations, words, matrices 05A15 Exact enumeration problems, generating functions 05A16 Asymptotic enumeration Keywords:words; compositions; successions; limiting distributions Software:OEIS; GJsqfree; GJseries; SYMGJ; BLANKS; GJSAW; NAIVE; DAVID_IAN; SPGJ; JODO PDFBibTeX XMLCite \textit{A. Knopfmacher} et al., Ann. Comb. 16, No. 2, 277--287 (2012; Zbl 1256.05006) Full Text: DOI References: [1] Bassino F., Clément, J., Fayolle, J., Nicodème, P.: Counting occurrences for a finite set of words: an inclusion-exclusion approach. Discrete Math. Theor. Comput. Sci. Proc. 29–44 (2007) · Zbl 1192.68942 [2] Bender E.A., Kochman F.: The distribution of subword counts is usually normal. European J. Combin. 14(4), 265–275 (1993) · Zbl 0776.68097 [3] Curtiss J.H.: A note on the theory of moment generating functions. Ann. Math. Statistics 13, 430–433 (1942) · Zbl 0063.01024 [4] Dymacek W., Roselle D.P.: Circular permutations by number of rises and successions. J. Combin. Theory Ser. A 25(2), 196–201 (1978) · Zbl 0404.05001 [5] Flajolet P., Sedgewick R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001 [6] Goulden I.P., Jackson D.M.: Combinatorial Enumeration. Dover Publications, Mineola, NY (2004) · Zbl 1099.05005 [7] Guibas L.J., Odlyzko A.M.: String overlaps, pattern matching, and nontransitive games. J. Combin. Theory Ser. A 30(2), 183–208 (1981) · Zbl 0454.68109 [8] Hwang H.-K.: On convergence rates in the central limit theorems for combinatorial structures. European J. Combin 19(3), 329–343 (1998) · Zbl 0906.60024 [9] Kaplansky I.: Solution of the ”problème des ménages”. Bull. Amer. Math. Soc 49(10), 784–785 (1943) · Zbl 0060.02904 [10] Knopfmacher A., Munagi A.O.: Successions in integer partitions. Ramanujan J. 18(3), 239–255 (2009) · Zbl 1225.11129 [11] Munagi A.O.: Combinations with successions and Fibonacci numbers. Fibonacci Quart 45(2), 104–114 (2007) · Zbl 1159.05006 [12] Munagi A.O.: Extended set partitions with successions. European J. Combin 29(5), 1298–1308 (2008) · Zbl 1149.05004 [13] Munagi A.O.: Set partitions with successions and separations. Int. J. Math. Math. Sci 2005(3), 451–463 (2005) · Zbl 1076.05009 [14] Noonan J., Zeilberger D.: The Goulden-Jackson cluster method: extensions, applications and implementations. J. Differ. Equations Appl. 5(4-5), 355–377 (1999) · Zbl 0935.05003 [15] Reilly J.W., Tanny S.M.: Counting permutations by successions and other figures. Discrete Math 32(1), 69–76 (1980) · Zbl 0462.05009 [16] Reilly J.R., Tanny S.M.: Counting successions in permutations. Stud. Appl. Math 61(1), 73–81 (1979) · Zbl 0418.05005 [17] Riordan J.: Permutations without 3-sequences. Bull. Amer. Math. Soc. 51, 745–748 (1945) · Zbl 0060.02902 [18] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. published electronically at http://www.research.att.com/\(\sim\)njas/sequences/ · Zbl 1274.11001 [19] Szpankowski W.: Average Case Analysis of Algorithms on Sequences. Wiley-Interscience, New York (2001) · Zbl 0968.68205 [20] Tanny S.M.: Permutations and successions. J. Combin. Theory Ser. A 21(2), 196–202 (1976) · Zbl 0339.05004 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.