# Generalisation of Binomial Coefficient (Combinatorics on words)

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}$

• If there is a question here, I can't find it. What are you talking about? May 1, 2015 at 9:19
• Could you put your question in words? It is not clear what you are asking. May 1, 2015 at 9:21
• @GerryMyerson is it better now? May 1, 2015 at 9:24
• But what is strange about there being $5$ occurrences of "ab" as a subword of "abracadabra"? May 1, 2015 at 9:30
• No. "I have this strange property" --- I don't see where you have stated any property, strange or otherwise. I don't know what you mean by "factorial?" In the formula, $\|na\|\|nb-1\|$, I don't know what $n$ stands for, I don't know what $a$ stands for, I don't know what $b$ stands for, and I don't know what $\|$ stands for. And I don't know what it is that you are trying to find a general formula for. May 1, 2015 at 9:30

## 1 Answer

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}$$