Can we model the number of increasing words as ball-and-urn problem?

Question

Let the ball-and-urn problem be defined as follows:

How many ways can one distribute $k$ [in]distinguishable balls into $n$ [in]distinguishable urns?

Let the problem of increasing words be defined as follows:

How many increasing words of length $x$ over an alphabet of $y$ letters exist? An increasing word is given if the letters are, alphabetically ordered, monotonically increasing. An increasing word is aabz, but abaz is not increasing.

My question is: Given a problem of increasing words, can we model it as ball-and-urn problem?

My initial ideas: Any ball-and-urn problem uses balls and distributes those among the urns. There is no possibility to impose a constraint which ball or urn is chosen next. As such all balls and urns can be chosen next unlike the increasing words problem. With that problem we have valid/invalid elements to chose from based on the decisions in the past (if z was chosen as first letter, only z can follow, assuming $y=26$). So naturally, those problems are different, but maybe I miss some encoding which models those constraints in a different way.

Answer 1

Yes, there is a natural mapping of the number of ways to distribute $x+y-1$ identical balls into $x+1$ distinguishable urns and the nondecreasing words. We are interested in the number of distributions, not the number of orders we can distribute the balls.

First, let us consider strictly increasing words. The number of strictly increasing words on $y$ characters of length $x$ is just $y \choose x$ because once you choose the characters to use you have the word. To get the the number of weakly increasing words of length x out of y characters, move the second character right one in the alphabet, the third right two, and so on. The alphabet expands to $y+x−1$ characters and you choose $x$ of them, then reverse the shift, so there are $y+x−1\choose x$ of them.

This is the same as having $x+y$ stars and putting $x$ bars between them. The bars separate the boxes, so you have $x+1$ boxes and put $x+y$ balls in them, requiring at least one ball in every box. Then you remove one ball from every box, leaving $y−1$ balls. We have a correspondence with the sequences of length $x+1$ that sum to $y−1$

Answer 2

Put an empty character (value =0) at the beginning of the word. Then consider the non-decreasing words of length $x$ that can be made with the characters $c_n$ taken from the alphabet $\{1,2,\cdots,y \}$.
Consider the sequence of the "backward Deltas": $d_n=c_n-c_{n-1}$. You will have that $$ \left\{ {\matrix{ {0 \le d_{\,n} \le y} \hfill \cr {0 \le \sum\limits_{1\; \le \,n\, \le \,x} {d_{\,n} } = c_{\,x} \le y} \hfill \cr } } \right. $$

$c_x$ being the last character in the word.

That corresponds to the number of ways of laying $c_x$ undistinguishable balls into $x$ distinguishable bins. Or adding a bin for the "remainder", to the number of ways of laying $y$ undist. balls into $x+1$ dist. bins.

You may be interested to know that there is a nice formulation for the more general case of words of length $x$, from the alphabet $\{1, \cdots, y\}$, containing $m$ strictly increasing sequences.
The case of "non-decreasing " sequences can be easily derived from that.