De onde vem a base em uma contagem de subsequência?

Question

Se sequência X tem m símbolos, então X tem 2^eu possíveis subsequências.

Onde fica a base (2) vem de onde?

A origem desta questão está no seguinte parágrafo:

Recebemos duas sequências ordenadas de símbolos e desejamos encontrar a maior subsequência comum de $X$ e $Y$.

Uma subsequência de $X$ é apenas $X$ com alguns (ou possivelmente todos ou nenhum) de seus elementos removidos.Por exemplo, uma subsequência de A; B; C; D; E; F; G seria B; C; E; G.

A duração de uma subsequência mais comum de $X$ e $Y$ fornece uma medida de quão semelhantes são essas duas seqüências.Por exemplo, se as duas seqüências forem pares de bases em fios de DNA, poderíamos considerá -los semelhantes se tiverem uma subsequência comum longa.

Se $X$ tem $m$ símbolos e $Y$ tem $n$ símbolos, então $X$ e $Y$ ter $2^m$ e $2^n$ Possíveis subseqüências, respectivamente.

Answer 1

Você pode pensar em uma subsequência $Y$ de $X$ como um vetor característico $\chi_Y$ isso tem $m$ elementos, um por elemento de $X$.O $i$-º elemento de $\chi_Y$ é $1$ se o $i$-º elemento de $X$ também está em $Y$ e $0$ de outra forma.

É fácil ver que isso é uma bijeção:cada subsequência $Y$ tem um vetor característico distinto $\chi_Y$, e cada vetor característico $\chi_Y$ está associado a uma sequência distinta $Y$.

Isso significa que o número de subsequências $Y$ é igual ao número de vetores $\chi_Y$.Como cada vetor $\chi_Y$ tem $m$ elementos, cada um dos quais pode ter um dos $2$ valores possíveis, esse número é $2^m$.

Um exemplo concreto de uma sequência $X$, uma subsequência $Y$, e seu vetor característico $\chi_Y$ é o seguinte: