1
$\begingroup$

What is the maximum number of the distinct subwords of the word AXIOMATIZABLE?

The answer is 88. But how?

  • 3
    There are 120 ways to rearrange the letters in AXIOM so I'm not sure how this could be 88 - what counts as a "subword"? If only actual English words count as subwords, then this isn't really a mathematics problem. Also, what does the phrase "Universal binary operation and finite fields (ring)" have to do with the question as stated?2012-01-31

1 Answers 1

6

If I am counting right (this is the weak part of the argument!), our word has $13$ letters. If all the letters were different, there would be $1$ subword of length $13$, $2$ of length $12$, and so on up to $13$ of length $1$, for a total of $1+2+\cdots +13$. By the usual formula, or by addition, this sum is $91$.

However, there are some repeated subwords, all of length $1$, three A's and two I's. So we should subtract $2$ for the extra A's, and $1$ for the extra I. The result is indeed $88$.

Remark: A subword of the word $W$ is a string of letters that are consecutive in $W$. Permuting is not allowed.

Being a mathematician, I think that there are $89$ distinct subwords. This is because I count the empty word as a word; shouldn't everybody?

  • 1
    @Ashish: A subword of a word consists of $0$ or more letters that are *consecutive* in the word. So XT is not a subword of AXIOMATIZABLE. Formally, $V$ is a subword of W if there exist words P and Q, possibly empty, such that W=PVQ. Here by PVQ is mean the concatenation, so write the word P, follow it by V, follow that with Q. So for example, let W be MATHEMATICS. Then TICS is a subword of W. Here P is MATHEMA, V is TICS, and Q is the empty word. Also, THEMAT is a subword of W, here P is MA and Q is ICS. HA is not a subword of W, the letters H and A don't appear consecutively in W.2012-02-02