Generalisation of Binomial Coefficient (Combinatorics on words)

Question

So, when trying to find subwords from a bigger word:

$\binom{abracadabra}{ab} = 5$

with $ABracadabra$, $AbracadaBra$, $abrAcadaBra$, $abracAdaBra$, $abracadABra$.

I have noticed that it doesn't go back (like first $a$ then $b$ in $abracadaBrA$) and it looks like it iterates through all (factorial?).

I thought of cardinalitates $n\cdot a\cdot (m \cdot b - 1)$, where $n$ is the number of $a$'s and $m$ of $b$'s but it isn't that.

Also just for $\binom{a^n}{a^m}$ the binomial $\binom{n}{m}$ fits perfectly.

And what is the general formula about that one here?

$\binom{(ba)^n}{(ba)^m}$

Answer 1

First of all, I recommend you to read Chapter 6 of Lothaire's book Combinatorics on words. The binomial coefficients can be computed from the three following formulas, where $u$ and $v$ are words, $a$ and $b$ are letters and $1$ is the empty word.

1. $\binom{u}{1} = 1$,
2. $\binom{u}{v} = 0$ if $|u| \leqslant |v|$ and $u \neq v$,
3. $\binom{ua}{vb} = \binom{u}{vb} + \delta_{a,b} \binom{u}{v}$

Hint to prove 3. If $a \not= b$, every subsequence of $ua$ equal to $vb$ is also a subsequence of $u$. If $a = b$, there are two categories of subsequences of $ua$ that are equal to $va$: those containing the last $a$ and those that are subsequences of $u$.

Another very useful formula is the following $$ \binom{u_1u_2}{v} = \sum_{v_1v_2 = v}\binom{u_1}{v_1}\binom{u_2}{v_2} $$

Apparently, you were looking for a formula to compute $\binom{u}{ab}$. If $u = a^{n_0}ba^{n_1}b \dotsm a^{n_{k-1}}ba^{n_k}$, then $$ \binom{u}{ab} = \binom{a^{n_0}ba^{n_1}b \dotsm a^{n_{k-1}}ba^{n_k}}{ab} = n_0 + (n_0 + n_1) + \dotsm + (n_0 + n_1 + \dotsm + n_{k-1}) $$ Finally, if I am not wrong, $$ \binom{(ab)^n}{(ab)^m} = \binom{n+m}{2m} $$