Question: Assume I want to form a sequence in which the numbers $1, 2, ..., m$ occur $k$ times each. Hence, the length of the sequence is $mk$.
We have the following constraint: the $j$th occurrence of "$2$" must be preceded by at least $j$ occurrences of "$1$", and the $j$th occurrence of "$3$" must be preceded by at least as many "$2$"s, and so forth. How do I count the number of valid sequences?
For example, valid sequences would be $ 123123 $ or $112233$. However, $1221$ is invalid, because the second "2" appears before we have seen a second "1". $123465$ is also invalid.
Update: Solution: I was pointed to the following post, which answers my question: Generalized Dyck words with alphabet of size $k$ (note that Generalized Dyck words are precisely the sequences that I define above).
Equivalent problems: Perhaps this distracts from the main problem, but I found it interesting to note that the same problem can be phrased in at least 2 different ways:
- Assume I have $n$ sites, of which the rightmost $m$ are occupied by a boulder. I am to move all boulders to the $m$ leftmost sites, and displacing a boulder by 1 site costs one unit of time. There cannot be two boulders at one site. In how many ways can I (optimally) do this?
Clearly the total units of time is fixed at $(n-m)m$, as I have to move all $m$ boulders over $(n-m)$ sites. We could write every valid solution by a sequence of numbers, writing a digit $b \in \{1....m\}$ if we move the $b$'th boulder, leading to the main problem above. Compared to the main problem, $k=(n-m)$.
- How many random walks on an $m$-dimensional grid, going from (0,0,..,0) to (k,k,...,k) in $mk$ steps, stay within the region defined by $x_2 \leq x_1$, and $x_3 \leq x_2$, etc.
Here, a number $b$ in a valid sequence from the main problem is interpreted to denote unit steps in the $b$'th dimensions of the grid.
This question arose in a quantum mechanics problem; although the question sounds deceptively simple, I have not even been able to even find reasonable bounds.