Lattice paths and Kazhdan-Lusztig polynomials

The purpose of this paper is to present a new non-recursive combinatorial formula for the Kazhdan-Lusztig polynomials of a Coxeter group $W$. More precisely, we show that each directed path in the Bruhat graph of $W$ has a naturally associated set of lattice paths with the property that the Kazhdan-Lusztig polynomial of $u,v$ is the sum, over all the lattice paths associated to all the paths going from $u$ to $v$, of $(-1)^{\Gamma _{\ge 0}+d_+(\Gamma)}q^{(l(v)-l(u)+\Gamma(l(\Gamma)))/2}$ where $\Gamma _{\ge 0}, d_+(\Gamma)$, and $\Gamma(l(\Gamma))$ are three natural statistics on the lattice path.