We introduce some new classes of words and permutations characterized by the second difference condition $\pi(i-1) + \pi(i+1) - 2\pi(i) \leq 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 Odlyzko and Wilf in the "coins in a fountain" problem.
@article{10_37236_5396,
author = {Christopher Coscia and Jonathan DeWitt},
title = {Locally convex words and permutations},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {2},
doi = {10.37236/5396},
zbl = {1335.05004},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5396/}
}
TY - JOUR
AU - Christopher Coscia
AU - Jonathan DeWitt
TI - Locally convex words and permutations
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5396/
DO - 10.37236/5396
ID - 10_37236_5396
ER -
%0 Journal Article
%A Christopher Coscia
%A Jonathan DeWitt
%T Locally convex words and permutations
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5396/
%R 10.37236/5396
%F 10_37236_5396
Christopher Coscia; Jonathan DeWitt. Locally convex words and permutations. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5396
