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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.