Foata, Hikita, and the Bulldozer Problem

Abstract

In a remarkable paper, Tatsuyuki Hikita settled a longstanding e-positivity conjecture of Stanley and Stembridge. Among many other things, he wrote down a certain formula ${\phi }_k$, and proved that the ${\phi }_k$ sum to one, thereby defining a probability distribution. Though Hikita's proof was simple, it remains surprising that the ${\phi }_k$ sum to one. In this note, we give a combinatorial interpretation of Hikita's probability distribution. The main tool is a certain permutation statistic that we call the watershed. After seeing an early version of our work, Darij Grinberg noticed that the permutation statistic was implicit in a so-called "bulldozer problem" that was on the short list for the 2015 International Mathematics Olympiad. However, our description of the statistic, which makes use of the Renyi-Foata bijection, appears to be new.

8 pages