1. The simple transpositions in $S_n$ satisfy the given relations.
2. The simple transpositions generate $S_n.$
3. The group given by generators $s_1,...,s_{n-1}$ and relations as in the statement of the theorem has order $\le n!.$

1. The following pictures show that the simple transpositions $s_i=(i,i+1), 1\le i\le n-2$ satisfy the given relations. $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$ $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$ $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$
2. The diagram of any permutation can be "stretched" to guarantee that no more than two edges cross at any given point. Then $w$ can be written as a product of simple transpositions corresponding to these crossings. $$w=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=s_1{s}_3{s}_5{s}_4{s}_5{s}_3.$$
3. Let $G_n$ be the free group generated by symbols $s_1,s_2,...,s_{n-1}$ modulo the relations in the statement of the theorem. Let $G_{n-1}$ be the subgroup generated by $s_1,s_2,...,s_{n-2}.$ We will show that
   1. Every element $w\in G_n$ can be written in the form $w=w_1{s}_{n-1}{w}_2,$ with $w_1,w_2\in G_{n-1}.$
   2. Every element $w\in G_n$ can be written in the form $w=a{a}_{n-1}{s}_{n-2}\cdots s_k, 1\le k\le n,$ and $a\in G_{n-1}.$
   
   
   1. Since $s_{n-1}^2=1$ every element $w\in G_n$ can be written in the form $$w=w_1{s}_{n-1}{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l,where\; w_j\in G_{n-1}.$$ By induction, either $w_2\in G_{n-2}$ or $w_2=a{s}_{n-2}b$ where $a,b\in G_{n-2}.$ In the first case $$\begin{array}{rcl}w& =& w_1{s}_{n-1}{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{w}_2{s}_{n-1}{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l,\end{array}$$ and in the second case $$\begin{array}{rcl}w& =& w_1{s}_{n-1}{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{s}_{n-1}a{s}_{n-2}b{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_{1}a{s}_{n-1}{s}_{n-2}{s}_{n-1}b{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_{1}a{s}_{n-2}{s}_{n-1}{s}_{n-2}b{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1^{\prime }{s}_{n-1}{w}_3^{\prime }{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\end{array}$$ where $w_1^{\prime }=w_{1}a{s}_{n-2}\in G_{n-1}$ and $w_3^{\prime }=s_{n-2}b{w}_3\in G_{n-1}.$ In either case the number of $s_{n-1}$ factors in the expression of $w$ has been reduced. The statement in (1) follows by induction.
   2. By (1) any element $w\in G_n$ is either an element of $G_{n-1}$ or can be written in the form $w=w_1{s}_{n-1}{w}_2,$ with $w_1,w_2\in G_{n-1}.$ In the first case $w=w{s}_{n-1}\cdots s_l$ with $l=n$ and the statement is satisfied. If $w=w_1{s}_{n-1}{w}_2$ then, by induction, $w_2=a{s}_{n-2}{s}_{n-3}\cdots s_l,$ for some $1\le l\le n-2$ and $a\in G_{n-2}.$ So $$w=w_1{s}_{n-1}a{s}_{n-2}\cdots s_l=w_{1}a{s}_{n-1}\cdots s_l=w_1^{\prime }{s}_{n-1}\cdots s_l,$$ where $w_1^{\prime }=w_{1}a\in G_{n-1}.$ Statement (2) follows.
   From (2) it follows that $\mathrm{Card}\left(G_n\right)\le \mathrm{Card}\left(G_{n-1}\right)\cdot n,$ and, by induction, that $\mathrm{Card}\left(G_n\right)\le n!.$ Since $S_n$ is a quotient of $G_n$ and $\mathrm{Card}\left(S_n\right)=n!$ we have $G_n\cong S_n.$

$\square$

1. The $S^{\lambda }$ are $S_n-$modules,
2. The $S^{\lambda }$ are non-isomorphic,
3. The $S^{\lambda }$ are all irreducible,
4. The $S^{\lambda },$$\lambda ⊢n,$ are all irreducible $S_n-$modules.

1. In order to show that $S^{\lambda }$ is an $S_n-$module there are three relations to check
   1. $s_i^2=1,$
   2. $s_i{s}_j=s_j{s}_i,$ if $|i-j|>1,$
   3. sisi+1si=si+1sisi+1.
   1. The action of $s_i$ preserves the subspace $S$ spanned by the vectors $v_Q$ indexed by the standard tableaux in the set $\{Q,s_{i}Q\}.$ Depending on the relative positions of the boxes containing $i$ and $i+1$ this space is either one or two dimensional. $$\begin{array}{ccc} & & \\ Case\; (A)& Case\; (B)& Case\; (C)\end{array}$$ In Case (A) the space $S$ is one dimensional and $s_i$ acts by the matrix $M\left(s_i\right)=1.$ In Case (B), $S$ is one dimensional and $s_i$ acts by the matrix $M\left(s_i\right)=-1.$ In Case (C), $S$ is two dimensional and $s_i$ acts on the subspace $S$ by a matrix of the form $$M\left(s_i\right)=\left(\begin{array}{cc}\frac{1}{a-b}& 1+\frac{1}{b-a}\\ 1+\frac{1}{a-b}& \frac{1}{b-a}\end{array}\right).$$ In cases (A) and (B) it is immediate that $M{\left(s_i\right)}^2=1$ and in case (C), since $\mathrm{Tr}\left(M\left(s_i\right)\right)=0$ and $\det \left(M\left(s_i\right)\right)=\mathrm{-}1,$ it follows from the Cayley-Hamilton theorem that $M{\left(s_i\right)}^2=\mathrm{Id}.$
   2. The action of $s_i$ and $s_j$ commute if $|i-j|>1$ because $s_i$ only moves $i$ and $i+1$ in $T$ and $s_j$ only moves $j$ and $j+1.$ The condition $|i-j|>1$ guarantees that $\{i,i+1\}$ and $\{j,j+1\}$ do not intersect.
   3. According to the formulas for the action, $s_i$ and $si+1$ preserve the subspace $S$ spanned by the vectors $v_Q$ indexed by the standard tableaux $Q$ in the set $\{L,s_{i}L,s_{i+1}L,s_i{s}_{i+1}L,s_{i+1}{s}_{i}L,s_i{s}_{i+1}{s}_{i}L\}.$ Depending on the relative positions of the boxes containing $i, i+1, i+2$ in $L,$ this space is either 1, 2, 3, or 6 dimensional. Representative cases are when these boxes are positioned in the following ways. $$\begin{array}{cccc} & & & \\ Case\; (1)& Case\; (2)& Case\; (3)& Case\; (4)\end{array}$$ In Case (1) the space $S$ is one dimensional and spanned by the vector $v_Q$ corresponding to the standard tableau
      where $a=i,b=i+1,$ and $c=i+2.$ The action of $T_i$ and $T_{i+1}$ on $S$ is given by the matrices $$M\left(s_i\right)=\left(1\right),andM\left(s_{i+1}\right)=\left(1\right),$$ respectively. In case (2) the space $S$ is two dimensional and spanned by the vectors $v_Q$ corresponding to the standard tableaux
      $$
      where $a=i,b=i+1,$ and $c=i+2.$ The action of $T_i$ and $T_{i+1}$ on $S$ is given by the matrices $$M\left(s_i\right)=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)andM\left(s_{i+1}\right)=\left(\begin{array}{cc}\frac{1}{2}& \frac{3}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right).$$ In case (3) the space $S$ is three dimensional and spanned by the vectors $v_Q$ corresponding to the standard tableaux
      $$ $$
      where $a=i,b=i+1,$ and $c=i+2.$ The action of $T_i$ and $T_{i+1}$ on $S$ is given by the matrices $$\begin{array}{rcl}M\left(T_i\right)& =& \left(\begin{array}{ccc}1& 0& 0\\ 0& \frac{1}{x_1-x_3}& 1+\frac{1}{x_3-x_1}\\ 0& 1+\frac{1}{x_1-x_3}& \frac{1}{x_3-x_1}\end{array}\right)and\\ {\varphi }_S\left(T_{i+1}\right)& =& \left(\begin{array}{ccc}\frac{1}{x_2-x_3}& 1+\frac{1}{x_3-x_2}& 0\\ 1+\frac{1}{x_2-x_3}& \frac{1}{x_3-x_2}& 0\\ 0& 0& 1\end{array}\right)\end{array}$$ respectively, where $x_1=c\left(L\left(i\right)\right), x_2=c\left(Li+1)\right)$ and $x_3=c\left(L(i+2)\right).$ In case (4) the space $S$ is six dimensional and spanned by the vectors $v_Q$ corresponding to the standard tableaux
      $$ $$ $$ $$ $$
      where $a=i,b=i+1,$ and $c=i+2.$ The action of $T_i$ and $T_{i+1}$ on $S$ is given by the matrices $$M\left(s_i\right)=\left(\begin{array}{cccccc}\frac{1}{x_1-x_2}& 1+\frac{1}{x_2-x_1}& 0& 0& 0& 0\\ 1+\frac{1}{x_1-x_2}& \frac{1}{x_2-x_1}& 0& 0& 0& 0\\ 0& 0& \frac{1}{x_1-x_3}& 1+\frac{1}{x_3-x_1}& 0& 0\\ 0& 0& 1+\frac{1}{x_1-x_3}& \frac{1}{x_3-x_1}& 0& 0\\ 0& 0& 0& 0& \frac{1}{x_2-x_3}& 1+\frac{1}{x_3-x_2}\\ 0& 0& 0& 0& 1+\frac{1}{x_2-x_3}& \frac{1}{x_3-x_2}\end{array}\right)$$ and $$M\left(s_{i+1}\right)=\left(\begin{array}{cccccc}\frac{1}{x_2-x_3}& 0& 1+\frac{1}{x_3-x_2}& 0& 0& 0\\ 0& \frac{1}{x_1-x_3}& 0& 0& 1+\frac{1}{x_3-x_1}& 0\\ 1+\frac{1}{x_2-x_3}& 0& \frac{1}{x_3-x_2}& 0& 0& 0\\ 0& 0& 0& \frac{1}{x_1-x_2}& 0& 1+\frac{1}{x_2-x_1}\\ 0& 1+\frac{1}{x_1-x_3}& 0& 0& \frac{1}{x_3-x_1}& 0\\ 0& 0& 0& 1+\frac{1}{x_1-x_2}& 0& \frac{1}{x_2-x_1}\end{array}\right)$$ where $x_1=c\left(L\left(i\right)\right), x_2=c\left(L(i+1)\right)$ and $x_3=c\left(L(i+2)\right).$ In each case we compute directly the products $M\left(s_i\right)M\left(s_{i+1}\right)M\left(s_i\right)$ and $M\left(s_{i+1}\right)M\left(s_i\right)M\left(s_{i+1}\right)$ and verify that they are equal.
2. Let $T$ be a standard tableau with $n$ boxes and let $T^{-}$ be the standard tableau $T$ except with the box containing $n$ removed. Then $T$ is the unique standard tableau given by adding a box (containing $n$) to $T^{-}$ in the diagonal of boxes with content $c\left(T\left(n\right)\right).$ Thus, by induction on the number of boxes in $T,$ $$T \; is\; uniquely\; determined\; by\; the\; sequence\; (c\left(T\left(1\right)\right),c\left(T\left(2\right)\right),...,c\left(T\left(n\right)\right)).$$ For example: if $(c\left(T\left(1\right)\right),c\left(T\left(2\right)\right),...,c\left(T\left(n\right)\right))=(0,1,-1,0,2,-2,-1,-3,1,3,2,-4,-3,-5,-6)$ then $$T=\begin{array}{c} 1 2 5 10 3 4 9 11 6 7 8 13 12 14 15 \end{array}$$ It follows that the vector $v_T$ is, up to constant multiples, the unique vector in all the $S^{\lambda }$ such that $x_k{v}_T=c\left(T\left(k\right)\right)v_T,$ for all $1\le k\le n.$ This proves that the $S^{\lambda }$ are nonisomorphic.
3. Let us show that $S^{\lambda }$ is irreducible. Let $N$ be a nonzero submodule of $S^{\lambda }$ and let $n=\sum _T{a}_T{v}_T$ be a nonzero vector in $N.$ Fix $T$ such that $a_T\ne 0.$ It follows from the lemma and the fact that $T$ is determined by the sequence $(c\left(T\left(1\right)\right),...,c\left(T\left(n\right)\right))$ that the element in $ℂS_n$ given by $$p_T=\prod _{k=1}^n\prod _{\genfrac{}{}{0ex}{}{j\ne c\left(T\left(k\right)\right)}{-n\le j\le n}}\frac{x_k-j}{c\left(T\left(k\right)\right)-j},acts\; on\; S^{\lambda } \; by{p}_T{v}_S={\delta }_{ST}{v}_T,$$ for all standard tableaux $S$ of shape $\lambda .$ So $(1/a_T)p_{T}n=v_T\in N.$
   
   Let $Q$ be a standard tableau of shape $\lambda$ and let $k$ be minimal such that $k+1$ is southwest (strictly south and strictly west) of $k$ in $Q.$
   In $k$ exists then $s_{k}W$ is a standard tableau and if $k$ doesn't exist then $Q$ is the column reading tableau, i.e. $Q$ is given by filling the boxes of $\lambda$ sequentially down columns from left to right. $$C=\begin{array}{c} 1 6 9 12 14 2 7 10 13 15 3 8 11 4 5 \\ Column\; reading\; tableau\end{array}$$ By repeating the procedure with $s_{k}Q$ in place of $Q$ repeatedly we construct a sequence $$Q,s_{k_1}Q,s_{k_2}{s}_{k_1}Q,...,s_{k_r}\cdots s_{k_2}{s}_{k_1}Q=C,$$ which ends at the column reading tableau $C.$ By concatenating this sequence with a similar sequence for $T,$ $T,s_{l_1}T,...,s_{l_m}\cdots s_{l_2}{s}_{l_1}T=C$ we obtain a sequence $T,s_{l_1}T,...,C,...,s_{k_1}Q,Q=s_{k_1}\cdots s_{k_r}{s}_{l_m}\cdots s_{l_1}T$ of standard tableaux of shape $\lambda$ which begins at $T$ and ends at $Q.$
   
   If $P$ is a standard tableau in this sequence and $v_P\in N$ and $s_{k}P$ is the next standard tableau in the sequence, then $$\begin{array}{rcl}(s_k-\frac{1}{c\left(P(k+1)\right)-c\left(P\left(k\right)\right)})v_P& =& (1+\frac{1}{c\left(P(k+1)\right)-c\left(P\left(k\right)\right)})v_P\\ & =& \left(\frac{c\left(P(k+1)\right)-c\left(P\left(k\right)\right)+1}{c\left(P(k+1)\right)-c\left(P\left(k\right)\right)}\right)v_{s_{k}P}.\end{array}$$ Since $s_{k}P$ is standard, $c\left(P(k+1)\right)-c\left(P\left(k\right)\right)+1\ne 0$ and so it follows that $v_{s_{k}P}\in N.$ Thus since $v_T\in N$ it follows that $v_Q\in N.$
   
   So $v_Q\in N$ for all standard tableaux of shape $\lambda .$ So $N$ contains a basis of $S^{\lambda }.$ So $N=S^{\lambda }.$ So $N$ is irreducible.
4. Let $f^{\lambda }$ be the number of standard tableaux of shape $\lambda .$ Then $$n!=\sum _{\lambda ⊢n}{\left(f^{\lambda }\right)}^2.$$ The proof is accomplished by giving a bijection between $$\begin{array}{rcl}permutations\; w\in S_n& and& pairs\; (P,Q) \; of\; standard\; tableaux,\\ & & of\; the\; same\; shape,\; with\; n \; boxes.\end{array}$$ The matching of $w\in S_n$ with a pair $(P,Q)$ is accomplished by a recursive algorithm which begins with $(P_0,Q_0)=(\varnothing ,\varnothing )$ and, at step $i,$ "inserts" $w\left(i\right)$ into $(P_{i-1},Q_{i-1})$ to obtain $(P_i,Q_i).$ The output of the algorithm is the pair of tableaux $(P,Q)=(P_n,Q_n).$
   
   The insertion step for inserting $w\left(i\right)$ into $(P_{i-1},Q_{i-1}):$
   1. Place $w\left(i\right)$ into the first column of $P_{i-1}$ as follows. If $w\left(i\right)$ is greater than all entries of column 1 of $P_{i-1}$ then place $w\left(i\right)$ at the end of column 1. Otherwise there is a unique entry in column 1 which can be replaced by $w\left(i\right)$ and preserve the standardness condition. (This is the smallest entry larger than $w\left(i\right).$)
   2. If $w\left(i\right)$ displaces an entry from column 1 then the displaced entry is inserted into column 2 (in exactly the same way that $w\left(i\right)$ was inserted into column 1). The displaced entries are successively inserted into the next column, and the process continues until there is no displaced entry.
   The resulting standard tableau is $P_i,$ which contains one more box than $P_{i-1}.$ The tableau $Q_i$ is obtained by adding a box filled with $i$ to $Q_{i-1}$ so that $P_i$ and $Q_i$ are the same shape.
   
   To show that the algorithm produces a bijection it is necessary to confirm that the process can be reversed. To see this note that, given $(P_i,Q_i),$ the position of the box containing $i$ in $Q_i$ tells which box of $P_i$ must be "uninserted" to obtain $P_{i-1}.$ The column by column insertion of this box will bump out an entry from column 1 of $P_i$ and this entry is $w\left(i\right)$ for the permutation $w$ which corresponds to the pair $(P,Q).$

$\square$

$\square$