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.