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

• Nov 14th 2013, 06:14 AM
Stormey
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!
• Nov 14th 2013, 06:59 AM
Stormey
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}$
• Nov 14th 2013, 07:14 AM
Plato
Re: How many possibilities are there for dividing a string to substrings, of any leng
Quote:

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.
• Nov 14th 2013, 08:23 AM
Stormey
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}$.
• Nov 14th 2013, 08:39 AM
Plato
Re: How many possibilities are there for dividing a string to substrings, of any leng
Quote:

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.