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_{k1},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 closedform formula for $P_k(x_1,\dots,x_a)$? If this problem appeared elsewhere earlier, a reference is more than welcome.

$\begingroup$ If I am not mistaken the coefficients in the simplest case $a=2$ are given by OEIS A105422. $\endgroup$ – Timothy Budd Nov 5 '20 at 7:23

$\begingroup$ 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$. $\endgroup$ – Dragan Stevanovic Nov 5 '20 at 19:37

$\begingroup$ What you are talking about is $k=2$, right? $\endgroup$ – Timothy Budd Nov 5 '20 at 19:53

$\begingroup$ Right, that was $k=2$. The coefficients for $a=2$ indeed look like the sequence you mention. $\endgroup$ – 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 transfermatrix 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 rowvector (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(ItA)^{1}v. $$ (More precisely, the righthand 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+bdc^2+cd)t^2+(b^2db^2c+bc^2bcd)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. $$

$\begingroup$ 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... $\endgroup$ – Dragan Stevanovic Nov 9 '20 at 18:11