# How many words are there such that some word $X$ is subsequence of them?

Let's define subsequence of the word as part of the word created by deleting some of its letters, for example aetics is a subsequence of mathematics.

QUESTION.

Given a $3$-letter word (let's call it $X$) I want to know how many words consisting of exactly $k_A$ letters $a$, $k_B$ letters $b$, ..., $k_Z$ letters $z$ are there such that $X$ is subsequence of it?

For example, if $k_A = 1, k_B = 1, k_C = 1, k_D = 1, k_E = 0, ..., k_z = 0$, and $X = abc$, then there are $4$ such words.

Given any word $w$ of length $k$ one can build by a standard method a deterministic automaton with $k+1$ states recognizing all words with $w$ as a subsequence. State $1$ is initial, state $k+1$ is final and the edge from $i$ to $i+1$ is labeled by letter $i$ if $w$. All other edges are loops. So each node has $m-1$ loops except node $k+1$, which has $m$ loops where $m$ is the alphabet size. Then you can use Schutzenberger's method to express the generating function you want as a rational function.
If I am doing the computation correctly I get if your alphabet has size $m$ then you get generating function $x^k/(1-(m-1)x)^k(1-mx)$.
Update. I realize I read the question too quickly and you want to control the number of occurrences of each letter. Then you need to do a multivariable generating function. This will depend on the letters in $w$ but is done the same way. So in your example if the alphabet is $a,b,c,d$ and $w=abc$, then the multivariate generating function is $$\frac{x_ax_bx_c}{(1-(x_b+x_c+x_d))(1-(x_a+x_c+x_d)(1-(x_a+x_b+x_d))(1-(x_a+x_b+x_c+x_d))}$$ where $x_a$ is the variable corresponding to $a$, etc. Then you need to look at the coefficient of $x^{k_a}x^{k_b}x^{k_c}x^{k_d}$.
• Keeping my notation, draw a digraph with $k+1$ nodes with a $m-1$-loops at each node except the last, which has $m$ loops, and an arc from node $i$ to node $i+1$. The edge from $i$ to $i+1$ is labelled by letter $i$ of $w$. The loops are labelled by the remaining letters. Then I claim that words containing $w$ as a subsequence are in bijection with labels of directed paths from node $1$ to node $k+1$ which is bijection with directed paths from node $1$ to node $k+1$. One counts these using the transfer method in Stanley's book. Oct 15 '16 at 14:25