subsequence of a string

alpar · P versus NP Offline Joined: 25 Jan 2008 Posts: 21

We have a string with $n$ characters.How many subsequences can i produce with this string?

is this a permutation?

**Posted:** Wed Nov 04, 2009 9:27 am

mavropnevma

For one thing, this is not a Calculus question, but Combinatorics.
For seconds, it is not a permutation, for sure.

Let the sequence be $(x_k)_{k=1,2,\ldots,n}$ . If by subsequence you mean (as you should) a sequence $(x_{k_m})_{m=1,2,\ldots,s}$ , then there are as many subsequences as non-empty parts of $\{1,2,\ldots,n\}$ , hence $2^n - 1$ . If you mean subsequences made by consecutive elements, there are $n+(n-1)+\cdots+2+1 = \frac {1} {2} n(n+1)$ .

**Posted:** Wed Nov 04, 2009 10:12 am

_________________
Listen to REMBETIKA for decoding the handle.

alpar · P versus NP Offline Joined: 25 Jan 2008 Posts: 21

**Posted:** Wed Nov 04, 2009 10:19 am

mavropnevma

Then it's $2^n - 2$ (we should not count the empty subsequence, nor the full sequence).

**Posted:** Wed Nov 04, 2009 10:29 am

_________________
Listen to REMBETIKA for decoding the handle.

alpar · P versus NP Offline Joined: 25 Jan 2008 Posts: 21

**Posted:** Wed Nov 04, 2009 11:06 am

mavropnevma

**Posted:** Wed Nov 04, 2009 11:13 am

_________________
Listen to REMBETIKA for decoding the handle.

alpar · P versus NP Offline Joined: 25 Jan 2008 Posts: 21

why not count the empty subsequence?
if we remove all characters we have the null sequence

**Posted:** Sat Nov 07, 2009 11:59 am