Solving a recursion for polynomials defined by a matrix product

Question

Define the polynomial $p_n(X) \in \mathbb{Z}[X_1,...,X_n]$ as the top left entry in $A^n$ for the $(d \times d)$ matrix \begin{align*} & A = \left(\begin{matrix} X_1 & \dots & \dots & X_d\\ 1 & 0 & \dots & 0\\ & \ddots & \ddots & \vdots \\ 0 & & 1 & 0 \end{matrix}\right) \ . \end{align*} For any $d \geq n$ this entry $p_n(X) = (A^n)_{1,1}$ will be the same, so the definition is somewhat independent of $d$. I find the recursive formula \begin{align*} & p_n(X) = \sum\limits_{i=1}^{n \land d} X_i p_{n-i}(X) \overset{(d \geq n)}{=} \sum\limits_{i=1}^{n} X_i p_{n-i}(X) \end{align*} for $p_0(X)=1$ by the observation that the vector $A^n e_1 \in \mathbb{Z}[X_1,...,X_d]^d$ will have the form $(p_n(X),p_{n-1}(X),...,p_0(X),0,...,0)^T$.

Question: Is there a nice explicit formula for $p_n(X)$ (when $d \geq n$) or does it fit nicely with some well-known polynomials?

If I haven't miscalculated, the first few polynomials are as follows: \begin{align*} & p_0 = 1\\ & p_1 = X_1\\ & p_2 = X_1^2 + X_2\\ & p_3 = X_1^3 + 2X_1X_2 + X_3\\ & p_4 = X_1^4 + 3 X_1^2X_2 + 2X_1X_3 + X_2^2 + X_4\\ & p_5 = X_1^5 + 4 X_1^3X_2 + 3X_1X_2^2 + 3X_1^2X_3 + 2X_1X_4 + 2X_2X_3 + X_5 \end{align*}

Any help is much appreciated!

---

Edit: It seems (at least simulations until $n=50$ confirm this) that the coefficient to a $X_1^{k_1} \cdots X_n^{k_n}$ is always either zero or ${k_1+...+k_n \choose k_1,...,k_n}$. All that would then be missing is a (non-recursive) rule for when the coefficients are zero.

Answer 1

Your polynomial is precisely $$ \sum_{k_1+2k_2+\cdots+nk_n=n}\binom{k_1+\cdots+k_n}{k_1,\ldots,k_n}X_1^{k_1}\cdots X_n^{k_n}. $$ The proof is straightforward by induction: you have $$ p_n(X)=\sum_{i=1}^nX_ip_{n-i}(X), $$ so the result follows from the usual recursive formula for multinomial coefficients (higher dimensional Pascal triangle).