I'm trying to solve the following recurrence relation in two natural number variables $m$ and $k$, where $m \geq k$: $$a_{m,k} = (n+k)a_{m-1,k} + a_{m-1,k-1}$$ with initial conditions $a_{m,0} = n^m$, $a_{m,m}=1$ (and $a_{m,k}=0$ for $m < k$). Here, $n$ is a fixed parameter.
So far I have worked out that $a_{m,k} \in O(n^{m-k})$ and is polynomial in $n$, and the special case $a_{m,m-1} = mn + T_{m-1}$, where $T_j$ is the $j$th triangular number. It also seems that $a_{m,m-2}$ has leading term $T_{m-1}\, n^2$.
I tried to solve for the generating function $G(x,y) = \sum_{k \leq m} a_{m,k} x^m y^k$, and got the partial differential equation $$xy\, \dfrac{\partial G}{\partial y}\ +\ (nx + xy - 1)\, G(x,y)\ +\ 1\ =\ 0$$ which I am also unsure how to solve. (This may be incorrect by a constant factor, I'm not sure).
How can I proceed to get (ideally) a closed-form expression for the $a_{m,k}$?
Note for context: $a_{m,k}$ counts the number of $k$-variable words of length $m$ over an alphabet $A$ of $n$ letters, i.e. elements of $(A \cup \{ x_1, \ldots, x_k \})^*$ where all the $x_i$ appear, and their first appearances are in increasing order. Such words arise in Ramsey theory, in the Graham--Rothschild theorem.
I will change your combinatorial problem to be equivalent to the number of partitions of $[m+n]$ into $n+k$ blocks in which the first $n$ numbers are in different blocks. This is a well known problem in Combinatorics.
Notice that this is still your problem but were the variables are giving us the name of the block and the position are the elements to be partitioned.
The name of these numbers are $r-$ Stirling of the second kind and they have the following closed form $$\sum _{r=0}^m\binom{m}{r}{m-r\brace k}n^{r}$$ where you decide how many elements are in the first $n$ blocks and you control that number by $r,$ so you choose the ones from the set $[m+n]\setminus[n]$ and then use a function to place them in the first $n$ blocks, the remaining $m-r$ you put them in $k$ distinct non empty blocks(this is done by the Stirling numbers of the second kind, denoted by ${n\brace k}$).
Edit: Let $A=\{a_1,\cdots ,a_n\}$ then let $w$ be a word of your interest. Consider the set $A_j=\{j\}\cup \{i+n:w_i=a_j\}$ and the set $X_j=\{i+n:w_i=x_j\}$ and so the partition $\pi _w$ as $\pi _w =\{\underbrace{A_1,\cdots ,A_n}_{\text{special first $n$ blocks}},X_1,\cdots X_k\}.$ Notice that they are not ordered by the condition of appearance and they are not empty. Notice further that this indeed is a partition of $[m+n].$
For example: let $m=6,k=3,n=2$ and the word $x_1\color{blue}{a_2}x_2x_3x_2\color{blue}{a_1}$ this would correspond to $\color{blue}{1}8/\color{blue}{2}4/3/57/6$ where the slashs are separating the blocks.