Da dove viene la base in un conteggio successivo?

Question

Se la sequenza X ha simboli m, quindi X ha 2 ^{M possibili successive.}

Da dove viene la base (2)?

L'origine di questa domanda è il seguente paragrafo:

.

Abbiamo dato due sequenze ordinate di simboli, e desideriamo trovare una più lunga successiva successiva di $ x $ e $ Y $ .

Una successiva di $ x $ è solo $ x $ con alcuni (o possibilmente tutti o nessuno) dei suoi elementi rimossi. Ad esempio, una successiva di A; B; C; D; E; F; G sarebbe B; C; E; G.

la lunghezza di un più lungo Comune successiona di $ x $ e $ y $ dà una misura di quanto siano simili questi Due sequenze sono. Ad esempio, se le due sequenze sono coppie di base in Fili di DNA, quindi potremmo considerarli simili se hanno un lungo successive comuni.

Se $ x $ ha $ m $ simboli e $ Y $ ha $ n $ simboli, quindi $ x $ e $ y $ avere $ 2 ^ m $ e $ 2 ^ n $ possibili successive rispettivamente.

Answer 1

Puoi pensare a una successiva $ y $ di $ x $ come un caratteristico vettore < class="container math"> $ \ chi_y $ che ha $ m $ elementi, uno per elemento di $ X $ . La $ I $ -th elemento di $ \ chi_y $ è $ 1 $ Se la $ i $ -th elemento di $ x $ è anche in $ y $ e $ 0 $ altrimenti.

È facile vedere che questa è una Biject: ogni successiva $ y $ ha una caratteristica caratteristica distinta $ \ chi_y $ , e ogni caratteristico vettore $ \ chi_y $ è associato a una sequenza distinta $ y $ .

significa che il numero di successive $ y $ è uguale al numero di vettori $ \ chi_y $ . Dal momento che ogni vettore $ \ chi_y $ ha $ m $ elementi, ognuno dei quali può avere uno < class="container di matematica"> $ 2 $ Valori possibili, questo numero è $ 2 ^ m $ .

Un esempio concreto di una sequenza $ x $ , una successiva $ y $ , e la sua caratteristica Vector $ \ chi_y $ è il seguente: