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