# Thread: How many possibilities are there for dividing a string to substrings, of any length?

1. ## How many possibilities are there for dividing a string to substrings, of any length?

Hi.
I just can wrap my head around this.

Let S be a string of length n:

$\displaystyle S=\sigma_1\sigma_2... \sigma_n$

how many possibilities are there for dividing it to substrings?
for example:
$\displaystyle S_1=\sigma_1\sigma_2\hspace{12pt} S_2=\sigma_3...\sigma_i\hspace{12pt} S_3=\sigma_{i+1}...\sigma_n$
is one division, and:
$\displaystyle S_1=\sigma_1 \hspace{12pt}S_2=\sigma_2...\sigma_n$
is another.
how many like that are there?

I can't think of anything and could really use some help here.
Thanks in anvanced!

2. ## Re: How many possibilities are there for dividing a string to substrings, of any leng

Never mind...
found it.
It's $\displaystyle 2^{n-1}$

3. ## Re: How many possibilities are there for dividing a string to substrings, of any leng

Originally Posted by Stormey
Let S be a string of length n:
$\displaystyle S=\sigma_1\sigma_2... \sigma_n$
how many possibilities are there for dividing it to substrings?
for example:
$\displaystyle S_1=\sigma_1\sigma_2\hspace{12pt} S_2=\sigma_3...\sigma_i\hspace{12pt} S_3=\sigma_{i+1}...\sigma_n$
is one division, and:$\displaystyle S_1=\sigma_1 \hspace{12pt}S_2=\sigma_2...\sigma_n$
is another. how many like that are there?
Here is one string $\displaystyle S=\sigma_1\sigma_2... \sigma_n$.

You gave another: $\displaystyle S_1=\sigma_1{\color{red}|}~S_2=\sigma_2... \sigma_n$

We can "move" the $\displaystyle {\color{red}|}$ to $\displaystyle n-2$ positions on the original string to get a total of $\displaystyle n-1$ decompositions of into two strings.

Now put two $\displaystyle {\color{red}|,~|}$ to $\displaystyle \binom{n-1}{2}$ positions on the original string to get a total of $\displaystyle \binom{n-1}{2}$ decompositions of into three strings.

In fact you can put as many as $\displaystyle n-1$ of those red bars into the original string. Add them up.

4. ## Re: How many possibilities are there for dividing a string to substrings, of any leng

Hi Plato, thanks for the help.

according to what you're saying, it's $\displaystyle \sum_{k=0}^{n-1}\binom{n-1}{k}$, which is $\displaystyle 2^{n-1}$.

5. ## Re: How many possibilities are there for dividing a string to substrings, of any leng

Originally Posted by Stormey
according to what you're saying, it's $\displaystyle \sum_{k=0}^{n-1}\binom{n-1}{k}$, which is $\displaystyle 2^{n-1}$.
Yes exactly.
It is well known that $\displaystyle \sum_{k=0}^{N}\binom{N}{k}=2^{N}$.
That is the number of subsets of a set of N elements.