Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
Thanks M. Piau. – brkn Dec 14 '11 at 22:58

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

share|cite|improve this answer
Thank you mercio. – brkn Dec 14 '11 at 22:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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