Locally convex words and permutations (Q281597)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Locally convex words and permutations
scientific article

    Statements

    Locally convex words and permutations (English)
    0 references
    0 references
    0 references
    11 May 2016
    0 references
    Summary: We introduce some new classes of words and permutations characterized by the second difference condition \(\pi(i-1) + \pi(i+1) - 2\pi(i) \leqslant k\), which we call the \(k\)-convexity condition. We demonstrate that for any sized alphabet and convexity parameter \(k\), we may find a generating function which counts \(k\)-convex words of length \(n\). We also determine a formula for the number of 0-convex words on any fixed-size alphabet for sufficiently large \(n\) by exhibiting a connection to integer partitions. For permutations, we give an explicit solution in the case \(k = 0\) and show that the number of 1-convex and 2-convex permutations of length \(n\) are \(\Theta(C_1^n)\) and \(\Theta(C_2^n)\), respectively, and use the transfer matrix method to give tight bounds on the constants \(C_1\) and \(C_2\). We also providing generating functions similar to the the continued fraction generating functions studied by \textit{A. Odlyzko} and \textit{H. Wilf} [Am. Math. Mon. 95, No. 9, 840--843 (1988; Zbl 0673.05006)] in the ``coins in a fountain'' problem.
    0 references
    permutations
    0 references
    words
    0 references
    permutation patterns
    0 references
    transfer matrices
    0 references
    asymptotics
    0 references
    generating functions
    0 references
    integer partitions
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references