Restricted words by adjacencies (Q1567620)

The paper focuses on the enumeration of words with restricted adjacencies and contains results generalizing previous results by Fedou and Rawlings. An adjacency alphabet is a set \(\{a_{i,xy}\mid x,y\in X, i\geq 1\}\), where \(X\) is an alphabet of letters. The adjacency monomial with index \(i\) for a word \(w= x_1 x_2\cdots x_n\) is then defined as a product of the \(a_{i,xy}\). The author solves the problem of computing the series \(A_{i,j}= \sum_{w\in L_i L_{i+1}\cdots L_j} a_{i,w}w\), where the sets \(L_k\) are subsets of the alphabet \(X\). The remainder of the paper lists enumeration problems that can be solved using this methodology, by defining in each case the appropriate adjacency alphabet. Applications are given for the Fibonacci polynomials, compositions enumerated according to their number of descents, rises and number of levels, directed vertically convex polyominoes, permutations and rearrangements enumerated according to their number of descents and inversions.