Words that are "raised above" the decreasing word $(n)(n-1) \cdots (2)(1)$.

33 Views Asked by At

Let $\mathscr{W}_n$ be the set of words of length $n$, that is, the set of ordered, length $n$ sequences of non-negative integers. I'm interested in words $w \in \mathscr{W}_n$ that satisfy the condition $$ w_i \geq n + 1 - i \quad\text{ for all } 1 \leq i \leq n $$ where $w_i$ denotes the $i$th letter in $w$. In other words (no pun intended), words that are weakly greater than the word $(n)(n-1)(n-2)\cdots(2)(1)$ entry-wise. For example, the word $4623$ satisfies the condition while $4263$ does not (since the second letter is strictly less than $3$). Note that the word need not be decreasing and that there is no upper bound on the letters. Does this condition have a name? If so, in what contexts does this condition appear?

For context, I am interested in the graph you get by letting these "raised" words be the vertices and adding an edge between $w$ and $u$ if you can get from $w$ to $u$ by swapping the $i$th and $i+1$th entry of $w$.