A new approach to word standardization and some of its applications

Authors: WESAM TALAB

Abstract: In this article, we study word standardization in comparison to Young tableau standardization. We count the number of words (respectively Young tableau) standardized to a given permutation (respectively to a given standard Young tableau). We prove that both rectification and standardization applications commute and show that the standardization commutes with the insertion of Robinson--Schensted. We show that the standardizations of Knuth-equivalent two words are also Knuth equivalent. Finally, using word standardization we establish a proof for the following well-known equality: $$ \forall l \in \left\lbrace 0,1,\ldots,n-1\right\rbrace ,~~\left \langle {n\atop l} \right \rangle=d_{n,l}=a_{n,l}= \sum_{0\leq k \leq l}(-1)^k { n+1 \choose k } (l+1-k)^n. $$

Keywords: RSK the correspondence of Robinson-Schensted-Knuth, Young tableaux, word standardization, Knuth equivalent of words, Eulerian number

Full Text: PDF