Counting Abelian Squares

L. B. Richmond, Jeffrey Shallit


An abelian square is a nonempty string of length $2n$ where the last $n$ symbols form a permutation of the first $n$ symbols. Similarly, an abelian $r$'th power is a concatenation of $r$ blocks, each of length $n$, where each block is a permutation of the first $n$ symbols. In this note we point out that some familiar combinatorial identities can be interpreted in terms of abelian powers. We count the number of abelian squares and give an asymptotic estimate of this quantity.

Full Text: