Locally convex words and permutations

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 Θ(Cⁿ₁) and Θ(Cⁿ₂), respectively, and use the transfer matrix method to give tight bounds on the constants C₁ and C₂. We also providing generating functions similar to the continued fraction generating functions studied by Odlyzko and Wilf in the “coins in a fountain” problem.