What is the generating function for these word types?

Question

I'm curious to see what the generating function is for numbers of some words with a few constraints.

Let's fix some $m$, and I'll denote by $[m]$ the set of $m$ symbols, say $\{1,2,\dots,m\}$. Now let $w(n,m)$ be the number of words of length $n$ whose symbols are in $[m]$, with the extra conditions that

• each symbol occurs at least once in the word,
• for every $k$, each of $1,2,\dots,k-1$ appears at least once to the left of the first $k$.

Is there some way to describe explicitly the ordinary generating function $$ F_m(x)=\sum_n w(n,m)x^n? $$

Thank you.

Answer 1

If $m\geqslant2$, any admissible word $W$ on $[m]$ is $W=W'mW''$ where $W'$ may be any admissible word on $[m-1]$ and $W''$ may be any word on $[m]$. If the length of $W$ is $n$ and the length of $W'$ is $n-k$, there are $w(n,m)$ such words $W$, $w(n-k,m-1)$ such words $W'$ and $m^{k-1}$ such words $W''$, hence $$ w(n,m)=\sum\limits_{k=1}^{n-m+1}m^{k-1}w(n-k,m-1). $$ Summing this over $n\geqslant m$, one gets $$ F_m(x)=\sum\limits_{n\geqslant m}w(n,m)x^n=\sum\limits_{n\geqslant m}\sum\limits_{k=1}^{n-m+1}m^{k-1}w(n-k,m-1)x^n, $$ hence $$ F_m(x)=\sum\limits_{k\geqslant1}m^{k-1}x^k\sum\limits_{n\geqslant k+m-1}w(n-k,m-1)x^{n-k}=x(1-mx)^{-1}F_{m-1}(x). $$ Since $w(n,1)=1$ for every $n\geqslant1$, $F_1(x)=x(1-x)^{-1}$. Finally, for every $m\geqslant1$, $$ F_m(x)=x^m\prod\limits_{k=1}^m(1-kx)^{-1}. $$

Answer 2

A word counted in $w(n,m)$ is of the form $1\cdot w_1 \cdot 2 \cdot w_2 \cdot 3 \cdot w_3 \cdots m \cdot w_m$ where $w_i$ is any word whose symbols are in $[i]$. So as a language, you are looking at $1[1]^*2[2]^*3[3]^* \ldots m[m]^*$

The generating function the language $[i]^*$ is $\sum i^n x^n = (1-ix)^{-1} $, and the generating function for the language $\{i\}$ is $x$.

Since the generating function of a concatenation of languages is the product of the generating functions of the languages, the generating function for $w(n,m)$ is $F_m(x) = x^m \prod_{i=1}^m (1-ix)^{-1} $