self doubt

Question

For longest common subsequence the total number of subsequence possible for the word DIYA should be 2^4 or (2^4)-1??Please explain.

Comments

Could you explain how you feel it as either 2^4 or 2^4-1 because i feel it should be 4*(4-1)/2 i.e i think the number of subsequences should be 6

---

every letter may or may not occur so each letter has 2 chances D=2,I=2,Y=2,A=2 now  the number of possible subsequences are 2*2*2*2 and in this there is one element in which no letters are selected so that is to be subtracted thats how I got 2^4-1

Answer 1

D I Y A

D, DI, DY, DA, DIY, DIA, DYA, DIYA

I, IY, IA, IYA

Y, YA

A

null ( 0 length)

HERE we can see total 16 subsequences are possible.

there is a difference between sub-string and subsequence, sub-string should be continuous but subsequence may or may not be.

so, string length = n

total subsequences possible = 2$^{n}$

Comments

AND THE 16TH OPTION WOULD HAVE BEEN THAT NONE OF THE LETTERS ARE INCLUDED(NULL STRING).

---

@DIYA BASU

yes, you are right.

then total subsequences become 2$^{n}$

and if asked about only non-trivial then it becomes 2$^{n}$ - 2.