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:

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

how many possibilities are there for dividing it to substrings?
for example:
$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:
$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 $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:
$S=\sigma_1\sigma_2... \sigma_n$
how many possibilities are there for dividing it to substrings?
for example:
$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: $S_1=\sigma_1 \hspace{12pt}S_2=\sigma_2...\sigma_n$
is another. how many like that are there?
Here is one string $S=\sigma_1\sigma_2... \sigma_n$.

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

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

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

In fact you can put as many as $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 $\sum_{k=0}^{n-1}\binom{n-1}{k}$, which is $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 $\sum_{k=0}^{n-1}\binom{n-1}{k}$, which is $2^{n-1}$.
Yes exactly.
It is well known that $\sum_{k=0}^{N}\binom{N}{k}=2^{N}$.
That is the number of subsets of a set of N elements.