# Closed-form formula for a multivariate polynomial

Counting certain walks in threshold graphs, I came to the following independent problem. Assume that $$x_1,\dots,x_a$$ are independent variables and for $$k\geq 2$$ let $$P_k(x_1,\dots,x_a)=\sum_{(i_1,\dots,i_k)\in\{1,\dots,a\}^k} x_{i_1} x_{\min(i_1,i_2)} x_{\min(i_2,i_3)}\cdots x_{\min(i_{k-1},i_k)} x_{i_k}.$$ Can you find the coefficient of the term $$x_{j_1}x_{j_2}\cdots x_{j_{k+1}}$$ for any given $$1\leq j_1\leq j_2\leq\dots\leq j_{k+1}\leq a$$, or better yet, a closed-form formula for $$P_k(x_1,\dots,x_a)$$? If this problem appeared elsewhere earlier, a reference is more than welcome.

• If I am not mistaken the coefficients in the simplest case $a=2$ are given by OEIS A105422. – Timothy Budd Nov 5 '20 at 7:23
• For $a=2$ the polynomial is $\sum_i x_i^3 + \sum_{i<j} 2x_i^2x_j$. Hence each coefficient is either 0, 1 or 2, depending on the number of distinct values among the selected indices $j_1, j_2, j_3$. – Dragan Stevanovic Nov 5 '20 at 19:37
• What you are talking about is $k=2$, right? – Timothy Budd Nov 5 '20 at 19:53
• Right, that was $k=2$. The coefficients for $a=2$ indeed look like the sequence you mention. – Dragan Stevanovic Nov 6 '20 at 18:37

Let $$F_a(t) = \sum_{k\geq 0}P_{k+2}(x_1,\dots,x_a)t^k$$. By a transfer-matrix argument, this is a rational function of $$t$$ (whose coefficients are polynomials in the $$x_i$$'s). More specifically, let $$A_a$$ be the matrix whose rows and columns are indexed by pairs $$(i,j)$$, with $$1\leq i,j\leq a$$, defined by $$(A_a)_{(i,j),(m,n)} = \left\{ \begin{array}{rl} 0, & \mbox{if}\ j\neq m\\ x_{\min(m,n)}, & \mbox{if}\ j=m. \end{array} \right.$$ Let $$u$$ be the row-vector (indexed by the same pairs as for $$A$$) with $$(i,j)$$-entry $$x_ix_{\min(i,j)}$$. Let $$v$$ be the column vector with $$(i,j)$$-entry $$x_j$$. Then $$F_a(t) = u(I-tA)^{-1}v.$$ (More precisely, the right-hand side is a $$1\times 1$$ matrix whose entry is $$F_a(t)$$.) I doubt whether there will be a nice formula for the coefficients $$P_{k+2}(x_1,\dots,x_a)$$.
For instance, when $$a=3$$ we get (writing $$x_1=b,x_2=c,x_3=d$$), $$F_3(t) = \frac{b^3+2b^2c + 2b^2d + c^3 + 2c^2d + d^3+Q_1t+Q_2t^2} {1-(b+c+d)t-(2b^2+bc+bd-c^2+cd)t^2+(b^2d-b^2c+bc^2-bcd)t^3},$$ where $$Q_1=2b^4 - b^3c - b^3d + 3b^2c^2 + b^2d^2 - bc^3 - 2bc^2d - bd^3 + c^4 - c^3d + c^2d^2 - cd^3$$ and $$Q_2=b^4c - b^4d - b^3c^2 + b^3cd + b^2c^3 - b^2c^2d + b^2cd^2 - b^2d^3 - bc^4 + bc^3d - bc^2d^2 + bcd^3.$$
• Thanks for pointing this out! Apparently I'll have to refocus on bounding $P_k$ from above instead in the original problem. Something like $x_{\min(i,j)}\leq\sqrt{x_i x_j}$ (assuming $x$'s are nonnegative and ordered so that $x_1\leq\dots\leq x_a$) will at least get this back to the realm of doable tasks... – Dragan Stevanovic Nov 9 '20 at 18:11