Successions in Words and Compositions

详细信息    查看全文

• 作者：Arnold Knopfmacher (1) Arnold.Knopfmacher@wits.ac.za
  Augustine Munagi (1) augustine.munagi@wits.ac.za
  Stephan Wagner (2) swagner@sun.ac.za
• 关键词：words &#8211 ; compositions &#8211 ; successions &#8211 ; limiting distributions
• 刊名：Annals of Combinatorics
• 出版年：2012
• 出版时间：June 2012
• 年：2012
• 卷：16
• 期：2
• 页码：277-287
• 全文大小：266.9 KB
• 参考文献：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)
  2. Bender E.A., Kochman F.: The distribution of subword counts is usually normal. European J. Combin. 14(4), 265–275 (1993)
  3. Curtiss J.H.: A note on the theory of moment generating functions. Ann. Math. Statistics 13, 430–433 (1942)
  4. Dymacek W., Roselle D.P.: Circular permutations by number of rises and successions. J. Combin. Theory Ser. A 25(2), 196–201 (1978)
  5. Flajolet P., Sedgewick R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
  6. Goulden I.P., Jackson D.M.: Combinatorial Enumeration. Dover Publications, Mineola, NY (2004)
  7. Guibas L.J., Odlyzko A.M.: String overlaps, pattern matching, and nontransitive games. J. Combin. Theory Ser. A 30(2), 183–208 (1981)
  8. Hwang H.-K.: On convergence rates in the central limit theorems for combinatorial structures. European J. Combin 19(3), 329–343 (1998)
  9. Kaplansky I.: Solution of the “probl猫me des m茅nages”. Bull. Amer. Math. Soc 49(10), 784–785 (1943)
  10. Knopfmacher A., Munagi A.O.: Successions in integer partitions. Ramanujan J. 18(3), 239–255 (2009)
  11. Munagi A.O.: Combinations with successions and Fibonacci numbers. Fibonacci Quart 45(2), 104–114 (2007)
  12. Munagi A.O.: Extended set partitions with successions. European J. Combin 29(5), 1298–1308 (2008)
  13. Munagi A.O.: Set partitions with successions and separations. Int. J. Math. Math. Sci 2005(3), 451–463 (2005)
  14. Noonan J., Zeilberger D.: The Goulden-Jackson cluster method: extensions, applications and implementations. J. Differ. Equations Appl. 5(4-5), 355–377 (1999)
  15. Reilly J.W., Tanny S.M.: Counting permutations by successions and other figures. Discrete Math 32(1), 69–76 (1980)
  16. Reilly J.R., Tanny S.M.: Counting successions in permutations. Stud. Appl. Math 61(1), 73–81 (1979)
  17. Riordan J.: Permutations without 3-sequences. Bull. Amer. Math. Soc. 51, 745–748 (1945)
  18. Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. published electronically at http://www.research.att.com/~njas/sequences/
  19. Szpankowski W.: Average Case Analysis of Algorithms on Sequences. Wiley-Interscience, New York (2001)
  20. Tanny S.M.: Permutations and successions. J. Combin. Theory Ser. A 21(2), 196–202 (1976)
• 作者单位：1. The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, Private Bag 3, Johannesburg, South Africa2. Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, 7602 Stellenbosch, South Africa
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  
• 出版者：Birkh盲user Basel
• ISSN：0219-3094

文摘

We consider words over the alphabet [k] = {1, 2, . . . , k}, k ≥ 2. For a fixed nonnegative integer p, a p-succession in a word w ₁ w ₂ . . . w _n consists of two consecutive letters of the form (w _i , w _i + p), i = 1, 2, . . . , 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.