%%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 \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'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}