How to compute total number of subsequences of length k from a word of length N?

Question

A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all subsequences of the word banana. We are interested in counting the number of distinct subsequences of a fixed length of a given word. For example, the word banana has 11 different subsequences of length 3: {aaa, aan, ana, ann, baa, ban, bna, bnn, naa, nan, nna}. Observe that the number of subsequences of length k of abcbbcaacaab that end in a ‘c’ is the same as the number of subsequences of length k−1 of abcbbcaa. In each of the following cases, you are given a word and a number N. You have to compute the number of different subsequences of length N of the given word. (a) tinnitus, 3 (b) gobbledygook, 4 (c) gargantuan, 5