Comment calculer le nombre total de sous-séquences de la longueur K à partir d'un mot de longueur n?

Question

Une sous-séquence d'un mot est obtenue en leur en laissant tomber des lettres. Les lettres qui sont abandonnées n'ont pas besoin d'être consécutives. Par exemple, BA, BNA et BANAA sont tous des sous-séquences du mot banane. Nous souhaitons compter le nombre de sous-séquences distinctes d'une longueur fixe d'un mot donné. Par exemple, le mot banane a 11 sous-séquences différentes de la longueur 3: {aaa, aan, ana, ann, baa, ban, bna, bnn, naa, nan, nna}. Observez que le nombre de sous-séquences de la longueur K d'ABCBBCAACAAB qui se termine par un «C» est le même que le nombre de sous-séquences de la longueur K - 1 d'ABCBBCAA. Dans chacun des cas suivants, on vous donne un mot et un nombre N. Vous devez calculer le nombre de sous-séquences différentes de la longueur n du mot donné. (a) acouphènes, 3 (b) Gobbledygook, 4 (c) gargantuesque, 5