Return to 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_{n+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-n$. 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. 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\}$, $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.$$

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

QUESTION 1. Yes, this looks to be true. Below is a sketch with missed boring details.

1. For any choice of $c_i\in V_i:=\{0,i,i+1,\ldots,i+e-2\}$ for all $i=1,2,\ldots,n-1$ we have the monomial $x^N$ for $N=\sum f(c_i)$, where $f(0)=0$ and $f(i)=e^{i-1}$ for $i>0$. Since the coefficient of $e^{i-1}$ in the sum for $N$ does not exceed $e-1$, 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

3. So we should count the sequences in the normal form. This may be done by the transfer-matrix method. Denote $y_0(n)$, corr. $y_i(n)$, $i=1,\ldots,e-1$ the number of normal forms $(b_1,\ldots,b_{n-1})$ such that $b_{n-1}=0$, corr. $b_{n-1}=e+i-1$. Denoting $a(n):=a_{n,e}$, we get:

$a(n)=y_0(n)+\ldots+y_{e-1}(n)$;

$y_0(n)=y_{e-1}(n)=y_0(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)$;

$y_{e-2}(n)=y_1(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)-y_0(n-1)=a(n-1)-a(n-2)$;

$y_{e-3}(n)=y_1(n-1)+\ldots+y_{e-2}(n-1)=y_{e-2}(n)-y_{e-1}(n-1)=a(n-1)-2a(n-2)$

etc. For example, for $e=5$ we get

$a(n)=y_0(n)+\ldots+y_4(n)$, $y_0(n)=y_4(n)=a(n-1)$, $y_3(n)=a(n-1)-a(n-2)$, $y_2(n)=a(n-1)-2a(n-2)$, $y_1(n)=a(n-1)-3a(n-2)+a(n-3)$. So the recurrence reads as $a(n)=5a(n-1)-6a(n-2)+a(n-3)$ as you prescribe. The similar pattern takes place for other $e$.

QUESTION 2. Yes, $a(n)=a_{n,e}$ is the number of paths of length $e+2(n-1)$ from the first vertex of $P_{e+1}$ to the last vertex.

I construct a bijection between such paths and the sequences $(b_1,\ldots,b_{n-1})$ in the normal form from the answer to Question 1. 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$.

Now consider a path from 0 to $e$ of length $e+2(n-1)$ (each edge joins a vertex $x\in \{0,1,\ldots,e\}$ with $x\pm 1$, all intermediate vertices belong to $[0,e]$.) If $n=1$, there is unique such path: all edges are $+1$. If $n=2$, the path has unique turn: the +1 edge followed by the -1 edge, say it happens between the vertices $j-1$ and $j$, $j\in \{1,\ldots,e\}$. So, there are $e$ possibilities naturally enumerated by the set $\{1,\ldots,e\}$, where our $x_i$'s from the previous paragraph leave. Not bad. For arbitrary $n$, choose the first turn $j-1\to j\to j-1$, and remove these two edges from the path. Denote $x_1=j$. After this removal the first turn in the new shorten path may be $(j-2)\to (j-1)\to (j-2)$ (if the next edge after the removed two edges was $-1$) or it is $i-1\to i\to i-1$ for certain $i\geqslant j$ (if the next edge after the removed two edges was $+1$). To summarize, the next first turn is $i-1\to i\to i-1$ for certain $i\geqslant j-1=b_1-1$. Denote this $i$ be $b_2$, remove this turn and proceed.

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_{n+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

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-n$. 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. 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\}$, $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.$$

QUESTION 1 looks to be true. Below is a sketch with missed boring details.

1. For any choice of $c_i\in V_i:=\{0,i,i+1,\ldots,i+e-2\}$ for all $i=1,2,\ldots,n-1$ we have the monomial $x^N$ for $N=\sum f(c_i)$, where $f(0)=0$ and $f(i)=e^{i-1}$ for $i>0$. Since the coefficient of $e^{i-1}$ in the sum for $N$ does not exceed $e-1$, 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. So we should count the sequences in the normal form. This may be done by the transfer-matrix method. Denote $y_0(n)$, corr. $y_i(n)$, $i=1,\ldots,e-1$ the number of normal forms $(b_1,\ldots,b_{n-1})$ such that $b_{n-1}=0$, corr. $b_{n-1}=e+i-1$. Denoting $a(n):=a_{n,e}$, we get:

$a(n)=y_0(n)+\ldots+y_{e-1}(n)$;

$y_0(n)=y_{e-1}(n)=y_0(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)$;

$y_{e-2}(n)=y_1(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)-y_0(n-1)=a(n-1)-a(n-2)$;

$y_{e-3}(n)=y_1(n-1)+\ldots+y_{e-2}(n-1)=y_{e-2}(n)-y_{e-1}(n-1)=a(n-1)-2a(n-2)$

etc. For example, for $e=5$ we get

$a(n)=y_0(n)+\ldots+y_4(n)$, $y_0(n)=y_4(n)=a(n-1)$, $y_3(n)=a(n-1)-a(n-2)$, $y_2(n)=a(n-1)-2a(n-2)$, $y_1(n)=a(n-1)-3a(n-2)+a(n-3)$. So the recurrence reads as $a(n)=5a(n-1)-6a(n-2)+a(n-3)$ as you prescribe. The similar pattern takes place for other $e$.

QUESTION 1. Yes, this looks to be true. Below is a sketch with missed boring details.

1. For any choice of $c_i\in V_i:=\{0,i,i+1,\ldots,i+e-2\}$ for all $i=1,2,\ldots,n-1$ we have the monomial $x^N$ for $N=\sum f(c_i)$, where $f(0)=0$ and $f(i)=e^{i-1}$ for $i>0$. Since the coefficient of $e^{i-1}$ in the sum for $N$ does not exceed $e-1$, 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. So we should count the sequences in the normal form. This may be done by the transfer-matrix method. Denote $y_0(n)$, corr. $y_i(n)$, $i=1,\ldots,e-1$ the number of normal forms $(b_1,\ldots,b_{n-1})$ such that $b_{n-1}=0$, corr. $b_{n-1}=e+i-1$. Denoting $a(n):=a_{n,e}$, we get:

$a(n)=y_0(n)+\ldots+y_{e-1}(n)$;

$y_0(n)=y_{e-1}(n)=y_0(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)$;

$y_{e-2}(n)=y_1(n-1)+\ldots+y_{e-1}(n-1)=a(n-1)-y_0(n-1)=a(n-1)-a(n-2)$;

$y_{e-3}(n)=y_1(n-1)+\ldots+y_{e-2}(n-1)=y_{e-2}(n)-y_{e-1}(n-1)=a(n-1)-2a(n-2)$

etc. For example, for $e=5$ we get

$a(n)=y_0(n)+\ldots+y_4(n)$, $y_0(n)=y_4(n)=a(n-1)$, $y_3(n)=a(n-1)-a(n-2)$, $y_2(n)=a(n-1)-2a(n-2)$, $y_1(n)=a(n-1)-3a(n-2)+a(n-3)$. So the recurrence reads as $a(n)=5a(n-1)-6a(n-2)+a(n-3)$ as you prescribe. The similar pattern takes place for other $e$.

QUESTION 2. Yes, $a(n)=a_{n,e}$ is the number of paths of length $e+2(n-1)$ from the first vertex of $P_{e+1}$ to the last vertex.

I construct a bijection between such paths and the sequences $(b_1,\ldots,b_{n-1})$ in the normal form from the answer to Question 1. 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$.

Now consider a path from 0 to $e$ of length $e+2(n-1)$ (each edge joins a vertex $x\in \{0,1,\ldots,e\}$ with $x\pm 1$, all intermediate vertices belong to $[0,e]$.) If $n=1$, there is unique such path: all edges are $+1$. If $n=2$, the path has unique turn: the +1 edge followed by the -1 edge, say it happens between the vertices $j-1$ and $j$, $j\in \{1,\ldots,e\}$. So, there are $e$ possibilities naturally enumerated by the set $\{1,\ldots,e\}$, where our $x_i$'s from the previous paragraph leave. Not bad. For arbitrary $n$, choose the first turn $j-1\to j\to j-1$, and remove these two edges from the path. Denote $x_1=j$. After this removal the first turn in the new shorten path may be $(j-2)\to (j-1)\to (j-2)$ (if the next edge after the removed two edges was $-1$) or it is $i-1\to i\to i-1$ for certain $i\geqslant j$ (if the next edge after the removed two edges was $+1$). To summarize, the next first turn is $i-1\to i\to i-1$ for certain $i\geqslant j-1=b_1-1$. Denote this $i$ be $b_2$, remove this turn and proceed.