2014/10/28 by Christopher Coscia, Coscia, Christopher, Jonathan DeWitt +1
Computer Science · Mathematics · #05A05 #05A15 #05A16 #05A17 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1410.7818
openalex publication_date 2014/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce some new classes of words and permutations characterized by the second difference condition π(i-1) + π(i+1) - 2π(i) ≤ 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 Θ(C1n) and Θ(C2n), respectively, and use the transfer matrix method to give tight bounds on the constants C1 and C2. We also providing generating functions similar to the the continued fraction generating functions studied by Odlyzko and Wilf in the "coins in a fountain" problem.