# Counting monomials in product polynomials: Part II

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

• 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. – Richard Stanley Jan 9 at 20:30
• @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 – T. Amdeberhan Jan 9 at 21:06
• Yow! You are right. I had an error in my code. Good conjecture! – Richard Stanley Jan 9 at 21:18
• @RichardStanley: I had my share of such too. :-) – T. Amdeberhan Jan 9 at 21:54
• 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}$. – Fedor Petrov Jan 11 at 0:36

## 1 Answer

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, 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