Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

The answer is 88. But how?

share|improve this question
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? –  anon Jan 31 '12 at 15:23
add comment

1 Answer 1

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?

share|improve this answer
1  
+1; Empty word is a word. –  Quixotic Jan 31 '12 at 18:22
    
here XT is also a subword of length 2 but you dont count it why? –  Ashish Feb 2 '12 at 19:22
    
@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. –  André Nicolas Feb 2 '12 at 19:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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