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!

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}$

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.

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}$.

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.