I am trying to figure out the formula that gives the exact number of left-to-right combinations in which a word can be segmented. For example, the word cat has 4 possible segmentation combinations:
- cat
- c at
- ca t
- c a t
I am not interested in the cases in which letters are scrambled; all combinations of a given words must have the same letter order (from left to right), but different ways to be segmented.
If I am not mistaken, the formula to get the total number of segments should be something like this (apologies for any mistakes in what follows):
∑(i+(i+1)+...k), where i=1 and k is the number of letters of the word
but I don't seem to be able to figure out the formula for the number of segmentations these segments may make up to form the actual word.
Does it make sense? Thank you in advance!
The letters are fixed, and between each letter there either is a separator between two segments or no separator. For an $n$-letter word there are $n-1$ places where such separators can lie, and hence $2^{n-1}$ segmentations.
At least in this case, there is no need for the sum you propose to count to the segmentations.