0
$\begingroup$

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'.

2 Answers 2

2

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.

0

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.

  • 0
    Note that the letters are all identical, so the words can only be different in their positions.2012-06-13