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