I would like to find an expression for the number of words that can be formed from a given word by a certain number of adjacent transpositions (without reversing any transpositions). In particular I care about the case with only two distinct elements.
Given a word ...AABB... with n A's and m B's I would like to know how many words can be made from k adjacent transpositions. For example, consider the word AABBB, then there is one word from a single adjacent transposition, namely ABABB, two from two, BAABB and ABBAB, etc.
I would like to know this because the elements I am dealing with pick up a complex phase when commuted. I have a sum over all anagrams of these elements and need to keep track of the phases and their multiplicities so that this sum can be written as a complex number times the ordered word ...AABB...
Please let me know if my question is unclear or whether the language of words/anagrams etc. is not standard.
Recall that $[n]_q=1+q+\cdots +q^{n-1}$ are the $q-$numbers. From there, one can define the $q-$factorial as $[n]_q!=[n]_q[n-1]_q\cdots [2]_q[1]_q.$ As an intermediate exercise one can see that $$[n]_q=\sum _{i = 0}^{\binom{n}{2}}A_{n,i}q^i,$$ where $A_{n,i}=|\{\sigma \in S_n:|Inv(\sigma)|=i\}|,$ so number of permutations with $i$ inversions.
As you have factorials, then you can define binomials, so you define $$\binom{a+b}{b}_q=\frac{[a+b]_q!}{[a]_q![b]_q!}=\sum _{i=0}^{\infty}B_{a,b,i}q^i,$$ you can show that with the description of the coefficients $A_{n,i}$ you will get that $B_{a,b,i}$ can be represented as the number of Young diagrams (i.e., tuples $(r_1,\cdots, r_k)$ such that $\sum _j r_j = i$ and $k\leq b$ and $r_1 \leq a$ and $r_1\geq r_2\geq \cdots \geq r_k>0$) inside the rectangle $[0,a]\times [0,b]$ in the plane with area $i.$
Now, the claim is that if we call $a$ the number of $A's$ in your string and $b$ number of $B's$ and $i$ the number of transpositions, then $B_{a,b,i}$ is your answer. Let's enumerate the A's and B's on your string for a moment, so $x=A_1\cdots A_aB_1\cdots B_b$ so note that if you move $A_a$ say $r_1$ times, then you can move $A_{a-1}$(called the number of transpositions $r_2$) the same amount or less (so you get $r_1\geq r_2 \geq \cdots \geq r_a\geq 0$). Notice also that you can not move $A_a$ more times that the numbers of B's, so $b\geq r_1$ and note then that the total amount of movements is $r_1+r_2+\cdots +r_a$ So, do you see know that this is exactly the same?