Closed-form formula for a multivariate polynomial

Question

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.

Answer 1

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