0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ If there is a question here, I can't find it. What are you talking about? $\endgroup$ May 1, 2015 at 9:19
  • $\begingroup$ Could you put your question in words? It is not clear what you are asking. $\endgroup$ May 1, 2015 at 9:21
  • $\begingroup$ @GerryMyerson is it better now? $\endgroup$
    – grapher
    May 1, 2015 at 9:24
  • $\begingroup$ But what is strange about there being $5$ occurrences of "ab" as a subword of "abracadabra"? $\endgroup$
    – Casteels
    May 1, 2015 at 9:30
  • 1
    $\begingroup$ 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. $\endgroup$ May 1, 2015 at 9:30

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.