Encouraged by the responses to [my earlier MO question](https://mathoverflow.net/questions/380734/counting-monomials-in-product-polynomials), 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](https://oeis.org/A001906)). Does this approach apply for all other $a\_{n,e}$?
> 
> 
> 


**REMARK.** The case $e=3$ recovers [my earlier request](https://mathoverflow.net/questions/380734/counting-monomials-in-product-polynomials) 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}$.



Counting monomials in product polynomials: Part II
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.$$


