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.
4
-
$\begingroup$ If I am not mistaken the coefficients in the simplest case $a=2$ are given by OEIS A105422. $\endgroup$Timothy Budd– Timothy Budd2020-11-05 07:23:16 +00:00Commented Nov 5, 2020 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– Dragan Stevanovic2020-11-05 19:37:36 +00:00Commented Nov 5, 2020 at 19:37
-
$\begingroup$ What you are talking about is $k=2$, right? $\endgroup$Timothy Budd– Timothy Budd2020-11-05 19:53:49 +00:00Commented Nov 5, 2020 at 19:53
-
$\begingroup$ Right, that was $k=2$. The coefficients for $a=2$ indeed look like the sequence you mention. $\endgroup$Dragan Stevanovic– Dragan Stevanovic2020-11-06 18:37:24 +00:00Commented Nov 6, 2020 at 18:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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. $$
-
$\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– Dragan Stevanovic2020-11-09 18:11:40 +00:00Commented Nov 9, 2020 at 18:11