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.


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


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


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.