Combinatorial Expansions of Kazhdan-Lusztig Polynomials

We introduce two related families of polynomials, easily computableby simple recursions into which any Kazhdan–Lusztig (andinverse Kazhdan–Lusztig) polynomial of any Coxeter groupcan be expanded linearly, and we give combinatorial interpretationsto the coefficients in these expansions. This yields a combinatorialrule for computing the Kazhdan–Lusztig polynomials interms of paths in a directed graph, and a completely combinatorialreformulation of the nonnegativity conjecture 15, p. 166].