1
$\begingroup$

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.

$\endgroup$
4
  • $\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
2
$\begingroup$

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

$\endgroup$
1
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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