Come calcolare il numero totale di successioni di lunghezza k da una parola di lunghezza n?

Question

Una successione di una parola si ottiene lasciando alcune lettere da essa. Le lettere che vengono eliminate non devono essere consecutive. Ad esempio, BA, BNA e Banaa sono tutte sottosequenze della parola banana. Siamo interessati a contare il numero di successioni distinte di una lunghezza fissa di una determinata parola. Ad esempio, la parola banana ha 11 diverse sottosequenze di lunghezza 3: {AAA, Aan, Ana, Ann, Baa, Ban, BNA, BNN, NAA, NAN, NNA}. Osservare che il numero di sottosequenze della lunghezza K di AbcBBcaab che si terminano in una "C" è lo stesso del numero di successioni di lunghezza K - 1 di ABCBBCAA. In ciascuno dei seguenti casi, ti viene data una parola e un numero N. Devi calcolare il numero di diverse successioni di lunghezza n della parola data. (a) Acufene, 3 (b) Gobbledygook, 4 (c) Gargantuan, 5