Proof of Two Conjectures of Brenti and Simion
on Kazhdan-Lusztig Polynomials

We find an explicit formula for the Kazhdan-Lusztig polynomials Pui,a,vi
of the symmetric group S(
n) where, for a, i, n \in N such that 1 \leq a \leq i \leq n,
we denote by
ui,a = sasa+1 ··· si-1 and by vi the element of S(n) obtained
by inserting
n in position i in any permutation of S(n - 1) allowed to rise
only in the first and in the last place. Our result implies, in particular,
the validity of two conjectures of Brenti and Simion [
Explicit formulae for some
classes of Kazhdan-Lusztig polynomials, J. Algebraic Combin. 11 (2000),  187-196,
Conjectures 4.2 and 4.3], and includes as a special case a result of Shapiro, Shapiro
and Vainshtein [Kazhdan-Lusztig polynomials for certain varieties of incomplete
flags, Discr. Math. 180 (1998), 345-355, Theorem 1].
All the proofs are purely combinatorial and make no use of the geometry
of the corresponding Schubert varieties.

Home