number of non-equivalent permutations of constant length of sequence of transpositions

36 Views Asked by At

We all know that the symmetric group $S_n$ could be viewed as a Coxeter group <$t_1,t_2,..,t_{n-1}|(t_i)^2=1 $>, where $t_i$ refers to transposition $(i,i+1)$. We define the length of a sequence of $\{t_1,t_2,..,t_{n-1}\}$ to be the number of bits in the sequence. For example, sequence $t_1t_2t_3t_4t_1$ has length 5 and sequence $t_1t_1t_2$ has length 3. Now suppose we have a sequence of length $k$, is there any theorem telling us how many different permutations are there among all these $(n-1)^k$ sequences?