# Solving a recursion for polynomials defined by a matrix product

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.

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).