# What is the number of words of length $h$ in a sequence of subsets of words?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given an integer $k$, and $S$ a finite subset of $L$ define recursively the following sequence of subsets of $L$: \begin{align} A_1 &=S\cup \{\epsilon\} \\ A_{n+1} &=\left\{\prod_{i=1}^ka_i^{n_i}\Big/a_i\in A_n, n_i\in \Bbb{N}\right\}\end{align}

My question:

For each integer $n$ there exists a polynomial $P$ such that the number of words of length $h$ in $A_n$ is less or equal to $P(h)$.

Example if $S=\left\{\epsilon,0,1\right\}$ and $k=2$ then $$A_2=\left\{\prod_{i=1}^2a_i^{n_i}\Big/a_i\in S \right\}=\left\{0^n1^m,1^n0^m/n,m\in\Bbb N\right\}$$ and the number of words of length $h$ is $2h+2$.

If $S$ is finite then I can prove that $A_2$ contains no more than $|S|\dbinom{|S|+k-1}{k-1}$, but how can I prove a similar result for $A_n$.

• Are you shure of your $k$ in the definition of $A_{n+1}$ (in the term $\prod_{i=1}^k\, a_i^{n_i}$) ? Apr 3, 2015 at 17:43
• Yes, every time we only use the product of $k$ elements and $k$ is fixed in the beginning so the sequence of subsets depends on $S$ and $k$ Apr 3, 2015 at 17:45
HINT: A word of length $h$ in $A_{n+1}$ is a composition of words of $A_n$, each of which must obviously have length at most $h$. There is a polynomial $P_n$ such that $A_n$ has at most $\sum_{i=0}^nP_n(i)$ words of length at most $h$, so you’re essentially working with an alphabet of size at most $\sum_{i=0}^nP_n(i)$.
• The problem is a word has lenght $h$ in $A_{n+1}$ if ond only if there exists $h_1n_1+\cdots+h_kn_k=n$ for some integers $n_i$ and words $w_i$ of lenght $h_i$ in $A_n$ and so : $$P_{n+1}=\sum_{(h_1,\cdots,h_k)}P_n(h_1)P_n(h_2)\cdots P_n(h_k) Numsol(h_1n_1+\cdots+h_kn_k=h)$$ Apr 3, 2015 at 18:12
• Do you mean that we can take $P_{n+1}=(\sum_{i=1}^nP_n(i))^k$ Apr 3, 2015 at 18:28
• @Elaqqad: No, it would be $P_{n+1}(h)=\left(\sum_{i=0}^hP_n(i)\right)^k$. Apr 3, 2015 at 18:35