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.