In how many ways can you split a string of length n such that every substring has length at least m?

Question

Suppose you have a string of length 7 (abcdefg) and you want to split this string in substrings of length at least 2.

The full enumation of the possibilities is the following:

ab/cd/efg
ab/cde/fg
abc/de/fg
abc/defg
abcd/efg
abcde/fg
abcdefg

And perhaps some others.

In general, if we have a string of length n and we want to split the string in substrings of length at least m, in how many ways can we achieve this?

Answer 1

Let $f(n,m)$ denote this number. Clearly, $f(n,m)=0$ if $n<m$ with the exception that $f(0,m)=1$ for all $m$. For $n>m$ we have $$ f(n,m)=\sum_{k=m}^nf(n-k,m)$$ It may be simlre when counting by number of substrings: To split into $r$ substrings is the same as to split $n-rm$ into $r$ nonnegative summands, which is possible in exactly $n-rm+r\choose r-1$ ways ("stars and bars"). Thus we find $$ f(n,m)=\sum_{r=1}^{\infty}{n-r(m-1)\choose r-1}\qquad\text{if }n\ge m>0.$$