number of ways you can partition a string into substrings of certain length Hi I am trying to teach myself combinatorics, and cannot figure out an expression number of ways you can partition a string of length $n$ into sub-strings of length at most $r$. Any help would be great, thanks!
That is for example abcd and $r=2$ could be partitioned into a|b|c|d, ab|c|d, ab|cd, a|bc|d
 A: Let $C_{n,r}$ be the counting we are looking for: partitions of a string of length $n$ into parts with length up to $r$. This set can be divided according to the length of the last segment. 
But the number of such partitions ending with a segment of length $k$ equals the number of partitions of the prefix string, of length $n-k$ (always with the same restriction). And then we have  the recursive expression:
$$C_{n,r} = C_{n-1,r}+C_{n-2,r}+\cdots + C_{n-r,r}=\sum_{k=1}^r C_{n-k,r}$$with the initial conditions $C_{0,r}=1$ and $C_{j,r}=0$ for $j<0$. 
This is the expression of generalized Fibonacci numbers (plain Fibonacci numbers if $r=2$), sometimes called r-step Fibonnaci numbers.
For example, for $r=4$ we get (starting from $n=0$) the tetranacci numbers: $1,1,2,4,8,15,29,56 \cdots$
Notice that, for $n\le r$ we get $C_{n,r}=2^{n-1}$, which should be obvious (all the partitions are valid).
The general value $C_{n,r}$ has no simple form. One formula:
$$ C_{n,r} = {\rm round}\left(\frac{z^{n-1}(z-1)}{(r+1)z -2 r}\right)$$
where $z$ is the root of $x+x^{-r}=2$ near $x=2$ (can be obtained numerically by iterating $z_{t+1}=2 - z_{t}^{-r}$, starting from $z_0=2$) and ${\rm round}(\cdot)$ returns the nearest integer.
An asymptotic for large $n$ can be
$$ C_{n,r} \approx 2^{n-1}(1-2^{-r})^{n/2}$$
