0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Is there any other way not requiring knowledge about automatons? I know nothing about it. $\endgroup$
    – Matthew Quartz
    Commented Oct 15, 2016 at 14:13
  • $\begingroup$ You can set up a linear system of difference equations $\endgroup$
    – Benjamin Steinberg
    Commented Oct 15, 2016 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$
    – Benjamin Steinberg
    Commented Oct 15, 2016 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$
    – Matthew Quartz
    Commented Oct 15, 2016 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$
    – Nate Eldredge
    Commented Oct 15, 2016 at 18:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .