%%This is an AMS-LaTeX 1.2 file submitted to  
%%Sem. Lotharingien et Combinatoire
\documentclass[12pt,twoside]{amsart} 
\usepackage{amssymb,amsmath,amscd} 
\pagestyle{headings}  

\thispagestyle{plain}  
\textwidth 420pt \oddsidemargin 20pt \evensidemargin 20pt 
\headsep 20pt \flushbottom  \textheight 620pt 
\theoremstyle{plain} 
\newtheorem{Lem}{Lemma}[section] 
\newtheorem{Prop}[Lem]{Proposition} 
\newtheorem{Thm}[Lem]{Theorem} 
\newtheorem{Cor}[Lem]{Corollary} 
\theoremstyle{definition} 
\newtheorem{Def}[Lem]{Definition} 
\newtheorem{Rem}[Lem]{Remark} 
\newtheorem{Ex}[Lem]{Example} 
%\theoremstyle{remark} 
\errorcontextlines=0  \numberwithin{equation}{section} 
\newcommand{\ccn}[1]{\framebox(10,10){{\scriptsize #1}}} 
\newcommand{\ccx}{\framebox(10,10){\mbox{$\times$}}} 
\newcommand{\ccd}{\makebox(10,10){$\cdot$}} 
\newcommand{\C}{\mbox{$\mathbb C$}} 
\newcommand{\R}{\mbox{$\mathbb R$}} 
\newcommand{\Q}{\mbox{$\mathbb Q$}} 
\newcommand{\Z}{\mbox{$\mathbb Z$}} 
\newcommand{\N}{\mbox{$\mathbb N$}} 
\newcommand{\K}{\mbox{$\mathbb K$}} 
\newcommand{\llll}{\mbox{${\bf L}$}} 
\newcommand{\bpi}{\begin{picture}} 
\newcommand{\epi}{\end{picture}} 
\newcommand{\gdw}{\Longleftrightarrow} 
\newcommand{\Lra}{\Longrightarrow} 
\newcommand{\lra}{\longrightarrow} 


\begin{document} 
\phantom{.}
\vspace*{-2.5cm}

{\sc S\'eminaire Lotharingien de Combinatoire, B39a(1997), 28pp.}
\vspace*{2cm}

\title[Graded Schubert functions] 
{Schubert functions and the number of reduced words of permutations} 
\date{July 1996} 
\author[R. Winkel]{Rudolf Winkel}  
\address{Institut f\"ur Reine und Angewandte Mathematik \\  RWTH Aachen \\ 
D-52056 Aachen \\ Germany\\ {\it papers/preprints}: 
http://www.iram.rwth-aachen.de/ $\sim$winkel/}  
\email{winkel@iram.rwth-aachen.de}  
\subjclass{14M15, 05E15, 20F55} 
\maketitle 
 
{\small {\it Abstract}: It is well known that a Schur function is the 
`limit' of a sequence of Schur polynomials in an increasing number of 
variables, and that Schubert polynomials generalize Schur polynomials. 
We show that the set of Schubert polynomials can be organized into 
sequences, whose `limits' we call Schubert functions. A graded 
version of these Schubert functions can be computed effectively by the 
application of mixed shift/multiplication operators to the sequence of  
variables $x=(x_{1}, x_{2}, x_{3}, \dots\ )$. This generalizes the 
Baxter operator approach to graded Schur functions of G.P. Thomas, 
and allows the easy introduction of skew Schubert polynomials and 
functions. 
 
Since the computation of these operator formulas relies basically on  
the knowledge of the set of reduced words of permutations, it seems natural 
that in turn the number of reduced words of a permutation can be 
determined with the help of Schubert functions: we describe new 
algebraic formulas and a combinatorial procedure, which allow the 
effective determination of the number of reduced words for an arbitrary 
permutation in terms of Schubert polynomials.}\\ \\ 
 
Let $S_{n}$ denote the symmetric group on 
the `letters' $\{1 , \dots , n\}$ and $\Z[x_{1},\dots, x_{n}]^{S_{n}}$ 
the $\Z$-algebra of symmetric polynomials in $n$ variables. There are 
several well known $\Z$-bases of this algebra (cf. [M1, Sa]), which 
are indexed by the partitions $\lambda \equiv \lambda _{1} \dots\ \lambda_{s}$  
($\lambda _{1} \geq \dots\ \geq \lambda_{s}\geq 1$) with length  
$l(\lambda ):=s \leq n$. The most important of these bases are the 
Schur polynomials  
$s_{\lambda }^{(n)}(x) := s_{\lambda }(x_{1},\dots, x_{n})$, which 
can be defined alternatively by determinant formulas or 
combinatorially with the help of semistandard Young tableaux. The Schur 
polynomials are {\em cumulative} in the following sense: if  
$\Z[x_{1},\dots, x_{n}]^{S_{n}}$ is extended to  
$\Z[x_{1},\dots, x_{n}, x_{n+1}]^{S_{n+1}}$, then  
(setting $s_{\lambda}^{(n)}(x):=0$ for $\lambda $ with $l(\lambda )>n$) 
one has \begin{equation} \forall \lambda : \quad  
s_{\lambda }^{(n)}(x_{1},\dots, x_{n}) = 
s_{\lambda }^{(n+1)}(x_{1},\dots, x_{n}, 0)\ . \end{equation}  
In other words: \begin{equation*} 
s_{\lambda}^{(n+1)}(x)=s_{\lambda}^{(n)}(x) + \text{ `non-negative terms 
containing $x_{n+1}$, but no $x_{\nu}$ with $\nu>n+1$'.}  
\end{equation*}  
It is therefore possible to extend the Schur polynomials to {\em Schur 
functions} $s_{\lambda }(x)$, which are homogeneous 
formal power series contained 
in the direct limit \begin{equation*}  \Z[[x]]^{S_{\infty }} =  
\underset{\longleftarrow}{\lim} _{n} \Z[x_{1},\dots, x_{n}]^{S_{n}} 
\end{equation*} such that  
$s_{\lambda }^{(n)}(x)=s_{\lambda }(x_{1},\dots, x_{n}, 0, \dots\ )$. 
Since the Schur polynomials are homogeneous of degree $|\lambda | := 
\lambda _{1} + \dots\ +\lambda_{s}$ the natural grading is not by 
degree but by the number of variables appearing; and cumulativeness 
shows, that for fixed $\lambda $ the complete information about 
all Schur polynomials and the Schur function is contained in the  
{\em graded Schur function}: \begin{equation} 
s_{[\lambda ]}(x):=(s_{\lambda }^{[1]}(x), s_{\lambda }^{[2]}(x),  
s_{\lambda}^{[3]}(x), \dots \ ) 
\end{equation} with {\em $n^{th}$ part} \begin{equation} 
s_{\lambda }^{[n]}(x):= s_{\lambda }^{(n)}(x) - s_{\lambda}^{(n-1)}(x) 
\quad ( s_{\lambda }^{(0)}(x):=0)\ . 
\end{equation} 
 
G.P. Thomas has shown that the graded Schur functions $s_{[\lambda ]}(x)$ 
can be represented by closed formulas, which are very well suited to 
computation; namely \begin{equation} 
s_{[\lambda ]}(x) = \sum_{\zeta \in SYT(\lambda)} B_{\zeta } (x)\ , 
\end{equation} where $SYT(\lambda )$ is the (finite) set of standard 
Young tableaux of shape $\lambda $ and the expressions $B_{\zeta}(x)$,  
which are easily computed for a given $\zeta $, are  
a mixture of multiplication and shift operators applied to the basis 
sequence $x=(x_{1}, x_{2}, x_{3}, \dots\ )$ of variables. 
  
In [W3] we have shown that this approach of Thomas can be extended to 
the 1- and 2-parameter families of  
Hall-Littlewood, Jack, and Macdonald symmetric polynomials, which 
contain Schur polynomials for special choices of parameters. 
In this paper we will introduce graded Schubert functions, which 
extends the Schur case in another direction: 
 
Due to the work of A. Borel (1953), I.N. Bernstein, I.M. Gelfand, and  
S.I. Gelfand (1973), M. Demazure (1973-74), and finally A. Lascoux 
and M.-P. Sch\"utzenberger (mainly 1982-87) the Schubert calculus for 
the cohomology ring of flag manifolds has been shown to have an 
isomorphic realization in terms of polynomials. 
In fact to every finite permutation $\pi$ contained in some $S_{n}$ 
there is associated an in general nonsymmetric Schubert polynomial  
$X_{\pi}\in \Z[x_{1},\dots, x_{n}]$. 
The set of all Schubert polynomials forms a $\Z$-basis of $\Z[x]$ and  
contains the Schur polynomials as special cases, namely, $X_{\pi}$ is 
a Schur polynomial exactly when $\pi$ is a Grassmannian permutation 
$\pi(\lambda ,n)$ (cf. Sec.1 below). More information about the  
Schubert calculus can be found in [Hi] and about Schubert polynomials 
in [LS, M2, M3, W1]. 
 
In Section 1 we will see that the $X_{\pi}$ are cumulative with respect  
to a certain natural embedding of the symmetric groups 
$S_{n}\hookrightarrow S_{n'}$ for $n<n'$ (Theorem 1.1). 
This will allow us to introduce the (graded) Schubert functions $X_{[\pi]}$, 
which generalize (graded) Schur functions. 
 
In Sections 2 and 3 we extend Thomas' formula for graded Schur functions  
(0.4) to the Schubert case (Theorem 3.9). The sets $SYT(\lambda )$  
of standard Young tableaux will be seen to be generalized by the sets 
$R(\pi)$ of {\em reduced sequences for $\pi$}. Recall that $S_{n}$ is 
generated by the elementary transpositions $\sigma _{i}=(i,i+1)$ 
\ ($i=1,\dots, n-1$) subjected to the relations \begin{equation*} 
{\rm (i)}\ \sigma_{i}^{2} = id, \quad  
{\rm (ii)}\ \sigma _{i}\sigma _{i'}=\sigma _{i'}\sigma _{i}\ , \text{ if 
$|i-i'|\geq 2$, and \ \ } 
{\rm (iii)}\ \sigma _{i}\sigma _{i+1} \sigma _{i}= 
            \sigma _{i+1}\sigma _{i} \sigma _{i+1}\ . 
\end{equation*} 
For $\pi=\sigma _{a}:= \sigma _{a_{1}} \dots\ \sigma _{a_{p}}$ the  
sequence $a\equiv a_{1}\dots\ a_{p}$ resp. the word $\sigma _{a}$  
is said to be reduced (for $\pi$) iff the number $p$ is minimal. Then 
$l(\pi):=p$ is called the length of $\pi$. We use the notations 
$R(\pi)$ for the set of reduced sequences for $\pi$, and  
\begin{align} r(\pi)& := |R(\pi)| \ , \\ 
f^{\lambda }& := |SYT(\lambda )|\ .\end{align}  
A basic fact underlying the generalization of Schur functions to 
Schubert functions is that $r(\pi(\lambda ))=f^{\lambda}$, where  
$\pi(\lambda )$ is a Grassmannian permutation associated to $\lambda$. 
This can be proved for example by a simple combinatorial bijection 
between the two sets  $R(\pi(\lambda ))$ and $SYT(\lambda )$ (cf. [W4]). 
 
Moreover, in Section 3 we introduce skew Schubert polynomials and 
functions. 
 
In Section 4 we derive a formula for the number of terms in each 
component of $X_{[\pi]}$, which generalizes the results of [W3, Sec.3] 
in the Schur case, and we recall some important results of I.G. Macdonald, 
which relate reduced words and Schubert polynomials resp. functions. 
Moreover we introduce `hexagon free' and `decomposable' permutations, 
which will simplify in many cases the computation of the numbers $r(\pi)$. 
 
In Section 5 two generalizations of binomial coefficients will be 
discussed: first by the numbers $f^{\lambda }$ and $r(\pi)$ in a 
lattice theoretic context, and second with the help of graded Schubert 
functions. 
  
The final Section 6 begins with a brief survey of what is known about 
the numbers $r(\pi)$. There are explicit formulas in special cases, and 
theoretical results, which relate reduced sequences, 
balanced labelings, Stanley functions, and Schubert polynomials 
([S1, EG, FS, FGRS]), but there is no general formula (see however Rem.6.13).  
We use initial parts of graded Schubert functions to provide new effective
algebraic formulas (Theorems 6.3, 6.5, 6.7) and a combinatorial method 
(Cor.6.11), which enable the determination of the $r(\pi)$'s in general. 
\vspace{20pt} 
 
 
\section{Schubert functions} 
 
We recall some facts about permutations, their codes, and Schubert 
polynomials. For every permutation $\pi\in S_{n}$  the 
{\it Schubert polynomial} $X_{\pi}\in \Z[x_{1}, \dots , x_{n}]$ is defined 
as the result of 
applying a certain $\pi$-dependent sequence of {\it divided differences}  
to the monomial $x_{1}^{n-1} x_{2}^{n-2}\dots\ x_{n}^{0}$. 
The divided differences $\partial_{i}\ 
(i\in \N) $ are defined by $\partial_{i} f= (f-\sigma_{i}(f)) / 
(x_{i}-x_{i+1}) $, where $f$ is an arbitrary function of $x$, and 
the elementary transposition $\sigma _{i}$ acts on $f$ by 
interchanging the variables $x_{i}$ and $x_{i+1}$. 
 
An important elementary device for working with permutations and 
Schubert polynomials is the {\it Lehmer code} of a permutation: for  
$\pi \in S_{n}$ the Lehmer code $L(\pi)$ is an element of the set 
$\llll_{n} := \{ \ \overline{l_{n-1}, \dots , l_{0}} \mid  
0\leq l_{n-\nu} \leq n-\nu ,\ \nu = 1,\dots, n\ \}$ defined by  
$l_{n-\nu} (\pi) := \sharp \{\ j \mid \nu < j ,\ \pi \nu > \pi j\}$ 
for all $\nu \in \{1,\dots, n\}$, 
e.g. $L(361542) = \overline{240210}$ or $L(1257346) = \overline{0023000}$; 
this sets up a bijection between $S_{n}$ and $\llll_{n}$ (cf. [W1]).  
 
A permutation $\pi$ is called {\em Grassmannian} iff there is a partition 
$\lambda\equiv \lambda _{1} \dots\ \lambda_{s}$ and a natural number 
$n\geq l(\lambda )=s$ such that $L(\pi) = 
\overline{0 \dots\ 0\ \lambda _{s}\ \dots\ \lambda _{1}\ 0 \dots\ 0}$ 
with $n-s \geq 0$ zeros on the left and (at least) $\lambda_{1}$ zeros 
on the right. An alternative definition is: $\pi$ is called Grassmannian iff 
$\pi$ has a at most one descent, i.e. there is at most one $i$ with 
$\pi(i)>\pi(i+1)$. Anyway \begin{equation} 
\pi (\lambda , n) : = L^{-1}  
(\overline{0 \dots\ 0\ \lambda _{s}\ \dots\ \lambda _{1}\ 0 \dots\ 0} )\ . 
\end{equation} 
Then a result of fundamental importance is \begin{equation} 
X_{\pi(\lambda , n)} = s_{\lambda }^{(n)}(x)\ ,\end{equation} 
in other words: a Schubert polynomial $X_{\pi}$ is a Schur polynomial 
exactly when $\pi$ is Grassmannian (see [M3] or [W1] for a proof). 
 
The exact number of zeros on the right side in $L( \pi (\lambda , m) )$ 
is irrelevant -- provided we get a well defined Lehmer code --, 
because in general the Schubert polynomials are invariant under  
{\it left embedding} of the symmetric groups: 
the left embedding of $S_{p}$ into $S_{p'}$  
($p < p'$) is given by $\pi \mapsto \pi (1)\dots\ \pi (p)\ p+1\ \dots\ p'$, 
and the invariance of Schubert polynomials as  
$X_{\pi}=X_{\pi (1)\dots\ \pi (p)\ p+1\ \dots\ p'}$. 
 
On the other hand for $q := p' - p > 0$ one has the {\it right embedding} 
of $S_{p}$ into $S_{p'}$ given by \begin{equation} 
\pi \mapsto  1\dots\ q\ \ q_{+} (\pi) := 
1\dots\ q\ \ (\pi (1) + q) \dots\ (\pi (p) + q)\ , 
\end{equation} but this time the corresponding Schubert polynomials 
behave cumulative: 
 
\begin{Thm}  Schubert polynomials are cumulative under right embedding 
of the symmetric groups,  
i.e. let $\pi'$ be the right embedding of a permutation $\pi \in S_{p}$  
into $S_{p'}$ with $q := p' - p > 0$, then \begin{equation} 
X_{\pi'} = X_{\pi} + \text{\rm{ `non-negative terms'}}\ . 
\end{equation}   \end{Thm} 
\begin{proof}  Clearly it suffices to show the assertion for $q=1$. 
Set $\pi' := 1\ 1_{+}(\pi)$ and $\pi'':= 1_{+}(\pi)\ 1$,  
then $\pi' = \pi'' \sigma _{p} \dots\ \sigma _{1}$ 
and repeated use of [W1, Cor.6.8] gives:  
\begin{multline*} 
X_{\pi'} = X_{( \pi'' \sigma _{p} \dots\ \sigma _{2} ) \sigma _{1}} = 
x_{1}^{-1} X_{\pi'' \sigma _{p} \dots\ \sigma _{2}} +  
\text{ `non-negative terms'} = \ \dots\ = \\ 
( x_{1} \dots\ x_{p} )^{-1} X_{\pi''} + \text{ `non-negative terms'}\ . 
\end{multline*}  
Now [W1, Prop. 3.3] says 
$X_{\pi''} = ( x_{1} \dots\ x_{p} ) X_{\pi}$, which proves (1.4). 
\end{proof} 
 
Theorem 1.1 enables the following 
 
\begin{Def}     
Let $\pi \in S_{n}$ be an arbitrary {\it unembedded} permutation, 
i.e. $\pi$ is not left embedded ($\pi (n) \neq n$), and 
$\pi$ is not right embedded ($\pi (1) \neq 1$). Set $\pi^{(0)}:=\pi$ and  
for $m \in \N$ let $\pi^{(m)}:=1 \dots\ m\ m_{+} (\pi)$ the right embedding  
of $\pi$ into $S_{n+m}$. Then the {\em graded Schubert function} 
associated to $\pi$ is \begin{equation} X_{[\pi]} := 
(\ 0 , \dots\ , 0 ,\ X_{\pi^{[0]}}, X_{\pi^{[1]}}, X_{\pi^{[2]}}, \dots \ ) \   
\end{equation} 
with $n-2$ leading zeros and {\em $m^{th}$ part} \begin{equation} 
X_{\pi^{[m]}} := X_{\pi^{(m)}} - X_{\pi^{(m-1)}} 
\quad ( X_{\pi^{(-1)}}:=0)\ . 
\end{equation} 
The {\em Schubert function} associated to $\pi$ is the formal sum  
\begin{equation} \widetilde{X_{\pi}} := \sum_{m\geq 0}  X_{\pi^{[m]}} \ . 
\end{equation} 
\end{Def}  
 
\begin{Rem}      
There are currently four possibilities to define Schubert polynomials:  
(1) the algebraic definition based on divided differences (as indicated 
above), (2) combinatorial rules based on box diagrams  
(similar to Ferrer diagrams, but with movements of boxes instead of 
numberings) (cf. Sec.6 below), (3) a semi-combinatorial rule based 
on reduced words: the BJS-formula due to S.C. Billey, W. Jokusch and  
R.P. Stanley ([FS]) (cf. Sec.2 below), and (4) two algebro-combinatorial
methods, which are consequences of Monk's rule:
the ``transition equation'' method of Lascoux and Sch\"utzenberger
[M3, (4.16)], and the ``ascent-descent'' method introduced in [W1, Sec.6].
 
For the proof of Thm.1.1 we have used the algebraic definition, but it is 
equally possible to proceed from one of the others: the 
cumulativeness of Schubert polynomials follows from the combinatorial  
definition via box diagrams with the same ease, as the cumulativeness  
of Schur polynomials from their combinatorial definition via semistandard  
Young tableaux. (In fact for all $m\in \N$ the box diagrams for the sequence 
of right embeddings $\pi^{(0)}, \dots, \pi^{(m)}$ form an ascending chain 
of principal box diagrams in the K-derived set $\K(\pi^{(m)})$   
(cf. [W2, Thm. 2.7]) ). With regard to the ``ascent-descent'' method (4)
 the result is 
immediate from the natural embedding of the right weak Bruhat order on 
$S_{n}$ into that of $S_{n+1}$ and with regard to the BJS-formula compare  
the proof of Thm.6.8 below. 
\end{Rem}  
 
Note that every finite permutation is of the form $\pi^{(m)}$ for 
some unembedded $\pi$ and a natural number $m$. Therefore every 
Schubert polynomial occurs as the sum of the initial parts of some 
graded Schubert function. For unembedded Grassmannian permutations  
$\pi(\lambda ) := \pi(\lambda,l(\lambda))$ we clearly obtain 
(setting $X_{\pi(\lambda ,m)} = 0$ for $m < l(\lambda )$ ): 
\begin{equation*}  X_{[\pi]} = s_{[\lambda ]}(x) \quad \text{ and  } \quad  
\widetilde{X_{\pi}} = s_{\lambda }(x)\ . 
\end{equation*} 
 
It is important to observe that $X_{\pi^{(m)}}\in \Z[x_{1},\dots, x_{n+m-1}]$ 
does not in general originate from  
$X_{\pi^{(m+1)}}\in \Z[x_{1},\dots, x_{n+m}]$ by setting $x_{n+m}=0$, 
but in general \begin{equation*} X_{\pi^{(m+1)}} \vert_{x_{n+m}=0} =  
X_{\pi^{(m)}} + \text{ `non-negative terms'}\ . 
\end{equation*} 
For example let $\pi=\pi^{(0)}=321$; then: $X_{\pi^{(0)}}=x_{1}^{2} x_{2}$, 
but $\pi^{(1)}=1432$ and $X_{\pi^{(1)}}=  
x_{1}^{2} x_{2} + x_{1} x_{2}^{2} + x_{1}^{2} x_{3} +  
x_{1} x_{2} x_{3} + x_{2}^{2} x_{3}$. This destroys the notion of 
`grading' as introduced in the Schur case, namely grading by the ``number 
of variables". But there is a substitute relying on the recursive 
structure of Schubert polynomials (cf. [W1, Cor.3.6]), which is almost as  
simple: \begin{equation} 
X_{\pi^{(m)}} = 1^{\downarrow}_{-} (X_{\pi^{(m+1)}} \vert_{x_{1}=0})\ , 
\end{equation} where the operator $1^{\downarrow}_{-}$ means: `shift 
all indices of variables by $-1$'. Indeed for the above example one 
computes $1^{\downarrow}_{-} (X_{\pi^{(1)}} \vert_{x_{1}=0}) = 
1^{\downarrow}_{-} (x_{2}^{2} x_{3}) = x_{1}^{2} x_{2} = 
X_{\pi^{(0)}}$. Note that for symmetric polynomials (1.8) is 
equivalent to (0.1). 
\vspace{20pt}

\section{The BJS-formula and the algebra of sequences of polynomials} 
 
Our general task in this section is to establish {\em $\tau Px$-formulas} 
for the graded Schubert functions $X_{[\pi]}$, i.e. to express $X_{[\pi]}$ 
as a $\Z$-linear combination of sequences consisting of the symbols  
$\tau$, $P$ and $x$, which are the shift operator, the geometric 
shift operator, and the multiplication operator, respectively, on the 
the space of sequences of polynomials in a growing number of variables.  
We discuss first the BJS-formula for Schubert polynomials  
found by S.C. Billey, W. Jokusch and R.P. Stanley (cf.[FS]), than 
we introduce the algebra of sequences of polynomials and the above 
mentioned operators, and in the next section we construct the  
$\tau Px$-formulas. 
The BJS-formula is our point of departure, because the divided difference  
definition does not work (see Rem.3.11 below). 
 
Let $\pi\in S_{n}$ be an arbitrary permutation of length $l(\pi)=p$ and 
$R(\pi)$ be the set of reduced sequences for $\pi$. To every 
$a\equiv a_{1}\dots\ a_{p} \in R(\pi)$ we can then associate a set of 
$p$-tuples \begin{equation}   
B(a):=\{ b=b_{p}\dots\ b_{1}\ |\  
n-1\geq b_{p} \geq \dots\ \geq b_{1} \geq 1,\ a_{i}\geq b_{i},\  
a_{i} < a_{i+1} \Lra b_{i+1}> b_{i} \}.  
\end{equation} 
The {\em BJS-formula} now reads: \begin{equation} 
X_{\pi} = \sum_{a \in R(\pi)} \quad \sum_{b \in B(a)} \ x_{b} \ \ \  
( \mbox{ with }  \ x_{b}=x_{b_{1}}\dots\ x_{b_{p}} )\ .\end{equation} 
We define the {\em support of $\pi$} as the set  
$supp \ \pi := \{ a\in R(\pi ) | B(a) \neq \emptyset \}\subset R(\pi)$.  
 
\begin{Rem}   Let $GR(\pi)$ denote the graph with vertices 
$R(\pi)$ and edges $(a,a')$ $:\gdw$ `$a$ can be transformed to $a'$ 
according to the relations (ii) and (iii) of elementary transpositions'. 
$GR(\pi)$ is connected (see e.g. [W1, Prop. 1.2]), but $supp\ \pi$ in 
general is not. It is therefore necessary to compute the whole set 
$R(\pi)$. This can be done conveniently by computing one reduced 
sequence (for example with the method described below) and than using 
relations (ii) and (iii) and the connectedness of $GR(\pi)$. 
\end{Rem}  
 
In [W1, Cor.2.11] it has been shown that for arbitrary $\pi\in S_{n}$ with 
Lehmer code $L(\pi)\equiv \overline{l_{n-1} \dots\ l_{0}}$ 
the sequence $\Phi L(\pi):= \Phi (l_{n-1}) \dots\ \Phi (l_{0})$ with  
\begin{equation}  
\Phi (l_{n-\nu}):= (\nu-1)_{+} (l_{n-\nu} \dots\ 1) =  
(l_{n-\nu}+\nu-1 \dots\ \nu) \ , \text{ if $l_{n-\nu}>0$  }  
\end{equation} 
and $\Phi (l_{n-\nu}):= \emptyset $, if $l_{n-\nu}=0$, is reduced; 
in signs: $\Phi L(\pi)\in R(\pi)$. For example  
$\Phi L(214635)= \Phi (\overline{101200}) = 1 3 54\in R(214635)$. Note that  
$\Omega _{n}:=\Phi L(n \dots\ 1)= \Phi (\overline{n-1 \dots\ 0})$ is given by 
\begin{equation*} \Omega _{n} =  
n-1 \dots\ 1\ \vert\ n-1 \dots\ 2\ \vert\ \dots\ \vert\ n-1 \ , 
\end{equation*} where we have included vertical {\em sectioning bars} 
for clarity. We call 	  \begin{equation} a(\pi):=\Phi L(\pi) 
\end{equation} the {\em canonical reduced sequence of $\pi$}. 
 
For the determination of $B(a)$ it is not necessary to know  
the exact form of $a$, but only the `type' $T(a)$ of $a$, which we will 
introduce next. 
Every reduced word $a\in R(\pi)$ can be written as \begin{equation*} 
a\equiv a_{1} \dots\ a_{p}\equiv A_{k} \dots\ A_{1}\ , 
\end{equation*}  
where $A_{k}, \dots , A_{1}$ ($k\leq p$) are the {\em sections} of 
$a$ defined by \begin{equation} 
a_{i} \text{ and } a_{i+1} \text{ are in the same section }\  : \gdw\ 
a_{i} > a_{i+1} \ . 
\end{equation}  
 
For a reduced sequence $a$ of length $p$ with $k$ sections the {\em type}  
$T(a)$ of $a$ is defined as a sequence of $p$ integers \begin{equation} 
T(a):=t_{1}\dots\ t_{1}\ t_{2}\dots\ t_{2}\ \dots\ t_{k}\dots\ t_{k} 
\equiv \tau _{p} \dots\ \tau _{1}\ , 
\end{equation}  
where the multiplicity of each $t_{\nu}$ is $|A_{\nu}|$, $t_{1}:=a_{p}$, 
and recursively \begin{equation} 
t_{\nu}:=\min \{ \min A_{\nu}, \ t_{\nu-1}-1 \} \ \text{ for $\nu > 1$. } 
\end{equation} 
Note that \begin{equation} 
t_{1} > t_{2} > \dots\ > t_{k} \ \text{ and } \  
\tau _{p}\geq \dots\ \geq \tau _{1}\ . 
\end{equation} 
For example $a=324324$ has length $p=6$ and $k=3$ sections; therefore  
$T(32\vert 432\vert 4)= 4 222 11$. Similarly $T(43\vert 5\vert 61)= 
11 0 (-1)(-1)$, and for $\Omega _{n}\in R(n\dots\ 1)$ one has:\begin{equation} 
T(\Omega _{n}) = \underbrace{n-1}_{1}\ \underbrace{n-2\ n-2}_{2} \dots\ 
\underbrace{2\dots\ 2}_{n-2}\ \underbrace{1\dots\ 1}_{n-1}\ . 
\end{equation} 
Let $b\equiv b_{1}\dots\ b_{s},\ \overline{b}\equiv \overline{b}_{1}\dots\  
\overline{b}_{r}$ be (finite) words in the alphabet $\Z$, then the 
{\em componentwise order} on such words 
(w.r.t. the linear order: `empty space'$< \dots\ < -1< 0< 1< 2< \dots$ ) 
is defined by: $b\leq \overline{b}\ :\gdw \  
b_{\nu}\leq \overline{b_{\nu}}$ for all $\nu\in \N$. 
 
\begin{Lem} For $\pi\in S_{n} $ and $a\in R(\pi)$ one has with the above  
notations: \\ 
a) $T(a)= \max B(a)$ for every $a\in supp\ \pi$; \\ 
b) $a\in supp\ \pi \gdw T(a) \in B(a) \gdw t_{k}(a) \geq 1$; \\ 
c) $a\in supp\ \pi \gdw a \text{ subword of } \Omega _{n}$. 
\end{Lem} 
\begin{proof} a) follows directly from the definitions and implies b),  
which in turn implies c): $a\in supp\ \pi \gdw T(a) \in B(a) \gdw  
\forall \nu: \min A_{k+1-\nu} \geq \nu \gdw  
A_{k+1-\nu}$ is subword of $(n-1) \dots\ \nu \gdw 
a$ is subword of $\Omega _{n}$. 
\end{proof} 
 
Let now $R$ be a commutative ring with unit and  
$x = ( x_{1} , x_{2} , \dots\ )$ a sequence of variables; then  
\begin{equation} 
A\equiv A(R,x) := \left( \ R[x_{1}] ,\ R[x_{1},x_{2}] ,\ 
R[x_{1},x_{2},x_{3}] ,  \  \dots\ \right) \end{equation} 
is a $R$-algebra under componentwise addition and multiplication; 
note that the sequences $X_{[\pi]}$ are elements of $A(\Z,x)$ for all 
(unembedded) $\pi$. 
The $n^{th}$-component of $a\equiv ( a_{1} , a_{2} , \dots\ )\in A$  
is $[a]_{n}:=a_{n}$. The {\em shift operator} $\tau :\  A\lra A$, 
defined by \begin{equation} 						    
\tau (a_{1},a_{2},a_{3}, \dots\ ) := ( 0, a_{1},a_{2}, \dots\ )  
\text{ \  or \ } \forall n:\ [\tau a]_{n+1}:=[a]_{n},\ [\tau a]_{1}:=0\ , 
\end{equation} 
and all its powers $\tau ^{\nu}$ ($\nu\in\N$), $\tau ^{0}:=id$ \ are 
algebra endomorphism of $A$; consequently the same is true for all operators 
$f(\tau ) \in R[\tau ]$ and even $f(\tau ) \in R[[\tau]]$,  
because $[A]_{n}$ is not affected by $\tau ^{\nu}$ with $\nu > n$.  
For $x = ( x_{1} , x_{2} , \dots\ )\in A$ and all $n \in\N$ one has  
$\{\ [\tau ^{\nu} x]_{n}\ |\ \nu \in\N_{0}\ \} 
= \{x_{1}, \dots, x_{n}\} \cup \{0\}$.  
One can calculate as usual in the rings $R[\tau ]$ and $R[[\tau]]$.  
Especially important is the `geometric' shift operator  
\begin{equation} P := \sum_{\nu=0}^{\infty } \tau ^{\nu} \ , \ \  
P \ (a_{1},a_{2},a_{3}, \dots\ ) = (a_{1}, a_{1}+a_{2},  
a_{1}+a_{2}+a_{3}, \dots\ ) \ .\end{equation}  Consequently one has for 
all unembedded $\pi$: \begin{equation} \overline{X_{\pi}}:= P\ X_{[\pi]} = 
(0,\dots,0, \ X_{\pi^{(0)}}, \ X_{\pi^{(1)}}, \ X_{\pi^{(2)}}, \dots\ ) \ , 
\end{equation} 
which justifies our restriction to the graded case of $X_{[\pi]}$. \  
$P$ and $S:=\tau P$ are Baxter operators, 
but because $\tau $ itself is not a Baxter operator we will not 
stress this topic further. 
															    
It is not hard to see (e.g. by induction) that a sequence $a\in A(\Z,x)$  
of the form  \begin{equation} \forall n:\ [a]_{n}=  
\sum_{\substack{n= i_{p} \geq \dots\ \geq i_{1} \geq 1  
\vspace{2pt} \\ i_{\nu}\in D \Rightarrow i_{\nu+1} > i_{\nu} }}  
x_{i_{1}} \dots\ x_{i_{p}}  \end{equation} 
for a fixed subset $D\subset \{1,\dots,p-1\}$  
can be written using the $\tau Px$-formula (or Baxter sequence)  
\begin{equation} B_{p,D}(x) := 
x B_{p-1} \dots\ x B_{1} x \quad \text{ with }  
B_{\nu} \in \{P,S\}\ \text{ and } B_{\nu} = S  \gdw i_{\nu}\in D\ . 
\end{equation}  
 
For the rest of this section (and the next) let $\pi$ be an unembedded 
permutation of $S_{n}$ and $\pi^{(0)}=\pi, \pi^{(1)}, \pi^{(2)}, \dots\ $ 
its sequence of right embeddings. 
 
\begin{Lem} For every unembedded $\pi$ of length $p$ and every  
$m\in \N_{0}$ one has \begin{equation}  
R(\pi^{(m)}) = m_{+} R(\pi):= 
\{m_{+}(a) = a _{1}+m \dots\ a_{p}+m \mid a\in R(\pi) \}\ . 
\end{equation} \end{Lem} 
\begin{proof} We use the above cited result that $\Phi L(\pi') \in 
R(\pi')$  for arbitrary $\pi'$. It follows from Def.1.2 and (2.3) that 
$\Phi L(\pi^{(m)}) = m_{+}(\Phi L(\pi))$, and by the connectedness of the 
graph $GR(\pi)$ that every element $a\in R(\pi)$ can be derived by a chain 
of applications of the relations (ii) and (iii). Shifting the indices 
of the occurring elementary transpositions by $m$ gives for every 
$a\in R(\pi)$ exactly one corresponding $m_{+}(a)\in R(\pi^{(m)})$, 
which proves the assertion. 
\end{proof} 
 
The BJS-formula together with Lemma 2.3 clearly implies \begin{equation} 
x_{\pi^{(m)}} = 
\sum_{a \in R(\pi)} \quad \sum_{b \in B(m_{+}(a))} \ x_{b} \ , 
\end{equation} whence we can write \begin{alignat}{2} 
X_{[\pi]}& \equiv \sum_{a \in R(\pi)} X_{[\pi]}(a) \quad \text{ with } \\ 
X_{[\pi]}(a)& = (0,\dots\ , 0,\ \sum_{b\in B^{[0]}(a)} x_{b},\  
\sum_{b\in B^{[1]}(a)} x_{b},\ \sum_{b\in B^{[2]}(a)} x_{b},\ \dots\ )  
\quad \text{ and } \\ 
B^{[m]}(a)& := B(m_{+}(a)) \setminus B((m-1)_{+}(a))\ , \text{ for $m>0$, }  
B^{[0]}(a) := B((a))\ . 
\end{alignat}  
\vspace{20pt} 
 
\section{$\tau Px$-formulas for graded Schubert functions} 
 
Continuing the discussion of the last section we want to find now  
$\tau Px$-expressions $B_{a}(x)$ for the sequences  
$X_{[\pi]}(a) \in A(\Z,x)$ [(2.18-20)]. We begin with a simple 
 
\begin{Lem}  
For $\pi\in S_{n} $ and $a\in R(\pi)$ with $k$ sections one has: \\ 
a) $T(m_{+}(a))= m_{+}(T(a))$; \\ 
b) $m_{+}(a)\in supp\ \pi^{(m)} \gdw t_{k}(m_{+}(a)) = t_{k}(a)+m \geq 1$; \\ 
c) $m_{+}(a)\in supp\ \pi^{(m)} \gdw  
    m_{+}(a) \text{ subword of } \Omega _{n+m}$. 
\end{Lem} 
\begin{proof} Immediate from the Lemmata 2.2 and 2.3. \end{proof} 
  
\begin{Cor}     
For $\pi\in S_{n} $ and $a\in R(\pi)$ with $k$ sections let 
\begin{equation} 
m_{0}(a):=\min \{m\in \N_{0} \mid m_{+}(a) \in supp\ \pi^{(m)}\}\ , 
\end{equation} which can be computed conveniently by Lemma 3.1 b) as 
\begin{equation} m_{0}(a) = \max \{ 0,\ 1-t_{k}(a) \}\ . 
\end{equation}  
Then the first non-zero term of $X_{[\pi]}(a)$ appears in $[A]_{n-1+m_{0}}$, 
i.e. in the $(n-1+m_{0})$th component of $A\equiv A(\Z,x)$. 
\end{Cor} 
 
For a reduced sequence $a\in R(\pi)$ of length $p$ let  
\begin{equation}  
D(a) := \{ \nu \mid a_{\nu} < a_{\nu+1} ,\ \nu=1,\dots\ , p \} =  
\{\nu \mid \tau _{\nu} > \tau _{\nu+1} ,\ \nu=1,\dots\ , p \}  
\end{equation} be the {\em descent set of $a$} (compare Rem.3.6 below). 
Let in addition $\pi\in S_{n}$ be unembedded; 
then the number \begin{equation} d(a) := n-1-a_{l(\pi)} 
\end{equation}	is called the {\em global delay for $a$} and the 
number \begin{equation} d(\pi) := \min \{ d(a) \mid a\in R(\pi) \} 
\end{equation} the {\em global delay for $\pi$}.  
Before stating a general result we elucidate the significance of the  
number $d(a)$ by the following 
 
\begin{Ex}  
Let $\pi=21543\in S_{5}$ and $a=4341$ a reduced sequence for $\pi$. 
Then $T(a)=1100$,  $m_{0}=1$ by (3.1), i.e. the first von vanishing 
term of $X_{[\pi]}(a)$ occurs in $[A]_{5}$, and the global delay  
is $d(a)=3$ by (3.4).  
Observe that $B(1_{+}(a)) = B(2211) =\{2211\}$ whence from (2.15-19) one has  
$X_{[\pi]}(a)= (0,0,0,0, x_{1}^{2} x_{2}^{2}, \dots\ )$. On the other 
hand it is not hard to see that $X_{[\pi]}(a)$ is ``essentially"  
of the form (2.14) with $p=4$, descend set $D(a)=\{2\}$, and  
$\tau Px$-expression $xPxSxPx = (0, x_{1}^{2} x_{2}^{2}, \dots\ )$, 
which implies $B_{a}(x)=\tau ^{3} xPxSxPx$. In other words: the 
onset of the sequence $xPxSxPx$ is delayed by $\tau ^{3}= \tau^{d(a)}$. 
\end{Ex} 
 
\begin{Prop} Let $\pi\in S_{n}$ be unembedded, $a\in R(\pi)$, and  
$B_{a}(x)$ the $\tau Px$-formula for $X_{[\pi]}(a)$. Then every term in  
$B_{a}(x)$ begins with $\tau ^{d(a)} \dots\ $\ . If moreover $d(\pi) > 0$,  
then the deletion of $d(\pi)$ (but not $d(\pi)+1$) leading zeros from  
$X_{[\pi]}(a)$ yields again an element of $A(\Z,x)$. 
\end{Prop} 
\begin{proof} By Cor.3.2 the first non-zero term in $X_{[\pi]}(a)$ 
appears in $[A]_{n-1+m_{0}}$ with $a_{l(\pi)}+m_{0}$ as the maximal index of 
the occurring variables. On the other hand any $\tau Px$-formula of the  
form $x \dots\ \in A$ contains in 
component $[A_{\nu}]$ the variable $x_{\nu}$ as the variable of 
maximal index. Therefore the $\tau Px$-formula for $X_{[\pi]}(a)$ 
must have the form $\tau ^{d}  \dots\ \ $, with  
$d=(n-1+m_{0}) - (a_{l(\pi)}+m_{0}) = n-1 -a_{l(\pi)}$, which is $d(a)$ 
by (3.4). The second assertion is now immediate. 
\end{proof} 
 
We call sequences of the form (2.14), which are  
expressed by $\tau Px$-formulas of type (2.15), {\em regular} and all other 
{\em singular}. Let $a$ be a reduced sequence of length $p$ with $k$ 
sections; then using (2.6) we define \begin{equation}  
a \text{ is regular } \ :\gdw\  
t_{\nu}(a) - t_{\nu+1}(a) = 1 \text{ for } \nu=1, \dots\ , k-1\ , 
\end{equation} where the $t_{\nu}(a)\equiv t_{\nu}$ are the entries 
of the type $T(a)$, or alternatively \begin{equation}  
a \text{ is regular } \ :\gdw\  
\tau_{\nu+1}(a) - \tau_{\nu}(a) \leq 1 \text{ for } \nu=1, \dots\ , p-1\ , 
\end{equation} where the $\tau_{\nu}(a)\equiv \tau_{\nu}$ are the entries 
of $T(a)$. 
 
\begin{Prop} Let $\pi\in S_{n}$ be unembedded of length $p$ and  
$a\in R(\pi)$ with descent set $D(a)$, and global delay $d(a)$.  
If $a\in R(\pi)$ is regular, then \begin{equation} 
X_{[\pi]}(a) \text{ is regular \quad and  \quad } 
X_{[\pi]}(a) = \tau ^{d(a)} B_{p, D(a)}(x)\ . \end{equation}  
For a partition $\lambda \equiv \lambda _{1} \dots\ \lambda _{s}$ and 
its associated unembedded Grassmannian permutation $\pi(\lambda)$  
every $a\in R(\pi(\lambda))$ is regular, the global delay for 
$\pi(\lambda )$ is $s-1$, and:  
\begin{equation} X_{[\pi(\lambda)]} = \tau ^{s-1} 
\sum_{a\in R(\pi(\lambda))}  B_{p, D(a)} (x) 
\end{equation} in accordance with {\rm (0.4)} (see Rem.3.6 below). 
\end{Prop} 
\begin{proof} Comparison between the summation in (2.15) and the 
definition (3.6-7) yields (3.8). By the definition of the unembedded  
Grassmannian permutation [ (1.1) with $n=l(\lambda )=s$ ] one sees that  
$\pi(\lambda )$ is an element of $S_{\lambda _{1}+s}$. Moreover 
(2.3) shows that the number $a_{p}$ with $p=|\lambda|$ of the reduced 
sequence $a=\Phi L(\pi(\lambda ))\in R(\pi(\lambda ))$ is  
$a_{p}=\lambda_{1}$. But by the results of [W4] (see Rem.3.6 below) 
every $a\in R(\pi(\lambda ))$ then ends with $a_{p}=\lambda _{1}$, 
and therefore we have proved $d(\pi) = \lambda _{1} +s -1 - \lambda_{1} 
= s-1$. 
The term wise equality (except for the global delay) between  
(3.9) and (0.4) yields the regularity of all $a\in R(\pi(\lambda))$. 
\end{proof} 
 
\begin{Rem} For any partition $\lambda$ we have established in [W4]  
a natural combinatorial bijection between the set $R(\pi(\lambda))$ of  
reduced words of the unembedded Grassmannian permutation $\pi(\lambda )$  
associated to $\lambda $ and the set $SYT(\lambda)$ 
of standard Young tableaux of shape $\lambda $.  Under this bijection  
every set $D(a)$ is mapped in fact to the corresponding descent set  
$D(\zeta )$ of a standard Young tableaux $\zeta $ (cf. [W3]) thus  
justifying the notion `descent set' for $D(a)$. 
\end{Rem} 
 
It remains to find the $\tau Px$-expressions $X_{[\pi]}(a)$ for non regular  
$a$. In view of the above proposition the following definition seems natural: 
 
Let $T(a)$ be the type of an arbitrary $a$ with $k$ sections and 
subdivide $T(a)$ into $h\leq k$ parts $T(a)\equiv T_{h} \dots\ T_{1}$ 
according to the condition: \begin{equation}	  
t_{\nu} \text{ and } t_{\nu+1} \text{ are in the same part }\   
: \gdw t_{\nu} - t_{\nu+1} = 1\ . 
\end{equation} Then the parts $T_{h}, \dots, T_{1}$ are called the  
{\em regular parts of $T(a)$}. As an example consider $a=14356$: 
it has length $p=6$, the type $T(a)=65331$ has $k=4$ sections, and 
the $h=3$ regular parts $T_{3}=65, \ T_{2}=33, \ T_{1}=1$. 
Of course one has: 
$a$ is regular iff $T(a)$ has exactly one regular part.  
 
As a convenient notation we introduce moreover the {\em complement}  
$C(a)$ of the type $T(a)$ for any reduced sequence $a$ of length $p$ by  
\begin{equation} C(a)\equiv c_{p} \dots\ c_{1}, \ \text{ with }  
c_{\nu}:= \tau _{p} - \tau _{\nu} \ \text{ for } \nu=1,\dots, p \ . 
\end{equation} For example $a=14356$ has type $T(a)=65331$ and  
complement $C(a)= 01335$. 
 
In front of Lemma 2.2 we have already described the componentwise order 
on the set of all finite words over $\Z$. Below we will use this  
componentwise order restricted to the sets \begin{equation} 
W_{p,D} := \{ i\equiv i_{p} \dots\ i_{1} \mid  
i_{p}\geq \dots\ \geq i_{1},\ \nu\in D \Lra i_{\nu+1} > i_{\nu} \} 
\end{equation} where $p$ is a natural number and $D$ a subset of 
$\{1,\dots, p-1 \}$. Define \begin{equation} 
\forall i\in W_{p,D}:\quad \overline{i} := 
\min \{ h\in W_{p,D} \mid i\leq h,\ h \text{ regular } \}\ ; 
\end{equation}  
$\overline{i}$ is called the {\em regular supremum of $i$}. 
Furthermore for $a\equiv a_{1}\dots\ a_{p}$,  
$T(a)\equiv \tau _{p}\dots\ \tau _{1}$, and every $l$ with $1\leq l\leq p$ 
let \begin{equation} T^{+}(l,a):= \tau _{p}\dots\ \tau _{l+1}  
\quad \text{ and } \quad T^{-}(l,a):= \tau _{l}\dots\ \tau _{1}  
\end{equation}  
Assume that $T(a)$ has $h$ regular parts and let  
$p=j_{h}> \dots\ > j_{1}\geq 1$ be the indices of the 
leftmost entries in each regular part $T_{h}, \dots\ , T_{1}$, 
i.e. $T_{j_{\nu}}=\tau_{j_{\nu}} \dots\ $ . Then we define for  
$\nu=1,\dots , h$ (with (3.3), (3.12-14)): 
\begin{multline} 
W^{+}(j_{\nu},a) := \\ 
 \{ i_{p}\dots\ i_{j_{\nu}+1}\in W_{p-j_{\nu}, D(T^{+}(j_{\nu},a))} \mid  
i_{j_{\nu}+1}>\tau _{j_{\nu}} \text{ and }  
i_{j_{s}}\leq \tau _{j_{s}}-1 \text{ for } s=\nu+1, \dots, h \} \ ,  
\end{multline}  \begin{equation}  
W^{-}(j_{\nu},a) :=  
\{ i_{j_{\nu}}\dots\ i_{1}\in W_{j_{\nu}, D(T^{-}(j_{\nu},a))} \mid  
i_{j_{\nu}}\dots\ i_{1} \nleq T^{-}(j_{\nu},a), \  
i_{j_{\nu}}\dots\ i_{1} \leq  \overline{T^{-}(j_{\nu},a)} \} \ . 
\end{equation} 
Before proceeding to the general description of how to set up the 
$\tau Px$-expressions $B_{a}(x)$ for arbitrary reduced sequences $a$,  
it will be helpful to go through some examples: 
 
\begin{Ex}  
Let $\pi=21543\in S_{5}$ and $a=1434$ a reduced sequence for $\pi$. 
Then $T(a)=4331$,  $C(a)=0113$, $m_{0}=0$, and global delay $d(a)=0$.  
By the definition of $B(a)$ resp. $B^{[m]}(a)$ the sum in $[A]_{n-1+m}$  
is over all 4-tuples $i\equiv i_{4} i_{3} i_{2} i_{1}$  
with $n-1+m=:r \geq  i_{4} > i_{3} \geq i_{2} >i_{1} \geq 1$,  
$r-1\geq i_{3}\geq i_{2}$ (automatically), $r-3 \geq i_{1}$. Moreover 
at least of the conditions: $i_{4} =r,\ i_{3}=r-1,\ i_{2}=r-1, 
i_{1}=r-3$ must be fulfilled; otherwise the 4-tuple $i$ would be contained  
in some prior component $[A]_{n-1+\nu}$ with $0\leq \nu < m$. 
 
Assume first that $i_{4}=r$. Then using $r-2 \geq i_{1}$ instead of  
$r-3 \geq i_{1}$ gives a regular sequence with $p=4$, $D=\{1,3\}$, 
and $\tau Px$-expression $xSxPxSx$, which has to be diminished in 
every part of $[A]_{r}$ by the term $x_{r} x_{r-1}^{2} x_{r-2}$. 
Hence in case of $i_{4}=4$ we get the expression  
$xSxPxSx - x\tau x^{2}\tau x$. Observe that  
$xSxPxSx$ alone yields $(0,0, x_{3} x_{2}^{2} x_{1}, x_{4} x_{2}^{2} x_{1} 
+ x_{4} x_{3} x_{2} x_{1} + x_{4} x_{3}^{2} x_{1} + x_{4} x_{3}^{2} x_{2}, 
\dots\ )$, which is diminished by  
$(0,0, x_{3} x_{2}^{2} x_{1}, x_{4} x_{3}^{2} x_{2}, \dots\ )$, and 
in fact $X_{[\pi]}(a)$ has its first non vanishing term in $[A]_{4}$. 
 
Assume now that $i_{3}=r-1$ or $i_{2}=r-1$. This implies $i_{4}=r$, 
which is already done. In general only the first place 
of a regular part in some $T(a)$ gives a contribution (here 
$T_{2}=433$ and $T_{1}=1$). Therefore it remains to study the case 
$i_{1}=r-3$ under the condition that $i_{4}\leq r-1$. But this forces 
of course $i_{4}=r-1$, $i_{3}=i_{2}=r-2$, and hence a term  
$\tau x\tau x^{2}\tau x$ in $X_{[\pi]}(a)$. Observe that in deed  
$x_{3} x_{2}^{2} x_{1}$ has to occur in $[A]_{4}$, and not in $[A]_{3}$. 
In total we have \begin{equation*} 
X_{[21543]}(1434) = (xSxPxSx - x\tau x^{2}\tau x)+\tau x\tau x^{2}\tau x\ . 
\end{equation*} 
\end{Ex} 
 
\begin{Ex}  
Let $\pi=2153674\in S_{7}$ and $a=14356$ a reduced sequence for $\pi$. 
Then $T(a)=65331$,  $C(a)=011335$, $m_{0}=0$, $d(a)=0$, $D(a)=\{1,3,4\}$,  
and the regular parts of $T(a)$ are $T_{3}=65, \ T_{2}=33, \ T_{1}=1$. 
By the definition of $B(a)$ resp. $B^{[m]}(a)$ the sum in $[A]_{n-1+m}$  
is over all 5-tuples $i\equiv i_{5} i_{4} i_{3} i_{2} i_{1}$  
with $n-1+m=:r \geq  i_{5} > i_{4} > i_{3} \geq i_{2} >i_{1} \geq 1$,  
$r-1 \geq i_{4}$, $r-3\geq i_{3}\geq i_{2}$, $r-5 \geq i_{1}$, and at 
least one of the conditions: $i_{5} =r,\ i_{4}=r-1,\ i_{3}=i_{2}=r-3, 
i_{1}=r-5$ has to be fulfilled.  
    
Assume first that $i_{5}=r$. Then the regular supremum [(3.13)] of $T(a)$ 
in $W_{5,D(a)}$ is $\overline{T(a)}=65443$. This yields a regular expression 
in $A$ with $\tau Px$-formula $xSxSxPxSx$, which has to be diminished by 
singular expressions corresponding to the words $65443$, $65442$, $65441$,  
$65432$, $65431$, $65421$, $65332$, $64332 \in W_{5,D(a)}$, i.e.  
$x\tau x\tau x^{2}\tau x$, $x\tau x\tau x^{2}\tau^{2}x$,  
$x\tau x\tau x^{2}\tau^{3} x$, $x\tau x\tau x\tau x\tau x$,  
$x\tau x\tau x\tau x\tau^{2} x$, $x\tau x\tau x\tau^{2} x\tau x$,  
$x\tau x\tau^{2} x^{2} \tau x$, $x\tau^{2} x\tau x^{2} \tau x$. 
 
$i_{4}=r-1$ implies $i_{5}=r$, which is done already, but  
$i_{3}=r-3$ with $i_{5}\leq r-1$ yields:  
$r-1 = i_{5} > i_{4} > i_{3}=r-3$, whence $i_{4}=r-2$, and  
$r-3 =i_{3} \geq i_{2} >i_{1} \geq 1$. Therefore we have  
the $\tau Px$-expression: $\tau x\tau x\tau [\dots]$, where `$\dots$' 
is determined by arguments similar to the case $i_{5}=r$ or Ex.3.7 
above as $xPxSx -x^{2}\tau x$. 
 
$i_{2}=r-3$ implies $i_{3}=r-3$, which is done already, but  
$i_{1}=r-5$ with $i_{5}\leq r-1$ and $i_{3}\leq r-4$ yields:  
$r-1 = i_{5} > i_{4} > r-4 \geq i_{3} \geq i_{2} > i_{1} = r-5$,  
whence $i_{3}=i_{2}= r-4$, and we have to consider singular expressions  
corresponding to the words $54221$, $53221$, $43221 \in W_{5,D(a)}$, i.e.  
$\tau x\tau x\tau^{2} x^{2}\tau x$, $\tau x\tau^{2} x\tau x^{2}\tau x$,  
$\tau^{2} x\tau x\tau x^{2}\tau x$. 
  
In total we have \begin{multline*} 
X_{[2153674]}(14356) = xSxSxPxSx -  
\left( x\tau x\tau x^{2}\tau x + x\tau x\tau x^{2}\tau^{2}x + 
x\tau x\tau x^{2}\tau^{3} x \right. \\ \left. + x\tau x\tau x\tau x\tau x +  
x\tau x\tau x\tau x\tau^{2} x + x\tau x\tau x\tau^{2} x\tau x + 
x\tau x\tau^{2} x^{2} \tau x + x\tau^{2} x\tau x^{2} \tau x 
\right) \\ + \tau x\tau x\tau (xPxSx -x^{2}\tau x) + 
\left( \tau x\tau x\tau^{2} x^{2}\tau x + \tau x\tau^{2} x\tau x^{2}\tau x 
+ \tau^{2} x\tau x\tau x^{2}\tau x \right)\ . 
\end{multline*} 
\end{Ex} \vspace{11pt} 
 
\begin{Thm}  
{\em (Computation of the $\tau Px$-formulas for graded Schubert 
functions $X_{[\pi]}$ )}  
For an unembedded $\pi\in S_{n}$ of length $p$ one computes first 
the set of reduced sequences $R(\pi)$, e.g. with the help of {\rm (2.3)}, 
the relations {\rm (ii)} and {\rm (iii)} for elementary transpositions,  
and the connectivity of $GR(\pi)$ [Rem.2.1]. 
 
For fixed $a\in R(\pi)$ let $B_{a}(x)$ be the $\tau Px$-expression for  
the sequence $X_{[\pi]}(a)$ {\rm [(2.18-20)]}. Calculate $T(a)$  
{\rm [(2.6-7)]}, $d(a)$ {\rm [(3.4)]}, the regular parts of $T(a)$  
{\rm [(3.10)]}, and with the 
help of the indices $j_{h}, \dots\ j_{1}$, which are the leftmost entries  
in each regular part $T_{h}, \dots\ , T_{1}$ of $T(a)$, the sets  
$W^{+}(j_{\nu},a)$ and $W^{-}(j_{\nu},a)$ {\rm [(3.15-16)]}. Then  
\begin{equation} 
B_{a}(x) = \tau^{d(a)} \sum_{\nu=1}^{h} B_{a, \nu}(x) \equiv  
\tau^{d(a)} \sum_{\nu=1}^{h} \alpha _{a,\nu}(x) \ \beta _{a, \nu}(x)\ , 
\end{equation} where $\alpha_{a, \nu}(x)$ and $\beta _{a, \nu}(x)$ 
are given by \begin{align} 
\alpha_{a, \nu}(x)& = \sum_{i_{p}\dots\ i_{j_{\nu}+1} \in W^{+}(j_{\nu},a)} 
\tau^{\tau_{p}(a)-i_{p}} x\tau^{i_{p}-i_{p-1}} x\dots\  
                      x\tau^{i_{j_{\nu}+1}-\tau_{j_{\nu}}(a) }\ , \\ 
\beta_{a, \nu}(x)& = B_{j_{\nu}, D(T^{-}(j_{\nu}, a))} (x ) - 
\sum_{i_{j_{\nu}}\dots\ i_{1} \in W^{-}(j_{\nu},a)} 
x\tau^{i_{j_{\nu}}-i_{j_{\nu}-1}} x\dots\ x\tau^{i_{2}-i_{1}}x \ . 
\end{align} 
\end{Thm} 
\begin{proof} Assuming that the set $R(\pi)$ and the types are 
already computed we are concerned with the computation of the $B_{a}(x)$  
for fixed $a\in R(\pi)$. In case of 
regular $a$ [(3.6-7)] one has: $h=1$, $j_{1}=p$, $W^{+}(p,a)=\emptyset$, 
$T^{-}(p,a)=T(a)$, $T(a)=\overline{T(a)} \Lra W^{-}(p,a)=\emptyset$, 
and finally $B_{a}(x)=\tau ^{d(a)} B_{p, D(a)} (x )$ in accordance 
with Prop.3.5 . Note that the global delay $d(a)$ is already handled  
by Prop.3.4 for every $a\in R(\pi)$. We have therefore to show the  
validity of formulas (3.17-19) in case of $h\geq 2$. 
 
Since $\sum_{b\in B^{[m]}(a)} x_{b}$ is the part of $X_{[\pi]}(a)$ in  
$[A]_{r}$ with $r:=n-1+m$, the task is to describe the sets  
$B^{[m]}(a)$ [(2.20)] for all $m\geq 0$ simultaneously.  
Using $C(a)$ [(3.11)] and $D(a)$ [(3.3)] the set $B(m_{+}(a))$ is given 
by \begin{equation*} 
B(m_{+}(a)) = \{  b_{p}\dots\ b_{1}\in W_{p, D(a))} \mid \forall \nu= 
1 \dots\ p:\ b_{\nu} \leq r-c_{\nu} \}\ . 
\end{equation*} 
For $B^{[m]}(a)$ we have to consider only those $p$-tuples 
of $B(m_{+}(a))$, which are not contained in $B((m-1)_{+}(a))$,  
i.e. for at least one $\nu\in \{1,\dots, p\}$ we require  
$b_{\nu} = r-c_{\nu}$. But this has to be assured only for  
$\nu\in \{j_{h}, \dots\ j_{1}\}$: for simplicity we consider $\nu=1$ 
resp. the regular part $T_{1}(a)= \tau _{j_{1}} \dots\ \tau _{1}$ and  
$s\in \{1,\dots, j_{1}-1\}$; if $\tau _{s}=r-c_{s}$, then from 
$T_{1}(a)\in W_{j_{1}, D(T_{1}(a))}$, regularity of $T_{1}(a)$, and 
$\tau _{j_{1}}\leq r-c_{j_{1}}$ it follows that $\tau_{j_{1}}=r-c_{j_{1}}$. 
In other words the case of $\tau _{s}=r-c_{s}$ is identical to the case 
of $\tau_{j_{1}}=r-c_{j_{1}}$. 
 
Fix some $\nu\in \{j_{h}, \dots\ j_{1}\}$ and let $B^{[m]}_{\nu}(a)$ 
be the set of all $b_{p}\dots\ b_{1}\in B(m_{+}(a))$ with  
$b_{j_{\nu}}=r-c_{j_{\nu}}$ and $b_{j_{s}}\leq r-c_{j_{s}}-1$  
for $s=\nu+1, \dots, h$. By the preceding discussion 
$B^{[m]}_{\nu}(a)\subset B^{[m]}(a)$,  
$\bigcup_{\nu=1}^{h} B^{[m]}_{\nu}(a) =B^{[m]}_{\nu}(a)$, and by 
definition $B^{[m]}_{\nu}(a)\cap B^{[m]}_{\mu}(a)=\emptyset $ for 
every $\nu$ and $\mu>\nu$, i.e. \begin{equation*} 
B^{[m]}(a) \text{ is the disjoint union of the } B^{[m]}_{\nu}(a)\ . 
\end{equation*} 
The $\tau Px$-expression $B_{a}(x)$ for the sequence $X_{[\pi]}(a)$  
is therefore the sum of the $\tau Px$-expressions $B_{a,\nu}(x)$  
($\nu=1,\dots,h$) for the sequences \begin{equation*} 
(0,\dots,0, \sum_{b\in B^{[0]}_{\nu}(a)} x_{b},	 
\sum_{b\in B^{[1]}_{\nu}(a)} x_{b}, \dots\ \ )\ . 
\end{equation*} 
From the definition of $B^{[m]}_{\nu}(a)$ and taking 
into account that $b_{j_{\nu}+1}> b_{j_{\nu}}=r-c_{j_{\nu}}$ it is 
easily seen that the `translations' of $W^{+}(j_{\nu},a)$ by $m_{+}$  
yield the first $p-j_{\nu}$ entries $b_{p}\dots\ b_{j_{\nu}+1}$ of the  
$b\in B^{[m]}_{\nu}(a)$. Thus every $(p-j_{\nu})$-tuple  
$i_{p}\dots\ i_{j_{\nu}+1}$ of $W^{+}(j_{\nu},a)$ yields a corresponding 
singular expression, the sum of which gives $\alpha_{a, \nu}(x)$ 
as described by (3.18). 
 
For the remaining part $b_{j_{\nu}}\dots\ b_{1}$ of the  
$b\in B^{[m]}_{\nu}(a)$ observe that  
$r-c_{j_{\nu}}=b_{j_{\nu}} \geq \dots\ \geq b_{1}\geq 1$ and  
$b_{j_{\nu}-1}\leq r-c_{j_{\nu}-1}, \dots, b_{1}\leq r-c_{1}$.  
The $(j_{\nu})$-tuple $r-c_{j_{\nu}} \dots\ r-c_{1}$ giving these `upper 
bounds' is obtained by `translation' of $T^{-}(j_{\nu},a)$ by $m_{+}$. 
Taking therefore the regular supremum $\overline{T^{-}(j_{\nu},a)}$  
of $T^{-}(j_{\nu},a)$ gives the 
regular $\tau Px$-formula $B_{j_{\nu}, D(T^{-}(j_{\nu}, a))} (x )$, 
which includes all terms $x_{b}$ for the $b\in B^{[m]}_{\nu}(a)$ in 
every component $[A]_{r}$. But in general this is too much, and 
therefore singular terms corresponding to all those 
$i_{j_{\nu}}\dots\ i_{1}\in W_{j_{\nu}, D(T^{-}(j_{\nu},a))}$, which are 
less or equal (in componentwise order) to  
$\overline{T^{-}(j_{\nu},a)}$ but not less or equal to  
$T^{-}(j_{\nu},a)$ have to be subtracted.  
(Note that $i_{j_{\nu}}(a)=\tau_{j_{\nu}}(a)$ for all  
$i_{j_{\nu}}\dots\ i_{1} \in W^{-}(j_{\nu},a)$.) 
In total this yields $\beta_{a,\nu}(x)$ as defined by (3.20). 
\end{proof} 
 
\begin{Rem} Note that the sets (3.15-16) and formulas (3.18-19) are unchanged 
if one replaces $T(a)$ by some $T(m_{+}(a))$. It is therefore 
convenient always to use $\overline{T}(a):=T(m_{+}(a))$ with $m=m_{0}$, 
because then $\overline{\tau}_{1}=1$ : in fact this is true for 
$m_{0}>0$ by Lemma 3.1, and \begin{equation} 
m_{0} = 0 \Lra \tau _{1}(a)=1\ , 
\end{equation} because: `$\pi$ unembedded' $\Lra\ `\pi(1)\neq 1'\ \Lra$ 
`$1$ occurs in $a$' $\Lra$ (3.20) by definition of the 
type $T(a)$.  
\end{Rem} 
 
\begin{Rem} The algebraic definition of Schubert polynomials relying on 
divided differences is not suitable to build up $\tau Px$-formulas: 
 
It would be necessary to have a 
`well behaved' extension of the operators $\partial_{i} $ to $A(\Z,x)$. 
For an unembedded $\pi \in S_{n}$ the $m^{th}$ part $X_{\pi^{[m]}}$ 
of the graded Schubert function and the Schubert polynomial 
$X_{\pi^{(m)}}=[\overline{X_{\pi}} ]_{n-1+m}$ (recall (2.4)) are elements 
of $\Z[x_{1},\dots,x_{n-1+m}]$. Now `well behaved' should clearly mean  
that the extended operator $\overline{\partial_{i ,\pi} }$ fulfills 
$\overline{\partial_{i ,\pi} } \quad  \overline{X_{\pi}} =  
\overline{ \partial_{i} X_{\pi}}$. This is achieved, if we 
define: \begin{align*}  
[ \overline{\partial_{i ,\pi}} \quad \overline{X_{\pi}} ]_{r} :=  
\partial_{i+r-n+1} \ [ \overline{X_{\pi}}]_{r}\ ,&  
\text{ if $r\geq n-1$, and }\\ 
[ \overline{\partial_{i ,\pi}} \quad \overline{X_{\pi}} ]_{r} := 0\ ,& 
\text{ if $1\leq r < n-1$. } 
\end{align*} 
Now one has for example  
$\partial_{1} X_{321}=\partial_{1} x_{1}^{2} x_{2} = x_{1} x_{2} =X_{231}$. 
The general approach in this section shows that 
$\overline{X_{321}} = PxSxPx + SxPxSx$ and $\overline{X_{231}} = PxSx$,  
whence $\overline{\partial_{1} } ( Px\tau PxPx +  
\tau PxPx\tau Px ) = Px \tau Px$. Since the term $\tau PxPx\tau Px $ 
does not contribute to $[\overline{X_{321}}]_{2}= X_{321}$, we would 
expect it to be of minor importance in  
$\overline{\partial_{1} }\ \overline{X_{321}}$, too, but the contrary  
is the case: an tedious but elementary 
computation shows that $\overline{\partial_{1} } (PxSxPx)= x\tau x$ and  
$\overline{\partial_{1} } (SxPxSx) = PxSx -x\tau x$. This unforeseen 
behavior of $\overline{\partial_{1} }$ in our example clearly shows that we 
can not hope to build up a neat calculus of $\tau Px$-formulas on the 
basis of extended divided differences. 
\end{Rem} 
 
The $\tau Px$-formulas for the graded Schubert functions 
allow the introduction and easy computation of (graded) {\bf skew 
Schubert functions} and therefore {\bf skew Schubert polynomials}, 
which in the Grassmannian case specialize to skew Schur functions and 
polynomials: 
 
Let $\pi$ be an unembedded permutation of length $p$ and $\mu$  
an unembedded permutation of length $q\leq p$, which is less than or 
equal to $\pi$ in right weak Bruhat order. For our purpose this means that  
every reduced sequence $a_{1} \dots a_{q}\in R(\mu)$ can be extended 
by suitable numbers $a_{q+1}, \dots, a_{p}$ to a reduced sequence  
$a_{1} \dots a_{q}\ a_{q+1} \dots a_{p}$ of $\pi$. It is therefore 
possible to define \begin{equation}  
R(\pi/\mu) := \{ a\equiv a_{1} \dots a_{p} \in R(\pi) \mid  
a_{1} \dots a_{q} \in R(\mu) \}\ . 
\end{equation}  
Every term in the $\tau Px$-formula for $X_{[\pi]}$ is of the form  
\begin{equation*} x f_{p-1} x \dots x f_{1} x \ \text{ with }  
f_{p-1}, \dots , f_{1} \in \Z[[\tau ]]\ . 
\end{equation*} 
For such an expression and $q\in \N$ we define \begin{equation*} 
(x f_{p-1} x \dots x f_{1} x) \downharpoonright q :=  
x f_{p-1} x \dots x f_{q+1} x\ , 
\end{equation*} where of course  
$(x f_{p-1} x \dots x f_{1} x) \downharpoonright (p-1)=x$ and  
$(x f_{p-1} x \dots x f_{1} x) \downharpoonright q =0$ for $q\geq p$. 
With this not(at)ions we define the graded skew Schubert function 
associated to the pair $(\pi ,\mu )$ to be \begin{equation} 
X_{[\pi /\mu]} := \sum_{a\in R(\pi/\mu)} B_{a}(x)\downharpoonright l(\mu)\ . 
\end{equation} 
 
\begin{Prop} Let $\lambda, \mu $ be partitions with $\mu\subset \lambda $, 
i.e. the Ferrer diagram of $\mu$ is included in that of $\lambda $, 
and $\pi(\lambda )$, $\pi(\mu)$ the associated unembedded Grassmannian 
permutations. Then $R(\pi(\lambda )/\pi(\mu))$ is well defined, and  
$X_{[\pi(\lambda )/\pi(\mu)]}$ equals  
$\tau ^{d(\pi(\lambda ))} s_{[\lambda/\mu]}(x)$, 
the graded skew Schur function associated to the skew partition  
$\lambda/\mu $ (shifted by $\tau ^{d(\pi(\lambda ))}$). 
\end{Prop} 
\begin{proof} (Sketch)  
Recall from Prop.3.5 or (3.9) that $X_{[\pi(\lambda)]} =  
\tau ^{d(\pi)} \sum_{a\in R(\pi(\lambda))} B_{p, D(a)} (x)$. For  
$R(\pi(\lambda )/\pi(\mu))$ to be well defined it is necessary and 
sufficient that every reduced sequence of $\pi(\mu)$ is contained as 
an initial segment of a reduced sequence of $\pi(\lambda )$. But this  
is immediate from the combinatorial bijection between the sets 
$R(\pi(\lambda))$ and $SYT(\lambda)$ of standard Young tableaux of shape  
$\lambda $ set up in [W4], and the obvious fact that the inclusion 
of the shapes $\mu \subset \lambda$ implies the inclusion  
$SYT(\mu)\subset SYT(\lambda )$ of standard Young diagrams. Finally 
it has been shown in [W3, Sec.2] how the $\tau Px$-formulas of the 
graded skew Schur functions $s_{[\lambda/\mu]}(x)$ can be deduced 
from the $\tau Px$-formula of $s_{[\lambda]}(x)$, and an easy comparison 
with the Schubert case yields that the latter is in fact a 
generalization of the former. 
\end{proof} 
\vspace{20pt} 

\section{The number of terms of graded Schubert functions} 
 
In this section let $\pi\in S_{n}$ be an unembedded permutation and  
$a\in R(\pi)$. In view of 
the cumulativeness of Schubert polynomials and the $\tau Px$-formulas 
for graded Schubert functions it is natural to investigate the sequences  
$\pi^{\sharp}(a):= (\pi_{1}^{\sharp}(a),\ \pi_{2}^{\sharp}(a) ,\ \dots\ )$ 
of numbers $\pi_{r}^{\sharp}(a):= |B^{[r-n+1]}(a)|$, which is the number of  
terms in each component of the sequence $X_{[\pi]}(a)$ [(2.19-20)]. 
Obviously one has \begin{equation} \pi^{\sharp}(a):=  
B(a)({\bf 1})\ \text{ \ \ with \ } \ {\bf 1}=(1,1,\dots) \ .\end{equation}  
Since all factors $x={\bf 1}$ except the rightmost act as the 
identity automorphism on $A\equiv A(\Z,x)$, they can be neglected. 
Moreover shift operators in $R[[\tau ]]$ commute and therefore every 
term in $B_{a}({\bf 1})$ can be written in the `normal form'  
$\tau^{K} P^{N}({\bf 1})$, where $N$ is the number of symbols $P$ or 
$S$ occurring and $K$ is the sum of exponents of the $\tau $'s 
occurring outside the $P$'s.  
In [W3, (3.3)] it has been shown that $P^{N}({\bf 1})=\binom{r+N-1}{N}$, 
whence \begin{equation} \tau ^{K} P^{N}({\bf 1})=\binom{r-K+N-1}{N} \ . 
\end{equation}  
For example from Ex.3.7 one concludes 
\begin{multline*} 21543^{\sharp}(1434) = B_{1434}({\bf 1}) = 
(\tau ^{2}P^{3} {\bf 1} -\tau^{2} {\bf 1}) +\tau ^{3} {\bf 1}  
= \binom{r}{3} - (0,0,1,0,0,\dots\ ) 
\end{multline*} and from Ex.3.8 
\begin{multline*} 2153674^{\sharp}(14356) = B_{14356}({\bf 1}) = 
\tau ^{3}P^{4} {\bf 1} -(\tau^{3}+ 4\tau ^{4} +3\tau ^{5}){\bf 1} + 
\tau ^{3} (\tau P^{2} -\tau ){\bf 1} +3\tau ^{5}{\bf 1} \\ 
= \binom{r}{4} +\binom{r-3}{2} - (0,0,0,-1,-6,-6, \dots\ )\ . 
\end{multline*} 
Summing up all sequences $\pi^{\sharp}(a)$ gives \begin{equation} 
\pi^{\sharp}:= \sum_{a\in R(\pi)} \pi^{\sharp}(a) \equiv  
(\pi_{1}^{\sharp},\ \pi_{2}^{\sharp} ,\ \dots\ )\ , 
\end{equation}											  
where $\pi_{r}^{\sharp} = |X_{\pi^{[r-n+1]}}|$ by (2.18) and (1.5-6). 
Of course \begin{equation}  
\pi^{\sharp} = X_{[\pi]}({\bf 1})\ , \end{equation}  
and as we will see below the tedious computation of $\pi^{\sharp}$ via  
the $\pi^{\sharp}(a)$ and their $\tau Px$-formulas can be simplified 
very much. 
 
By (2.13) the sequence $X_{[\pi]}({\bf 1})$ is clearly known iff one 
knows the sequence \begin{equation} 
(s_{\pi^{(0)}}, s_{\pi^{(1)}}, s_{\pi^{(3)}}, \dots\ )\ 
\text{ with } s_{\pi^{(m)}} := X_{\pi^{(m)}} (1,\dots, 1)\ , 
\end{equation} i.e. $s_{\pi^{(m)}}$ is the sum of coefficients of the 
corresponding Schubert polynomial. 
It has been shown by I.G. Macdonald ([M1, M2, FS]) that for every 
permutation $\mu\in S_{n}$ of length $p=l(\mu)$ \begin{equation} 
X_{\mu}(1,\dots,1) = \frac{1}{p!} \sum_{a\in R(\mu)} pr(a)\ \text{ 
with }\ pr(a):=a_{1}\dots\ a_{p}\ . 
\end{equation}	 
Moreover Macdonald has conjectured the following $q$-analog,  
which subsequently has been proven by S. Fomin and R.P. Stanley in [FS]: 
\begin{equation} 
X_{\mu}(1,q,\dots,q^{n-2}) = \frac{1}{[p]!} \sum_{a\in R(\mu)}  
pr_{q}(a) \ q^{\alpha (a)} \ ,  
\end{equation} where 
$\alpha (a):= \sum_{a_{\nu} < a_{\nu+1}} \nu$, $[k]:= 1+q+\dots +q^{k-1}$, 
$[p]!:=[1][2]\dots\ [p]$, and $pr_{q}(a):= [a_{1}] \dots\ [a_{p}]$. 
 
Observing that for an unembedded $\pi\equiv\pi^{(0)}\in S_{n}$ of length $p$  
all $\pi^{(m)}$ have length $p$, too, by Lemma 2.3, formula (4.6) 
immediately implies 
\begin{equation} s_{\pi^{(m)}} = \frac{1}{p!} P_{\pi} (m)  
\end{equation} with 
\begin{equation} P_{\pi} (m) := \sum_{a\in R(\mu)} pr^{(m)}(a)\  
\text{ and } pr^{(m)}(a):=(m+a_{1}) \dots\ (m+a_{p})\ . 
\end{equation}  
The $q$-analog with  
$pr^{(m)}_{q}(a):=[m+a_{1}] \dots\ [m+a_{p}]$ is of course 
\begin{equation*} s_{\pi^{(m)}}(q):= 
X_{\pi^{(m)}}(1,q,\dots,q^{n-2}) = \frac{1}{[p]!} P_{\pi} (m;q) := 
\frac{1}{[p]!} \sum_{a\in R(\mu)} pr^{(m)}_{q}(a) \ q^{\alpha (a)} \ . 
\end{equation*} 
 
\begin{Prop} For all unembedded $\pi$ of length $p$ the polynomials  
$\frac{1}{p!} P_{\pi} (m)$ are elements of $\Q[m]$ with non-negative 
coefficients and degree $p$ with the property of \begin{equation*} 
\text{ integrality:} \quad \quad  
\frac{1}{p!} P_{\pi} (m) \in \N \ \text{ for all } m\in \N_{0}\ . 
\end{equation*} 
\end{Prop} \begin{proof} Immediate from formula (4.8) and the fact 
that the coefficients of Schubert polynomials are non-negative 
integers. \end{proof} 
 
\begin{Rem} In [FK] S. Fomin and A.N. Kirillov have shown that the 
polynomials $P_{\pi}(m)$ and $P_{\pi}(m;q)$ enumerate certain sets of plane 
partitions at least in the special case of $\pi$ being of `staircase shape'  
$\pi=n\ (n-1) \dots\ 1$ or more generally $\pi$ being dominant. 
Cor.4.4 below gives an answer to one of the question raised in [FK], 
namely for which $\pi$ the polynomial $P_{\pi}(m)$ is a product of linear 
factors in $\Z[m]$. 
\end{Rem} 
 
\begin{Prop} Let $\mu\in S_{n}$ be a permutation of length $p=l(\mu)$, 
$r(\mu)$ the number of reduced sequences {\rm [(0.5)]}, and $a(\mu)$ the 
canonical reduced sequence of $\mu$ {\rm [(2.4)]}. If now $\mu$ is  
{\em hexagon free}, that is: every $a\in R(\mu)$ can be computed 
from $a(\mu)$ by a sequence of transpositions according to 
relation {\rm (ii)} alone, then \begin{equation} 
p!\ s_{\mu} = r(\mu)\ pr(a(\mu))\ . \end{equation}  
\end{Prop} 
\begin{proof} Since transpositions according to relation (ii) do 
not change the `letters' contained in a reduced sequence $a$, the 
result is immediate from (4.8-9).  
\end{proof} 
 
\begin{Cor} The following statements are equivalent:\\
a) the polynomial $P_{\pi}(m)$ is a product of linear factors 
in $\Z[m]$;\\
b) $\pi$ is hexagon free.\\ c) $\pi$ is $321$-avoiding, i.e. there are no 
numbers $i < j < k$, such that $\pi(i) > \pi(j) > \pi(k)$.
\end{Cor} 
\begin{proof} a) $\gdw$ b) by the preceding proposition and  b) $\gdw$ c)
by [BJS, Thm.2.1].
 \end{proof}

We quote without proof a nice result from [M1, M2]: 
\begin{Prop} Let $\mu$ be vexillary of length $p$ and  
$\lambda \equiv \lambda (\mu)$ the partition obtained from reordering the  
entries of $L(\mu)$. Then with (0.5-6) \begin{equation}  
r(\mu) = f^{\lambda} = \frac{p!}{h(\lambda)}\ , \end{equation} 
where $h(\lambda )$ is the product of hooks according to the celebrated 
hook length formula. 
For Grassmannian permutations $\pi(\lambda )$ imply formulas {\rm 
(4.10-11)} that $h(\lambda)=s_{\pi(\lambda )}/pr(a(\pi(\lambda)))$. 
\end{Prop} 
 
Unfortunately the proportion of vexillary permutations contained in 
some $S_{n}$ is $\leq (23/24)^{n-3}$ for $n\geq 4$ and thus vanishes for 
$n\lra \infty $. In comparing Propositions 4.3 and 4.5 note that  
Grassmannian permutations are vexillary and hexagon free, but in general 
a vexillary permutation need not be hexagon free (e.g. $\pi=321$) 
and vice versa (e.g. $\pi=2143$). 
 
The following important general result has been observed by I.G. 
Macdonald, too: 
 
\begin{Prop} Let $\pi$ be an unembedded permutation of length $p$. 
Then \begin{equation} r(\pi)=  
p! \lim_{m\lra \infty } X_{\pi^{(m)}} (\frac{1}{m}, \dots, \frac{1}{m})\ . 
\end{equation} \end{Prop} 
\begin{proof} One has $p:=l(\pi)=l(\pi^{(m)})$ for all $m$; 
and a well known fact about Schubert polynomials says that the  
$X_{\pi^{(m)}}$ are homogeneous of degree 
$p$ for all $m$. Thus \begin{equation*} 
X_{\pi^{(m)}} (\frac{1}{m}, \dots, \frac{1}{m}) =  
(\frac{1}{m})^{p}\ X_{\pi^{(m)}} (1,\dots, 1)  
\end{equation*} and \begin{equation*} 
(\frac{1}{m})^{p} \ \lim_{m\lra \infty } pr^{(m)} (a) =  
\lim_{m\lra \infty } (1+\frac{a_{1}}{m}) \dots\ (1+\frac{a_{p}}{m}) = 
1 \quad \forall a\in R(\pi) \end{equation*}  
together with (4.8) prove (4.12). 
\end{proof} 
 
\begin{Def} Let $\pi \in S_{n}$ be an arbitrary permutation, then 
$\pi$ is called {\em decomposable} iff it is of the form 
`$\pi_{1}\times \pi_{2}$', where $\pi_{1}\in S_{k}$ for some $k\in 
\{1,\dots, n-1\}$ and $\pi_{2} \in S_{k_{+}(n-k)}:= S_{\{k+1, \dots, n\}}$. 
Otherwise $\pi$ is called {\em indecomposable}. The decomposition 
$\pi=\pi_{1}\times \dots\ \times \pi_{s}$ is called {\em maximal} iff 
the `parts' $\pi_{\nu}$ are indecomposable. (But it is useful to 
collect neighborly `identities'.) 
\end{Def} 
 
\begin{Prop} Let $\pi\in S_{n}$. Then the following statements are 
equivalent: \\ 
i) $\pi$ is decomposable with $\pi = \pi_{1}\times \pi_{2}$ and  
   $\pi_{1}\in S_{k}$ with $1\leq k\leq n-1$;\\ 
ii) $L(\pi)=[l_{n-1} \dots\ l_{0}]$ (cf. Sec.1) with  
   $[l_{n-1}\dots\ l_{n-k}] \in \llll_{k}$ and  
   $[l_{n-k-1}\dots\ l_{0}] \in \llll_{n-k}$.\\ 
iii) The interval $[id,\ \pi]$ in right (weak Bruhat) order is the 
    direct product of the intervals $[id,\ \pi_{1}]$ and $[id,\ \pi_{2}]$. 
 
Moreover with the notation of i) and $p:=l(\pi_{1})$, $q:=l(\pi_{2})$:  
\begin{equation}  
r(\pi) = \binom{p+q}{q}\ r(\pi_{1}) \ r(\pi_{2})\ . 
\end{equation}  
\end{Prop} 
\begin{proof} $i)$ means that on places $1, \dots, k$ there is a 
permutation of the letters $1, \dots, k$, and on places $k+1, \dots, n$ 
there is a permutation of the letters $k+1, \dots, n$. Hence $\pi_{1}$ 
and $\pi_{2}$ have independent complete Lehmer codes as stated in $ii)$,  
and for the entries of $a\equiv a_{1}, \dots, a_{p}\in R(\pi_{1})$ and  
$b\equiv b_{1}, \dots, b_{q} \in R(\pi_{2})$ one has from (2.3): 
$a_{\nu}\in \{1, \dots, k-1\}$ and $b_{\nu'}\in \{k+1, \dots, n-1\}$. 
Therefore all $a_{\nu}$ and $b_{\nu'}$ `commute' in the sense of relation 
(ii) of the introduction, which shows that $ii) \Lra iii) \Lra i)$.  
 
Moreover the `commutativity' of $a_{\nu}$'s and $b_{\nu'}$'s yields that  
the reduced sequences in $R(\pi)$ are exactly the $(p,q)$-shuffles of pairs 
$(a,b) \in R(\pi_{1}) \times R(\pi_{2})$, where the shuffles of the 
words $a$ and $b$ are all distributions of the $p$ letters of $a$ and  
the $q$ letters of $b$ over $p+q$ places such that $a$ and $b$ remain 
subwords. Clearly for a given pair $(a,b)$ the number of $(p,q)$-shuffles is 
$\binom{p+q}{q}$, which completes the proof. 
\end{proof} 
 
\begin{Rem} The reduced sequences of some permutation $\pi$ are the  
sequences of edge labels of maximal chains (without repetitions) in 
the interval $[id,\ \pi]$ of right order. In Rem.2.1 we have 
introduced the graph $GR(\pi)$ with vertex set $R(\pi)$ and in [W4] 
we have made $GR(\pi)$ into a ranked poset $PR(\pi)$ by declaring the  
canonical reduced word $a(\pi)$ as bottom element. It would be nice now to 
continue the equivalences of Prop.4.8 above by a characterization `$iv)$'  
of decomposability in terms of $GR(\pi)$ or $PR(\pi)$. 
 
This hints at a general problem: to every lattice ${\mathcal L}$ (or poset 
with top and bottom element) with labeled edges one can associate a graph  
$G{\mathcal L}$ on the set of `vertices' = `the maximal chains of  
${\mathcal L}$' by considering two chains, i.e. the associated sequences of 
labels, as `adjacent' iff they can by transformed into each other by changing 
as less labels as possible. With every (natural) choice of a 
`canonical vertex' as bottom element this graph may be turned into a 
poset $P{\mathcal L}$. The problem is now to find relationships 
between the original ${\mathcal L}$ and the associated graph or poset 
of maximal chains. 
\end{Rem} 
\hspace{20pt} 
 
\section{Generalizations of binomial coefficients} 
 
For every $n,k\in \N_{0}$ the binomial coefficients $\binom{n}{k}$ 
are well known to have the following properties: \begin{align*} 
\text{ integrality:}&\quad \quad  
      \binom{m+k}{k}\in\N\text{ for all } m\in\N_{0}\ ,\\ 
\text{ recursion:}&\quad \quad 
     \binom{n}{k} = \binom{n-1}{k} +\binom{n-1}{k-1}\ , \text{ and} \\ 
\text{ symmetry:}&\quad \quad  
        \binom{n}{k} = \binom{n}{n-k}\ . 
\end{align*} 
All these properties can be deduced at once from the fact  
(cf. [S2, Ex.3.5.4-5]) that $\binom{m+k}{k}$ is the number of linear 
extensions of the direct sum of the chains ${\bf m}$ and ${\bf k}$ with  
$m$ and $k$ elements, respectively, which is well known to be the number 
of saturated chains in the direct product ${\bf m+1}\times {\bf k+1}$: 
take the rectangular grid of points $[0,m]\times [0,k]\subset 
\Z\times \Z$ (--this is the direct product of the chains--) and count all 
possible paths or chains on this grid from $(0,0)$ to $(m,k)$ with steps 
$(1,0)$ and $(0,1)$; clearly the number of such chains is $\binom{m+k}{k}$, 
because the $k$ steps $(0,1)$ can be chosen as an arbitrary subset  
of the set of all $m+k$ steps. 
 
We call the partition $\lambda = (n-k+1)\ 1^{k}$ of $n+1$ the 
$(n,k)$-hook with leg consisting of $k$ boxes and arm consisting of $m=n-k$ 
boxes. The set $SYT(\lambda )$ of standard Young tableaux of 
such a $(n,k)$-hook is clearly in bijective correspondence to the 
saturated chains in ${\bf m+1}\times {\bf k+1}$: for $\nu=1,\dots, m+k$  
write the number $\nu$ into a box of the leg, if $\nu$ is a step $(0,1)$, 
otherwise into a box of the arm, such that resulting tableau is 
standard.  
 
Thus we conclude that the numbers $f^{\lambda }=|SYT(\lambda )|$ for 
partitions $\lambda $ generalize binomial coefficients. In fact all 
the direct sums of the chains ${\bf m}$ and ${\bf k}$ are the finite 
order ideals in $\N + \N$ ($\N$ viewed as the infinite chain 
$1<2<\dots$). $\N + \N$ is embedded (as half axes) into the 
direct product $\N\times\N$, which has as finite order ideals the 
Ferrer shapes of partitions $\lambda $.  
The Young lattice ${\mathcal Y}$ of all Ferrer shapes ordered by 
inclusion is therefore the (distributive) lattice of order ideals of 
$\N\times\N$, and the saturated chains of an interval  
$[\emptyset ,\ \lambda ]$ in ${\mathcal Y}$ are in natural one to one 
correspondence with the set $SYT(\lambda)$. The symmetry of binomial 
coefficients is generalized now by the conjugation of partitions:  
\begin{equation*} \text{ symmetry:} \quad \quad  
f^{\lambda } =f^{\lambda '} \quad (\text{ with $\lambda '$ the conjugate 
of $\lambda $)} \ , \end{equation*} 
the recursion relation is generalized by \begin{equation*} 
\text{ recursion:} \quad \quad  
f^{\lambda } = \sum_{\overline{\lambda } \text{ is covered by $\lambda $ 
in $\mathcal Y$ }} f^{\overline{\lambda } }\ . 
\end{equation*} 
 
Let $S_{\infty }=\underset{\longleftarrow}{\lim} _{n} S_{n}$ (using 
left embedding) and ${\mathcal P}_{\infty }$ the set $S_{\infty }$ 
with right (weak Bruhat) order, where right order is the transitive 
closure of the covering relation:\begin{equation} 
\pi \text{ covers } \overline{\pi } \text{ in } S_{\infty } \ :\gdw 
\exists i\in \N:\ \pi=\overline{\pi } \sigma _{i}, \  
l(\pi) = l(\overline{\pi }) +1 \ . 
\end{equation} Since the above condition for $i$ is fulfilled 
exactly when $i$ is a descent of $\pi$, i.e. $\pi(i) > \pi(i+1)$, it 
is helpful to define the {\em descent set of $\pi$}: \begin{equation}  
D(\pi) := \{i \mid \pi(i) > \pi(i+1) \}\ . 
\end{equation}  
Note that for $i\in D(\pi)$ the permutation $\pi\sigma _{i}$ is the 
same as $\pi$ except for the numbers $\pi(i)$ and $\pi(i+1)$ 
interchanged. 
The edges of the Hasse diagram of ${\mathcal P}_{\infty }$ can be 
labeled by the natural numbers $i$ according to (5.1-2). 
 
Since for every partition $\lambda $ we know e.g. from (4.11) that  
$r(\pi(\lambda ))= f^{\lambda }$ (-- see [W4] for a combinatorial 
bijection establishing this identity --), the sets $SYT(\lambda )$  are 
special cases of reduced words, and the reduced sequences for $\pi$ 
are the sequences of edge labels of saturated chains from $id$ to $\pi$ 
in ${\mathcal P}_{\infty}$. 
Therefore the numbers $f^{\lambda }$ are generalized by the numbers 
$r(\pi)\in \N$, which obey 
\begin{align} 
\text{ symmetry:}&\quad \quad  
r(\pi)= r(\pi') \quad (\text{ with $\pi':=\omega \pi \omega$ the `conjugate' 
of $\pi$) and } \\ 
\text{ recursion:}&\quad \quad  
r(\pi) = \sum_{i \in D(\pi)} r(\pi\sigma _{i})\ . 
\end{align} 
The notion `conjugate permutation' is justified by the fact that  
for every partition $\lambda $ one has  
$\pi'(\lambda ):=\omega\ \pi(\lambda )\ \omega = \pi(\lambda ')$  
with $\omega = n \ (n-1) \dots\ 1$ for $n$ large enough ([W1, Prop.4.9]). 
 
\begin{Rem} R.P. Stanley has defined ``generalized Pascal triangles" in an 
purely order theoretic way ([S2, S3]) relying on the Birkhoff duality 
between (finite) posets and distributive lattices ([S2, 3.4.1-3]). But the  
above described embedding of ${\mathcal Y}$ into ${\mathcal P}_{\infty}$  
is not covered by this result, because ${\mathcal P}_{\infty}$ is not 
even modular as can be seen already in the case of $S_{3}$. 
\end{Rem} 
 
An interesting other approach to a generalization of binomial 
coefficients is suggested by \begin{equation} 
\binom{m+k}{k} = \frac{1}{k!}\ P_{\pi(\lambda )} (m)  \text{ \ for $\lambda 
=1^{k}$ or $\lambda =k$.} \end{equation}  
This is true, because by (2.3-4) one has $a(\pi(1^{k}))=1 \dots\ k$ and  
$a(\pi(k))=k \dots\ 1$, whence $P_{\pi(\lambda )}(m)= 
(m+k)\cdot\dots\cdot (m+1)$ in both cases. 
Therefore binomial coefficients are generalized by the 
expressions $\frac{1}{l(\pi)!}\ P_{\pi}(m)$, which by Prop.4.1 fulfill 
\begin{equation} \text{ integrality:} \quad \quad  
\frac{1}{l(\pi)!}\ P_{\pi(\lambda )} (m) \in \N \text{ \ for all 
$m\in \N_{0}$.} \end{equation}  
(Note that for every $k\geq 2$ there are infinitely many unembedded $\pi$ 
of length $k$.) Furthermore one has the \begin{equation}  
\text{ recursion:} \quad \quad  
P_{\pi}(m) = \sum_{i\in D(\pi)} (m+i)\ P_{\pi\sigma _{i}} (m) \ , 
\end{equation} where for unembedded $\pi$ the covered $\pi\sigma _{i}$ 
are not necessarily unembedded. 
\vspace{20pt} 

\section{Computing the number of reduced sequences of a permutation} 
 
The number $r(\pi)$ of reduced sequences of a permutation $\pi\in S_{n}$ is  
easily computable by the recursion (5.4). But of course one would 
like to have a simple closed formula as in the case of Grassmannian  
or more generally vexillary permutations (Prop.4.5). An important step 
in this direction are the results of R.P. Stanley ([S1]) and 
Edelman and Green ([EG]), which say that the number of reduced 
sequences of a permutation $\pi$ can be computed as a sum of $f^{\lambda}$, 
where the $\lambda $'s are partitions of the length $l(\pi)$ of $\pi$: 
\begin{equation} 
r(\pi) = \sum_{\lambda \vdash l(\pi)} \alpha _{\pi\lambda }\ f^{\lambda } 
\ \text{ with } \alpha _{\pi \lambda }\in \N_{0} 
\end{equation} 
The non-negativity has been established in [EG] with the help of 
balanced tableaux. But more can be said: 
 
\begin{Thm} {\rm ([S1, Thm.4.1, Cor.4.2])} Let $\pi\in S_{n}$ be an 
arbitrary permutation and $\pi'=\omega_{n} \pi \omega _{n}$ its 
conjugate. Define \begin{align*}  
\lambda _{0} \equiv \lambda _{0}(\pi)& := \lambda (L(\pi')) \ , \\ 
\lambda _{1} \equiv \lambda _{1}(\pi)& := \lambda' (L(\pi)) \ , 
\end{align*} where $\lambda (L(\mu))$ is the partition obtained by 
reordering the components of the Lehmer code of the permutation 
$\mu$, and $\lambda '(L(\mu))$ is the conjugate of $\lambda (L(\mu))$. 
Then (with `$<$' being the dominance order on partitions) \begin{align*}  
r(\pi)& = f^{\lambda _{0}} =f^{\lambda _{1}} \ ,  
\text{ if } \lambda _{0} = \lambda _{1} \ , \\ 
r(\pi)& = f^{\lambda _{0}} + \sum_{\lambda_{0} < \lambda < \lambda_{1}}  
\alpha _{\pi\lambda }\ f^{\lambda } + f^{\lambda _{1}} \ ,  
\text{ if } \lambda _{0} \neq \lambda _{1} \ , \text{ whence:} \\ 
r(\pi)& = f^{\lambda _{0}} + f^{\lambda _{1}} \ ,  
\text{ if $\lambda _{1}$ covers $\lambda _{1}$ in dominance order.}  
\end{align*} 
The $\alpha _{\pi \lambda }$ occurring in the case  
`$\lambda _{0} \neq \lambda_{1}$' may be nonzero ! 
\end{Thm} \vspace{11pt} 
 
Except for the special cases discussed above there is unfortunately no simple 
method known how to compute the coefficients $\alpha _{\pi \lambda}$: 
 
In [S1] Stanley has introduced symmetric functions $F_{\pi}$ ($=G_{\pi^{-1}}$ 
in the notation of [FS]), which upon expansion into Schur functions yield 
the $\alpha _{\pi \lambda}$ as coefficients; but the $F_{\pi}$ in 
turn are computed from the sets $R(\pi)$ of reduced sequences of $\pi$.  
The sets of balanced tableaux studied and used in [EG] and [FGRS] seems to 
be much more complicated than the sets of standard tableaux or the 
sets $R(\pi)$ itself.  
Especially the computation of reduced words from balanced tableaux by a 
procedure of promotion and evacuation in [EG] seems to be of theoretical 
interest only. 
 
In view of the close connections between reduced words and balanced 
tableaux ([EG, FGRS]), reduced words and the Stanley functions $F(\pi)$ 
([S1]), Stanley functions and Schubert polynomials ([FS]), and balanced 
tableaux and both Stanley functions and Schubert polynomials ([FGRS]), it 
doesn't come as a surprise that Schubert polynomials can be used  
for the computation of the numbers $r(\pi)$. This will be the subject 
of this final section. 
 
 
By (2.16) and (4.13) we can restrict to unembedded and indecomposable  
permutations $\pi$. As an example take $\pi=132458769$, which is represented  
by the unembedded permutation $2134765=21\times 34\times 765\equiv 
\pi_{1}\times \pi_{2} \times \pi_{3}$. Since $l(\pi_{1})=1$, $l(\pi_{2})=0$, 
$L(\pi_{3})=\overline{210}$, $l(\pi_{3})=3$, and $\pi_{3}$ dominant  
(hence vexillary) of shape $\lambda (\pi_{3})=21$, one sees: 
$r(\pi)=\binom{4}{3} 1 \cdot 3=12$. 
(Note: $R(id)=\{\emptyset \}$, $r(id)=1$.) 
 
Propositions 4.1 and 4.6 have clearly shown the combinatorial 
significance of the polynomials $P_{\pi}(m)$ and their coefficients, and 
formula (4.8) connects the $P_{\pi}(m)$ to the sums $s_{\pi^{(m)}}$ of 
coefficients of the Schubert polynomials $X_{\pi^{(m)}}$ [(4.5)]. 
 
\begin{Lem} Let $\pi$ be an unembedded permutation of length $p$ and  
$P_{\pi}(m)=c_{p} m^{p} + \dots\ + c_{1} m + c_{0}$. Then  
$c_{0}=p! \ s_{\pi}$ and $c_{p} = r(\pi)$. 
\end{Lem} 
\begin{proof} Setting $m=0$ in (4.8) gives $c_{0}=p! \ s_{\pi}$. The 
other equality $c_{p} = r(\pi)$ follows directly from the definition  
of $P_{\pi}(m)$ in (4.8) and the observation that $pr^{(m)}(a)$ is a 
monic polynomial of degree $p$ in $m$ for all $a\in R(\pi)$.  
\end{proof} 
 
\begin{Thm} Let $\pi\in S_{n}$ be an unembedded permutation of length $p>0$.  
Then \begin{equation} 
r(\pi) = \sum_{i=0}^{p} (-1)^{p-i} \binom{p}{i}\ s_{\pi^{(i)}}\ . 
\end{equation} \end{Thm} 
\begin{proof} Using the notation of the above lemma and formula (4.8) one 
sees that for $p+1$ different values of $m$ one gets $p+1$ linear 
equations for the coefficients $c_{0}, \dots, c_{p}$. Taking the values  
$0,\dots, p$ \ we get the system \begin{equation*} 
c_{p} i^{p} + \dots + c_{1} i + c_{0} = p!\ s_{\pi^{(i)}},\ (i=p,\dots, 0)\ , 
\end{equation*} which can be solved for $c_{p}$ by Cramers rule. 
We use the Vandermonde $V_{n}(x_{1},\dots, x_{n}):= \det((x_{i}^{n-j}))$ 
to compute: \begin{equation*}  
r(\pi) = c_{p} = \frac{p!}{V_{p+1}(p,\dots,0)}\ \det((*\vert\ (p-i)^{p-j})) 
_{\substack{i=0,\dots,p\\ j=1,\dots,p}} 
\end{equation*}  
with $*$ being the column vector $(s_{\pi^{(i)}})_{i=p,\dots,0}$. 
Expansion of the determinant w.r.t. the first column $*$ yields  
\begin{multline*} \sum_{i=0}^{p} (-1)^{p-i}\ s_{\pi^{(i)}}\ 
V_{p} (p,\dots, p-i+1, p-i-1, \dots, 0) = \\ \sum_{i=0}^{p}  
(-1)^{p-i}\ s_{\pi^{(i)}}\ \frac{V_{p+1}(p,\dots,0)}{i! (p-i)!}\ , 
\end{multline*} which completes the proof. 
\end{proof} 
 
The drawback of formula (6.2) is of course that one needs to compute  
all the numbers $s_{\pi^{(m)}}$ for $m=0,\dots,p$, which is getting 
harder for increasing $m$. But as we will see next one usually has 
to compute only a small fraction of the numbers $s_{\pi^{(m)}}$.  
As Prop.4.3 has shown the complexity of the determination of $P_{\pi}(m)$ 
can be reduced considerably by singling out a factor corresponding to the  
multiset $M(\pi)$ of letters, which occur in all reduced sequences 
$a\in R(\pi)$ simultaneously. Since we don't want to determine $M(\pi)$ by 
enumeration of all reduced sequences, we must be content with the  
following (good) `approximation' of $M(\pi)$: 
 
\begin{Lem} {\rm ([FK, Lem.2.2])} For any permutation $\pi$ the number 
of occurrences of an entry $k$ in every $a\in R(\pi)$ is at least 
\begin{equation} m_{k}\equiv m_{k}(\pi):=\{i\mid i\leq k,\ \pi(i) > k \}\ . 
\end{equation} \end{Lem}  
\begin{proof} For the convenience and pleasure of the reader we quote  
the argument from [FK]: ``Let us interpret a reduced word as a process of 
converting the identity permutation into $\pi$ by means of adjacent 
transpositions. Since $m_{k}$ numbers have to be moved from some of 
the first $k$ positions to some of the remaining ones, it follows that 
the transposition $\sigma _{k}$ has to be applied at least $m_{k}$ times." 
\end{proof} 
 
For (unembedded) $\pi\in S_{n}$ we define the {\em $m$-vector} of $\pi$ 
by \begin{equation} m(\pi):=(m_{1}, \dots, m_{n-1})\ , 
\end{equation} e.g. $m(597216384)=(1,2,3,3,2,2,1,1)$, and a polynomial  
\begin{equation} 
(x)^{m(\pi)} := (x+1)^{m_{1}}\ (x+2)^{m_{2}} \dots\ (x+n-1)^{m_{n-1}} \ . 
\end{equation} In addition we introduce the polynomial $Q_{\pi}(m)$ by 
requiring 	  \begin{equation} P_{\pi}(m) = (m)^{m(\pi)} \ Q_{\pi}(m) \ . 
\end{equation} 
Then we get the following refinement of Thm.6.3: 
 
\begin{Thm} Let $\pi\in S_{n}$ be an unembedded permutation of length $p>0$ 
and $d:=p-|m(\pi)|=p-(m_{1} + m_{2} + \dots\ )$ {\rm [(6.3-4)]}. Then 
with with notations {\rm (4.5), (6.6)}: 
\begin{equation} r(\pi) = \sum_{i=0}^{d} (-1)^{d-i}\ 
\frac{p!}{d!\ (i)^{m(\pi)}}\ \binom{p}{i}\ s_{\pi^{(i)}}\ . 
\end{equation} \end{Thm} 
\begin{proof} Using the notation of Lemma 6.4,  and (4.8), (6.4-6) one 
sees that $Q_{\pi}(m)=c_{p} m^{d} + \dots\ $ . Taking $m= 0,\dots,d$ one now  
gets the system of linear equations: \begin{equation*} 
(i)^{m(\pi)}\ (c_{p} i^{d} + \dots\ )= p!\ s_{\pi^{(i)}},\ (i=d,\dots,0)\ . 
\end{equation*}  
A calculation similar to that in the proof of Thm.6.3 yields the result. 
\end{proof} 
 
For the computation of the numbers $s_{\pi^{(0)}}, \dots, s_{\pi^{(d)}}$ 
one can use advantageously the (up case) recursive structure of Schubert 
polynomials described in [W1]: assume $\pi\in S_{n}$ and $X_{\pi^{(m)}}$  
as known; then \begin{equation} X_{\pi^{(m+1)}}=  
\partial_{1}\dots\ \partial_{n+m} ( (x_{1}\dots\ x_{n+m}) X_{\pi^{(m)}})\ . 
\end{equation} 
\vspace{7pt} 
 
\begin{Ex} Take $\pi=4321$. Then $L(\pi)=\overline{3210}$, $l(\pi)=6$,  
$\lambda (L(\pi))=321$, and $r(\pi)=16$ by Prop.4.5. The 
$m$-vector for $\pi$ is $m(\pi)=(1,2,1)$, whence $d=2$. Since 
$s_{\pi^{(0)}}=1$, $s_{\pi^{(1)}}=14$, and $s_{\pi^{(2)}}=84$, 
formula (6.7) gives \begin{equation*} r(4321) = 30\cdot 1 - 10\cdot 
14 + \frac{3}{2}\cdot 84 = 30 -140 +126 = 16 
\end{equation*} as desired. 
\end{Ex} 
 
\begin{Rem}     
In a sense the Theorems 6.3 and 6.5 are complementary to the 
recursion formula (5.4): formula (5.4) relies on knowledge about  
the interval $[id,\pi]$ in right weak Bruhat order, and formulas (6.2)	 
and (6.7) on knowledge about certain Schubert polynomials, which is  
essentially equivalent to knowledge about the intervals  
$[\pi, \omega _{n+p}]$ and $[\pi, \omega _{n+d}]$, respectively. 
This can be seen from the method of divided differences or even more 
clearly from the ascent-descent method (cf. [W1, Sec.6]) for the computation 
of Schubert polynomials. 
\end{Rem} 
 
\begin{Thm} Let $\pi\in S_{n}$ be an unembedded permutation of length $p>0$ 
and let $\overline{s}_{\pi^{(m)}}$ denote the coefficient of the 
monomial $x_{1}\dots\ x_{p}$ in $X_{\pi^{(m)}}$. Then \begin{equation} 
0\leq \overline{s}_{\pi^{(0)}} \leq\overline{s}_{\pi^{(1)}} \leq 
\dots\ \leq \overline{s}_{\pi^{(p-2)}} \leq r(\pi) =  
\overline{s}_{\pi^{(p-1)}} = \overline{s}_{\pi^{(p)}} = \dots\ \ .  
\end{equation} \end{Thm} 
\begin{proof} Recall the BJS-formula (2.2) for Schubert polynomials. 
Clearly $b=p \dots 1$ appears at most once in a set $B(a)$. Moreover, 
$B(m_{+}(a))\subset B((m+1)_{+}(a))$ for all $m\in \N_{0}$ by Lemma 2.3, 
whence: $0\leq \overline{s}_{\pi^{(m)}} \leq r(\pi)$ and  
$\overline{s}_{\pi^{(m)}} \leq \overline{s}_{\pi^{(m+1)}}$ for all  
$m\in \N_{0}$. But for $m\geq p-1$ every entry $a_{\nu}$ of a reduced 
sequence $a$ obeys $a_{\nu}+m \geq 1+ (p-1)=p$; thus from the definition 
of the sets $B(m_{+}(a))$ it follows: $b=p\dots\ 1 \in B(m_{+}(a))$ 
for $m\geq p-1$ independently of $a\in R(\pi)$. \end{proof} 
 
Of course (6.9) in connection with the recursive computation (6.8) of  
Schubert polynomials can be used to determine $r(\pi)$, but more importantly 
(6.9) in connection with the K-rule for the combinatorial generation  
of Schubert polynomials opens up a way for the combinatorial determination 
of $r(\pi)$ and possibly the simple determination of the coefficients 
$\alpha _{\pi \lambda}$ in (6.1). 
Below we describe briefly the {\bf K-rule}, which has been conjectured 
for arbitrary $\pi$ (and proved for vexillary $\pi$) by A. Kohnert, 
and proved in general in [W2]. \\ 
 
A {\it box diagram} $B$ is a subset of an $n \times n$-array of unit  
squares or {\it boxes} in the plane:  
$B \subset \{[i,j]\in \Z\times\Z \mid 1\leq i,j \leq n \}$ for 
some $n\in \N$. The {\it position} ``column $i$, row $j$" will be  
denoted by $(i,j)$, the {\it box at position} $(i,j)$ 
by $[i,j]$. We use the notation $[i,j]\in B$ \ ($[i,j]\notin B$) 
as an abbreviation for: $B$ contains (does not contain) the box $[i,j]$. 
 
The {\it diagram} $D(\pi)$ of a permutation 
$\pi\in S_{n}$ is the box diagram, which originates from  
$\{ [i,j] \mid 1\leq i,j \leq n \}$ by cancelation of the `hooks' of boxes 
\begin{equation*} 
\{ [i',\pi (i)] \mid i'\geq i \}\cup \{ [i,j'] \mid j'\geq \pi (i) \} 
\end{equation*} for $i=1,\dots,n$.  
For example $\pi=263154$ has the diagram \\  
\begin{center} \bpi(60,60)(0,0) 
  \put(0,0){\line(0,1){60}} \put(0,0){\line(1,0){60}}  
  \put(0,60){\line(1,0){60}} \put(60,0){\line(0,1){60}}  
    \put(0,0){\ccx} \put(10,0){\ccx} \put(10,20){\ccx} 
	\put(10,30){\ccx} \put(10,40){\ccx} \put(20,0){\ccx} 
	\put(40,30){\ccx}  
    \put(0,10){\ccd} \put(10,50){\ccd} \put(20,20){\ccd} 
    \put(30,0){\ccd} \put(40,40){\ccd} \put(50,30){\ccd} 
  \put(-7,3){\scriptsize{1}} \put(-7,13){\scriptsize{2}} 
  \put(-7,23){\scriptsize{3}} \put(-7,33){\scriptsize{4}} 
  \put(-7,43){\scriptsize{5}} \put(-7,53){\scriptsize{6}}  
  \put(2,-6){\scriptsize{$x_{1}$}} \put(12,-6){\scriptsize{$x_{2}$}} 
  \put(22,-6){\scriptsize{$x_{3}$}} \put(32,-6){\scriptsize{$x_{4}$}} 
  \put(42,-6){\scriptsize{$x_{5}$}} \put(52,-6){\scriptsize{$x_{6}$}}  
\epi \quad , \end{center} \vspace{11pt} 
where we have added: dots in the positions $(i,\pi(i))$, row numbers  
$j=1,\dots,6$ at the left, and variables $x_{i}$ in columns $i=1,\dots,6$ 
at the bottom of the diagram. For the columns we have taken variables 
instead of numbers in view of the following {\em evaluation rule}: 
to every box diagram $B$ one associates 
a monomial $x^{B} := x_{1}^{\beta _{1}} x_{2}^{\beta _{2}} \dots\ $,  
where $\beta_{i}$ is the number of boxes in column $i$ of $B$. 
The most important part of the K-rule is now a prescription, how to 
move a box $[i,j]$ of a given box diagram $B$:  
 
\begin{Def} ({\bf of K-moves:}) \  
Let $[i,j]\in B$ with $\{ (i,j') \mid j'\geq j\} \cap B=\emptyset$, 
i.e. there is no box above $[i,j]$ in $B$, and assume that  
$M_{B} (i,j):=\{(i',j) \mid i'<i,\ [i',j] \notin B \}\neq \emptyset $.  
Then $[i,j]$ is allowed to move to the position in $M_{B} (i,j)$ with  
the greatest column number $i'$, i.e. the closest empty position left 
to $[i,j]$ in row $j$ of $B$. \end{Def} 
 
\begin{Thm} {\rm ([W2])} Let $\K(\pi)$ denote the set of all box diagrams, 
which can be derived by (repeated) K-moves from $D(\pi)$; then  
\begin{equation*} 
X_{\pi}=\sum_{B\in {\scriptsize \K(\pi)} } x^{B}\ . 
\end{equation*} \end{Thm}  
 
\begin{Ex} We depict $\K(31542)$ with $D(\pi)$ appearing as the upper left 
box diagram. (The empty third level has been omitted from all box 
diagrams.)\\ 
\begin{center} \bpi(300,80) 
  \put(0,50){\line(1,0){10}}   \put(10,50){\line(0,1){10}} 
  \put(10,60){\line(1,0){30}}   \put(0,50){\line(0,1){30}} 
    \put(0,50){\ccx} \put(0,60){\ccx} \put(20,60){\ccx} 
	\put(20,70){\ccx} \put(30,60){\ccx} 
  \put(80,50){\line(1,0){10}}   \put(90,50){\line(0,1){10}} 
  \put(90,60){\line(1,0){30}}   \put(80,50){\line(0,1){30}} 
    \put(80,50){\ccx} \put(80,60){\ccx} \put(100,60){\ccx} 
	\put(90,70){\ccx} \put(110,60){\ccx} 
  \put(160,50){\line(1,0){10}}   \put(170,50){\line(0,1){10}} 
  \put(170,60){\line(1,0){30}}   \put(160,50){\line(0,1){30}} 
    \put(160,50){\ccx} \put(160,60){\ccx} \put(190,60){\ccx} 
	\put(160,70){\ccx} \put(180,60){\ccx} 
  \put(240,50){\line(1,0){10}}   \put(250,50){\line(0,1){10}} 
  \put(250,60){\line(1,0){30}}   \put(240,50){\line(0,1){30}} 
    \put(240,50){\ccx} \put(240,60){\ccx} \put(270,60){\ccx} 
	\put(250,70){\ccx} \put(250,60){\ccx} 
  \put(0,0){\line(1,0){10}}   \put(10,0){\line(0,1){10}} 
  \put(10,10){\line(1,0){30}}   \put(0,0){\line(0,1){30}} 
    \put(0,0){\ccx} \put(0,10){\ccx} \put(20,10){\ccx} 
	\put(20,20){\ccx} \put(10,10){\ccx} 
  \put(80,0){\line(1,0){10}}   \put(90,0){\line(0,1){10}} 
  \put(90,10){\line(1,0){30}}   \put(80,0){\line(0,1){30}} 
    \put(80,0){\ccx} \put(80,10){\ccx} \put(110,10){\ccx} 
	\put(80,20){\ccx} \put(90,10){\ccx} 
  \put(160,0){\line(1,0){10}}   \put(170,0){\line(0,1){10}} 
  \put(170,10){\line(1,0){30}}   \put(160,0){\line(0,1){30}} 
    \put(160,0){\ccx} \put(160,10){\ccx} \put(170,10){\ccx} 
	\put(170,20){\ccx} \put(180,10){\ccx} 
  \put(240,0){\line(1,0){10}}   \put(250,0){\line(0,1){10}} 
  \put(250,10){\line(1,0){30}}   \put(240,0){\line(0,1){30}} 
    \put(240,0){\ccx} \put(240,10){\ccx} \put(260,10){\ccx} 
	\put(240,20){\ccx} \put(250,10){\ccx} 
\epi   \end{center}  \vspace{5pt} 
And indeed $X_{\pi}=   
x_{1}^{2} x_{3}^{2} x_{4} + x_{1}^{2} x_{2} x_{3} x_{4} 
+ x_{1}^{3} x_{3} x_{4} + x_{1}^{2} x_{2}^{2} x_{4} 
+ x_{1}^{2} x_{2} x_{3}^{2} + x_{1}^{3} x_{2} x_{4} 
+ x_{1}^{2} x_{2}^{2} x_{3} + x_{1}^{3} x_{2} x_{3} $.  
\end{Ex} 
 
\begin{Cor} Let $\pi\in S_{n}$ be an unembedded permutation of length 
$p>0$, and define \begin{equation*} \overline{\K}(\pi^{(m)}) :=  
\{ B\in \K(\pi^{(m)}) \mid x^{B}=x_{1}\dots\ x_{p} \}  
\end{equation*} for every $m\in \N_{0}$.  
Then $r(\pi)=|\overline{\K}(\pi^{(m)})|$ for $m\geq p-1$.  
\end{Cor}  
\begin{proof} Immediate from Theorems 6.7 and 6.9. \end{proof} 
 
This corollary opens up a combinatorial way for the determination of 
the numbers $r(\pi)$. We remark that a box diagrams in $B\in \K(\pi^{(m)})$ 
(or $\overline{\K}(\pi^{(m)})$) gives rise in a natural way to a labeling 
of $D(\pi)$, which is called the retract $r(B)$ in [W2, Def.4.1], 
and which in general is substantially different from the balanced  
labelings of [EG] and [FGRS]. 
It seems possible that a closer inspection of the 
sets $\K(\pi^{(m)})$ could yield a combinatorial method for the 
determination of the coefficients $\alpha _{\pi \lambda }$ in (6.1) 
resp. Theorem 6.1. 
\begin{Rem} A short time after finishing the present paper conversations with
Mark Shimozono brought to light that the paper [RS, Thm.24]
of Reiner and Shimozono contains a combinatorial algorithm for the 
computation of the numbers  $\alpha _{\pi \lambda }$. The algorithm
begins with the diagram $D(\pi)$ and is based on the notions of 
`plactification' and `peelable tableau'. In fact it seems that 
this approach has been known already by Lascoux and Sch\"{u}tzenberger and that
it underlies a MAPLE routine in the package ACE, which computes the number
 of reduced words. Therefore it is almost certain that a related algorithm
exists, which is based on the K-rule. 
\end{Rem} 
\vspace{20pt} \vfill \pagebreak
 
\begin{thebibliography}{99}
\bibitem[BJS]{BJS} {\sf S. Billey, W. Jockusch, R.P. Stanley}, 
Some combinatorial properties of Schubert polynomials, 
{\it J. of Algebraic Combinatorics} {\bf 2} (1993), 345 -374.
\bibitem[EG]{EG} {\sf P. Edelman, C. Greene}, Balanced Tableaux, 
{\it Advances in Math.} {\bf 63} (1987), 42 - 99. 
\bibitem[FGRS]{FGRS} {\sf S. Fomin, C. Greene, V. Reiner, M. 
Shimozono}, Balanced Labelings and Schubert Polynomials, preprint (1995). 
\bibitem[FK]{FK} {\sf S. Fomin, A.N. Kirillov}, Reduced words and 
plane partitions, preprint (1995). 
\bibitem[FS]{FS} {\sf S. Fomin, R.P. Stanley}, Schubert Polynomials 
and the NilCoxeter Algebra,  
{\it Advances in Math.} {\bf 103} (1994), 196 - 207. 
\bibitem[Hi]{Hi} {\sc H. Hiller}, ``Geometry of Coxeter groups", Pitman, 
Boston, 1982.  
\bibitem[LS]{LS} {\sc A. Lascoux, M.-P. Sch\"utzenberger}, D\'{e}compositions 
dans l'alg\'{e}bre des diff\'{e}rences divis\'{e}es, {\it discrete math.} 
{\bf 99} (1992), 165-179. 
\bibitem[M1]{M1} {\sf I.G. Macdonald}, ``Symmetric functions and Hall 
polynomials", Clarendon Press, Oxford, 1979. 
\bibitem[M2]{M2} {\sf I.G. Macdonald}, Schubert polynomials, {\it in}: 
{\sc A.D. Kendwell (ed.)}, ``Surveys in Combinatorics", London Math. 
Soc. Lec. Notes Ser. {\bf 166}, 73-99, Cambridge University Press, 
Cambridge, 1991. 
\bibitem[M3]{M3} {\sf I.G. Macdonald}, ``Notes on Schubert 
polynomials", Publications du L.A.C.I.M., vol. 6, Universit\'{e} du  
Qu\'{e}bec, Montr\'{e}al, 1991. 
\bibitem[Sa]{Sa} {\sf B.E. Sagan}, ``The Symmetric Group", Wadsworth \& 
Brooks/Cole, Pacific Grove, California (1991).
\bibitem[RS]{RS} {\sf V. Reiner, M. Shimozono}, Plactification,
{\it J. of Algebraic Combinatorics} {\bf 4} (1995), 331 - 351.  
\bibitem[S1]{S1} {\sf R.P. Stanley}, On the Number of Reduced 
Decompositions of Elements of Coxeter Groups, {\it Europ. J. 
Combinatorics} {\bf 5} (1984), 359 - 372. 
\bibitem[S2]{S2} {\sf R.P. Stanley}, ``Enumerative Combinatorics, 
Volume I", Wadsworth \& Brooks/Cole, Montery CA, 1986. 
\bibitem[S3]{S3} {\sf R.P. Stanley}, The Fibonacci lattice, 
{\it Fib. Quart.} {\bf 13} (1975), 215 - 232. 
\bibitem[T]{T} {\sf G.P. Thomas}, Frames, Young Tableaux, and Baxter 
Sequences, {\it Advances in Math.} {\bf 26} (1977), 275 - 289. 
\bibitem[W1]{W1} {\sf R. Winkel}, Recursive and combinatorial 
properties of Schubert polynomials, preprint (1995). 
\bibitem[W2]{W2} {\sf R. Winkel}, A combinatorial rule for the 
generation of Schubert polynomials, preprint (1995). 
\bibitem[W3]{W3} {\sf R. Winkel}, Sequences of symmetric polynomials 
and combinatorial properties of tableaux, preprint (1995). 
\bibitem[W4]{W4} {\sf R. Winkel}, A combinatorial bijection between standard 
Young tableaux and reduced words of Grassmannian permutations, 
S\`{e}minaire Lotharingien et Combinatoire, {\bf B36h} (1996), 24pp.
\end{thebibliography} 
\end{document}  
