Locally convex words and permutations (Q281597)

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.