In 1993, Haiman studied certain functions from the Hecke algebra to Z[q] called monomial traces. He conjectured that the evaluation of these at Kazhdan-Lusztig basis elements resulted in polynomials in N[q]. A weakening of this conjecture is that the evaluation of other traces, called power sum traces, results in polynomials in N[q]. We will discuss several combinatorial interpretations of these polynomials for Kazhdan-Lusztig basis elements indexed by permutations which avoid the patterns 3412 and 4231. These interpretations come from joint work with Mathhew Hyatt, and results of Athanasiadis, Shareshian, and Wachs.