Counting monomials in product polynomials: Part II

Question

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

Answer 1

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.

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

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