Geodesic
Alphabetic points in compositions and words
Diskretnaya Matematika, Tome 33 (2021) no. 2, pp. 20-30.

Voir la notice de l'article provenant de la source Math-Net.Ru

We use generating functions to account for alphabetic points (or the lack thereof) in compositions and words. An alphabetic point is a value $j$ such that all the values to its left are not larger than $j$ and all the values to its right are not smaller than $j$. We also provide the asymptotics for compositions and words which have no alphabetic points, as the size tends to infinity. This is achieved by the construction of upper and lower bounds which converge to each other, and in the latter case by probabilistic arguments. } \keywords{generating function, fixed point, derangement, composition, word, alphabetic points, strong fixed point, asymptotics
Keywords: generating function, fixed point, derangement, composition, word, alphabetic points, strong fixed point, asymptotics. 
@article{DM_2021_33_2_a2,
     author = {M. Archibald and A. Blecher and A. Knopfmacher},
     title = {Alphabetic points in compositions and words},
     journal = {Diskretnaya Matematika},
     pages = {20--30},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_2_a2/}
}
TY  - JOUR
AU  - M. Archibald
AU  - A. Blecher
AU  - A. Knopfmacher
TI  - Alphabetic points in compositions and words
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 20
EP  - 30
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_2_a2/
LA  - ru
ID  - DM_2021_33_2_a2
ER  - 
%0 Journal Article
%A M. Archibald
%A A. Blecher
%A A. Knopfmacher
%T Alphabetic points in compositions and words
%J Diskretnaya Matematika
%D 2021
%P 20-30
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_2_a2/
%G ru
%F DM_2021_33_2_a2
M. Archibald; A. Blecher; A. Knopfmacher. Alphabetic points in compositions and words. Diskretnaya Matematika, Tome 33 (2021) no. 2, pp. 20-30. http://geodesic.mathdoc.fr/item/DM_2021_33_2_a2/

[1] M. Archibald, A. Blecher, A. Knopfmacher, “Fixed points in compositions, words”, J. Integer Seq., 23 (2020), 20.11.1 | MR

[2] P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2008 http://algo.inria.fr/flajolet/Publications/books.html | MR

[3] N. Glick, “Breaking records, breaking boards”, Amer. Math. Monthly, 85 (1978), 2–26 | DOI | MR | Zbl

[4] X. Gourdon, H. Prodinger, “A generating function approach to random subgraphs of the $n$-cycle”, Discr. Math., 1997, no. 169, 227–232 | DOI | MR | Zbl

[5] S. Heubach, T. Mansour, Combinatorics of compositions and words, CRC press, Taylor Francis Group, 2010 | MR

[6] D. E. Knuth, “The average time for carry propagation”, Indag. Math., 40 (1978), 238–242 | DOI | MR

[7] I. Kortchemski, “Asymptotic behavior of permutation records”, J. Comb. Theory A., 116:6 (2009), 1154–1166 | DOI | MR | Zbl

[8] A.N. Myers, H.S. Wilf, “Left-to-right maxima in words, multiset permutations”, Isr. J. Math., 166 (2008), 167–183 | DOI | MR | Zbl

[9] H. Prodinger, “Combinatorics of geometrically distributed random variables: Left-to-right maxima”, Discr. Math., 153 (1996), 253–270 | DOI | MR | Zbl

[10] H. Prodinger, “Records in geometrically distributed words: sum of positions”, Appl. Anal. Discr. Math., 2 (2008), 234–240 | DOI | MR | Zbl

[11] A. Rényi, “Théorie des éléments saillants d'une suite d'observations”, Ann. Fac. Sci. Univ. Clermont-Ferrand, 8 (1962), 7–13 | MR

[12] N. Sloane, The On-line Encyclopedia of Integer Sequences https://oeis.org/

[13] Stanley, R. P., Enumerative Combinatorics, v. 1, Cambridge University Press, 1999 | MR