Pushes in words-a primitive sorting algorithm

Authors

  • Margaret Archibald University of the Witwatersrand
  • Aubrey Blecher University of the Witwatersrand
  • Charlotte Brennan University of the Witwatersrand
  • Arnold Knopfmacher University of the Witwatersrand
  • Toufik Mansour University of Haifa

DOI:

https://doi.org/10.55016/ojs/cdm.v17i1.67951

Keywords:

words, generating functions, sorting, asymptotics

Abstract

We define the statistic of a push for words on an alphabet $[k]$ and use this to obtain a generating function measuring the degree to which an arbitrary word deviates from sorted order. Several subsidiary concepts are investigated: the number of cells that are not pushed, the number of already sorted columns, the number of cells that coincide before and after pushing, the fixed cells in words and finally, the frictionless pushes.

Author Biography

Charlotte Brennan, University of the Witwatersrand

Mathematics, Associate Professor

References

G.~Andrews, {em The theory of Partitions}, Cambridge University Press, Cambridge Mathematical Library, 1998.

M.~Archibald, A.~Blecher, C.~Brennan, A.~Knopfmacher, T.~Mansour, Shedding light on words, {em Applicable Analysis and Discrete Mathematics}, {bf 11}, (2017), 216--231.

A.~Blecher, C.~Brennan, A.~Knopfmacher and T.~Mansour, The perimeter of words, {em Discrete Maths}, {bf 340}, (2017), 2456--2465.

A.~Burstein and T.~Mansour, Words restricted by patterns with at most 2 distinct letters, {it The Electronic Journal of Combinatorics}, {bf 9:2}, (2002-3), $sharp$ R3.

P.~Flajolet and R.~Sedgewick, {it Analytic Combinatorics}, Cambridge University Press, 2009.

S.~Heubach, and T.~Mansour, Combinatorics of compositions and words, Discrete Mathematics and its applications, CRC press, Taylor and Francis group, 2010.

A.~Knopfmacher, T.~Mansour and A.~Munagi, Smooth compositions and smooth words, {it Pure Mathematics and Applications}, {bf 22}, (2011), 209--226.

A.~Knopfmacher, A.~Munagi and S.~Wagner, Successions in words and compositions, {em Annals of Comb.}, {bf 16}, (2012), 277--287

S.-M.~Ma and T.~Mansour, Pattern restricted Stirling $k$-array words, plateau statistic, and kernel method, {it Discrete Applied Mathematics}, (2016), 100--108.

T.~Mansour and M.~Shattuck, A statistic related to trees and words on a finite alphabet, {it Discrete Mathematics, Algorithms and Applications}, {bf 8:2}, (2016), 1650031.

A.~Myers and H.~Wilf, Left-to right maxima in words and multiset permutations, {it Israel Journal of Mathematics}, {bf 166}, (2008), 167--183.

H.~Prodinger, Combinatorics of geometrically distributed random variables: Left-to-right maxima, {it Discrete Mathematics}, {bf 153}, (1996), 253--270.

R.~Stanley, Enumerative combinatorics, Wadsworth and Brooks/Cole, ISBN: 0-534-06546-5, Advanced books and software, Monterey, California. 1986.

H.~Wilf, Generatingfunctionology, ISB: 0-12-751956-4, 1994, Academia Press, INC. United Kingdom.

Downloads

Published

2022-05-18

Issue

Section

Articles