I just can wrap my head around this.
Let S be a string of length n:
how many possibilities are there for dividing it to substrings?
is one division, and:
how many like that are there?
I can't think of anything and could really use some help here.
Thanks in anvanced!
You gave another:
We can "move" the to positions on the original string to get a total of decompositions of into two strings.
Now put two to positions on the original string to get a total of decompositions of into three strings.
In fact you can put as many as of those red bars into the original string. Add them up.