Leading coefficients of Kazhdan-Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan-Lusztig polynomial P (x,w) (q) known as mu(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111-136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar's algorithm (Deodhar in Geom. Dedicata 63(1):95-119, [1990]), we provide some combinatorial criteria to determine when mu(x,w)=1 for such permutations w.