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.

Given an $n$ letter string of identical letters, how many $k+2$ letter words can be formed of adjacent letters?

By observing data I came up with n-(1+k), but I'm at a loss for a descent combinatorial explanation.

For example, if I had a 5 letter string and k=1 and I label the letters for clarity: 'abcde' I get 'abc', 'bcd', 'cde'.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

If I understand the problem correctly, each word is uniquely determined by the position of its first letter. The rightmost word's first letter will be in the $n-(1+k)$ position, and each letter before that also determines a word, so there are exactly $n-(1+k)$ in total.

share|improve this answer

If you don't require all the words to be different, (i.e. if you take abcabc then you have 'abc' twice), then any word is determined uniquely by the letter you start with. You can start with any letter, such that there are at least $k+1$ letters after it before the end of the string, so you have $n-(k+1)$ starting points.

share|improve this answer
    
Note that the letters are all identical, so the words can only be different in their positions. –  AMPerrine Jun 13 '12 at 14:59

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.