12
$\begingroup$

Encouraged by the responses to my earlier MO question, here is a follow up and upgraded quest.

Let $e\geq2$ be an integer. Define the polynomials $$P_{n,e}(x)=\prod_{i=1}^{n-1}\left(1+x^{e^{i-1}}+x^{e^i}+\cdots+x^{e^{i+e-3}}\right).$$ Denote the number of monomials in $P_{n,e}(x)$ by $a_{n,e}$.

QUESTION 1. Is this true? $$\sum_{n\geq1}a_{n,e}\,y^n=\frac{y}{\sum_{k=0}^{\lfloor\frac{e+1}2\rfloor}(-1)^k\binom{e+1-k}k\,y^k}.$$ QUESTION 2. Emeric Deutsch interprets (for instance) the sequence $a_{n,3}$ as "number of walks of length $2n+1$ in the path graph $P_4$ from one end to the other one" (see on OEIS). Does this approach apply for all other $a_{n,e}$?

REMARK. The case $e=3$ recovers my earlier request that $a_{n,3}=F_{2n}$ since $$\frac{y}{1-3y+y^2}=\sum_{n\geq1}F_{2n}\,y^n.$$ The case $e=2$ is trivially $a_{n,2}=2^{n-1}$ or $\sum_{n\geq1}a_{n,2}\,y^n=\frac{y}{1-2y}$.

$\endgroup$
6
  • $\begingroup$ Let $e=4$. According to my computations, the number of monomials in $P_{5,4}(x)$ is 119, while the coefficient of $y^5$ in $y/(1-4y+3y^2)$ is 121. $\endgroup$ – Richard Stanley Jan 9 at 20:30
  • 3
    $\begingroup$ @RichardStanley: my count shows 121 not 119. I'm not sure if I made a mistake. The counts $a_{n,4}$ according to Maple are: 1, 4, 13, 40, 121, 364, 1093, etc $\endgroup$ – T. Amdeberhan Jan 9 at 21:06
  • 2
    $\begingroup$ Yow! You are right. I had an error in my code. Good conjecture! $\endgroup$ – Richard Stanley Jan 9 at 21:18
  • $\begingroup$ @RichardStanley: I had my share of such too. :-) $\endgroup$ – T. Amdeberhan Jan 9 at 21:54
  • $\begingroup$ by the way, this is Chebyshev-related polynomial, its roots are $4\cos^2 \pi k/(e+2)$, $0<k<e+2$, so the growth of $a_{n,e}$ for large $n$ is $C_e\times (2\cos \pi/(e+2))^{2n}$. $\endgroup$ – Fedor Petrov Jan 11 at 0:36
5
$\begingroup$

The answer to Question 1 is positive. In Question 2 it is true that

Claim 1. $a_{n,e}$ equals to the number of walks of length $e+2(n-1)$ in the path graph $P_{e+1}$ from one end to the other one.

I start with general reformulations, then prove Claim 1, then deduce the generating function for $a_{n,e}$ (Question 1).

  1. Denote $V_i:=\{0,i,i+1,\ldots,i+e-2\}$; $f(0)=0$ and $f(i)=e^{i-1}$ for $i>0$. Any monomial in $P_{n,e}(x)$ have the form $x^N$ for $N=\sum f(c_i)$ for a certain choice $c_i\in V_i$ for all $i=1,2,\ldots,n-1$. The sum $\sum f(c_i)$ is the linear combination of powers of $e$ with non-negative integer coefficients not exceeding $e-1$. Thus such sums are in 1-to-1 correspondence with the multisets $\{c_1,\ldots,c_{n-1}\}$.

  2. Any fixed multiset $C=\{c_1,\ldots,c_{n-1}\}$ has the unique normal form: a sequence $(b_1,\ldots,b_{n-1})\in V_1\times V_2\times\ldots \times V_{n-1}$ such that

(i) $\{b_1,\ldots,b_{n-1}\}=C$;

(ii) if $b_j=0$ and $b_{j+1}>0$, then $b_{j+1}=j+e-1=\max(V_{j+1})$ (any 0 is followed by 0 or the maximum);

(iii) if $b_i>0$, $b_j>0$ and $i<j$, then $b_i\leqslant b_j$ (that is, positive $b_i$'s non-strictly increase).

Both the existence and the uniqueness seem pretty straightforward by induction, in case of doubts feel free to ask me to elaborate.

  1. Let $(b_1,\ldots,b_{n-1})$ be a sequence in the normal form. Denote $x_i=e$ if $b_i=0$ and $x_i=b_i-i+1$ otherwise. Then $x_i\in \{1,2,\ldots,e\}$ and the conditions (ii) and (iii) read as follows: $x_{i+1}\geqslant x_i-1$. Denote by $X_n$ the set of corresponding sequences $(x_1,\ldots,x_{n-1})$.

Let $\Omega_n\subset \{1,-1\}^{e+2(n-1)}$ denote the set of all sequences $\omega=(\varepsilon_1,\ldots,\varepsilon_{e+2(n-1)})$ of $\pm 1$'s satisfying $0\leqslant S_i\leqslant e$ and $S_{e+2(n-1)}=e$, where $S_i=\varepsilon_1+\ldots+\varepsilon_i$. The elements of $\Omega_n$ correspond to the paths from 0 to $n$ of length $e+2(n-1)$ in the path graph $0-1-2-\ldots-e$. Let me describe the bijection between $\Omega_n$ and $X_n$. For $\omega=(\varepsilon_1,\ldots,\varepsilon_{e+2(n-1)})$ choose the minimal $j$ for which $\varepsilon_{j}=1$, $\varepsilon_{j+1}=-1$. Denote $x_1=j$; remove the terms $\varepsilon_{j}$ and $\varepsilon_{j+1}$ from $\omega$, we get an element of $\Omega_{n-1}$. Repeat the same procedure $n-1$ times until we define consequently the numbers $x_1,x_2,\ldots,x_{n-1}$ (and $\omega$ is transformed to the unique element $(1,1,\ldots,1)\in \Omega_1$.)

  1. Fix $e$ and denote $a(n):=a_{n,e}$. We have $a(1)=1$ and should prove $a(n)-{e\choose 1}a(n-1)+{e-1\choose 2}a(n-2)\ldots=0$ for $n\geqslant 2$. This looks like an inclusion-exclusion, and it is indeed. Consider the following $e$ subsets of $\Omega_n$: $\Theta_{i}=\{(\varepsilon_1,\ldots,\varepsilon_{e+2(n-1)})\in \Omega_n: \varepsilon_i=1,\varepsilon_i=-1\}$, for $i=1,\ldots,e$. Then $$a(n)=\lvert\Omega_n\rvert=\lvert \cup_{i=1}^e \Theta_i \rvert=\sum_{i=1}^e \lvert\Theta_i\rvert-\sum_{i<j} \lvert\Theta_i\cap\Theta_j\rvert+\ldots\\ =ea(n-1)-{e-1\choose 2}a(n-2)+\ldots.$$
$\endgroup$

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.