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.


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}$.

  • $\begingroup$ Is there any other way not requiring knowledge about automatons? I know nothing about it. $\endgroup$ Oct 15 '16 at 14:13
  • $\begingroup$ You can set up a linear system of difference equations $\endgroup$ Oct 15 '16 at 14:19
  • $\begingroup$ 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. $\endgroup$ Oct 15 '16 at 14:25
  • $\begingroup$ Thank you for your answer, but I really don't understand it, because it is so complex to me, because I don't know much about generating functions. I don't need explicit formula, some kind of recursion would suffice. $\endgroup$ Oct 15 '16 at 15:02
  • 6
    $\begingroup$ @MatthewQuartz: Note that this is a research level site, so you should expect answers to assume a research level knowledge of a field. If that's not what you want, then math.stackexchange.com might be a better site for your question. $\endgroup$ Oct 15 '16 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.