Words that almost commute

The Hamming distance $\mathrm{ham}(u,v)$ between two equal-length words u, v is the number of positions where u and v differ. The words u and v are said to be conjugates if there exist non-empty words $x,y$ such that $u=xy$ and $v=yx$. The smallest value $\mathrm{ham}(xy,yx)$ can take on is 0, when x and y commute. But, interestingly, the next smallest value $\mathrm{ham}(xy,yx)$ can take on is 2 and not 1. In this paper, we consider conjugates $u=xy$ and $v=yx$ where $\mathrm{ham}(xy,yx)=2$. More specifically, we provide an efficient formula to count the number $h(n)$ of length-n words $u=xy$ over a k-letter alphabet that have a conjugate $v=yx$ such that $\mathrm{ham}(xy,yx)=2$. We also provide efficient formulae for other quantities closely related to $h(n)$. Finally, we show that $h(n)$ grows erratically: cubically for n prime, but exponentially for n even.