  We introduce the structure of vacillating Hecke tableaux, and establish a
one-to-one correspondence between vacillating Hecke tableaux and linked
partitions by using the Hecke insertion algorithm developed by Buch, Kresch,
Shimozono, Tamvakis and Yong. Linked partitions arise in free probability
theory. Motivated by the Hecke insertion algorithm, we define a Hecke diagram
as a Young diagram possibly with a marked corner. A vacillating Hecke tableau
is defined as a sequence of Hecke diagrams subject to certain addition and
deletion of rook strips. The notion of a rook strip was introduced by Buch in
the study of the Littlewood-Richardson rule for stable Grothendieck
polynomials. A rook strip is a skew Young diagram with at most one square in
each row and column. We show that the crossing number and the nesting number of
a linked partition can be determined by the maximal number of rows and the
maximal number of columns of the diagrams in the corresponding vacillating
Hecke tableau. The proof relies on a theorem due to Thomas and Yong concerning
the lengths of the longest strictly increasing and the longest strictly
decreasing subsequences in a word. This implies that the crossing number and
the nesting number have a symmetric joint distribution over linked partitions,
confirming a conjecture of de Mier. We also prove a conjecture of Kim which
states that the crossing number and the nesting number have a symmetric joint
distribution over the front representations of partitions.
