Given a natural number $n$ and define $B_n$ as the set of all sequence $b_1, b_2, \dots, b_n$ of length $n$...

Question

Given a natural number $n$ and define $B_n$ as the set of all sequences $b_1, b_2, \dots, b_n$ of length $n$ such that $b_1 = 1$ and for every $i = 1, 2, \dots, n-1$, then we have $$ b_{i+1} - b_i \in \{ 1 , -1, -3, -5, -7, \dots \} $$Where $b_i > 0$ for all $i$. Find a closed form of $|B_n|$.

We can easly see (say by induction) that $b_n\leq n$ for all $n$.

So if we say $[e_2,e_4,...,e_{2n}]$ are all possible outcomes for $b_{2n}$ to be $2,4,...2n$ and $(o_1,o_3,...,o_{2n-1})$ are all possible outcomes for $b_{2n-1}$ to be $1,3,...,2n-1$ then we have a following chain:

$$(1)\to [1]\to (1,1)\to [2,1]\to (3,3,1)\to [7,4,1]\to$$ $$\to (12,12,5,1)\to [30,18,6,1]\to (55,55,25,7,1) \to...$$

so $|B_n|\in \{1,1,2,3,7,12,30,55,143,...\}$, but no closed form. Any idea how to find it?

Edit: So, writen number at a vertex $V$ is a number of paths (only going up or right) from red vertex to the vertex $V$.

Answer 1

Let us consider walks on an integer lattice starting at $(0,0)$, where each step is one unit up or right, and which stay at or above the line $y=2x$. Each step either increases the quantity $y-2x$ by $1$ or decreases it by $2$, and this quantity must always be nonnegative. According to the generalized ballot theorem, the number of such walks which end at $(a,b)$ is

$$ \frac{b+1-2a}{a+b+1}\binom{a+b+1}{b+1}=\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} $$

We can break such a walk into portions of the form $(\to,\to,\dots,\to,\uparrow)$, consisting of $k$ right steps followed by a single up step. Such a sequence increases the quantity $y-2x$ by $1-2k$, which can be $1,-1,-3,-5,\dots$ etc. This is the connection to your problem; the number of walks which have exactly $n$ up steps corresponds exactly to $|B_{n+1}|$. To count walks with exactly $b$ up steps and any number of right steps, we sum over all possible values of $a$ in the above formula. If $b$ is even, then $a$ can go as high as $b/2$, so the number of walks is \begin{align} \sum_{a=0}^{b/2}\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} &=\binom{\frac32b+2}{b+2}-3\binom{\frac32b+1}{b+2} =\frac1{b+1}\binom{\frac32b+1}{b} %\\&=\binom{\frac32b+2}{\frac12b}-3\binom{\frac32b+1}{\frac12 b-1} %\\&=\binom{\frac32b+2}{\frac12b}-3\cdot \frac{\frac12b}{\frac32b +2}\binom{\frac32b+2}{\frac12 b} %\\&=\frac{2}{\frac32b+2}\binom{\frac32b+2}{\frac12b} %\\&=\frac{2}{b+2}\binom{\frac32b+1}{\frac12b} \end{align} The first equality follows from two applications of the hockey stick identity, while the latter can be verified by converting everything to factorials. Therefore, when $n$ is odd, $|B_n|$ is the result of the substituting $n-1$ in the above formula, so

$$ |B_n|=\frac1n\binom{(3n-1)/2}{n-1}.\tag{$n\text{ is odd}$} $$

You can verify $|B_1|=\frac11\binom10=1,|B_3|=\frac13\binom42=2,|B_5|=\frac15\binom{7}3=7,$ etc.

When $b$ is odd, the highest $a$ can go is $(b-1)/2$, so we instead get

\begin{align} \sum_{a=0}^{(b-1)/2}\binom{a+b+1}{b+1}-3\binom{a+b}{b+1} =\binom{\frac32b+\frac32}{b+2}-3\binom{\frac32b+\frac12}{b+2}=\frac1{b+2}\binom{\frac32(b+1)}{\frac12(b+1)} \end{align} so that

$$ |B_n|=\frac1{n+1}\binom{\frac32 n}{\frac12 n}.\tag{$n\text{ is even}$} $$

---

There is also a generating function solution. Let $a_n$ be the number of lattice walks from $(0,0)$ to $(n,2n)$ which stay at or above the line $y=2x$. With the previous discussion and some thought, $a_n=|B_{2n}|$. We will derive a generating function for $a_n$, and handle $|B_{2n+1}|$ separately later.

Define the elevation of a point $(x,y)$ to be the quantity $y-2x$. Our lattice walks always have a nonnegative elevation. A nonempty walk $W$ can uniquely be decomposed as a concatenation $$ W=W_1+\uparrow+W_2+\uparrow+W_3+\rightarrow $$ where

• $W_1$ is the portion of the path up until the last time before reaching $(n,2n)$ that the walk has an elevation of $0$.

• $W_2$ is the portion of the walk after $W_2$, and up until the last time it has an elevation of $1$.

• $W_3$ is the portion of the walk after $W_3$, and up until the last time it has an elevation of $2$.

This implies that whenever $n>0$, we have that $$ a_n = \sum_{i+j+k=n-1}a_ia_ja_k $$ since $a_i,a_j,a_k$ represent the number of ways to choose $W_1,W_2,W_3$. (Compare and contrast this analysis to the Catalan numbers, $C_n$, where each path $C$ can be uniquely decomposed as $C=C_1+\uparrow+C_2+\to$, which gives the recurrence $C_n=\sum_{i+j=n-1}C_iC_j$, giving the generating function for $C_n$).

Letting $A(x)=\sum_{n\ge 0} a_nx^n$, and using the base case $a_0=0$, this gives the generating function equation $$ A(x)=1+xA(x)^3 $$ This does let us solve for $A(x)$, but it is quite messy. Fortunately, using Lagrange inversion, you can recover $a_n=\frac1{2n+1}\binom{3n}n$.

To find $|B_{2n+1}|$, let $d_n$ be the number of walks from $(0,0)$ to $(n,2n+1)$, and note that $d_n=|B_{2n+1}|$. By considering the last time the walk has an elevation of $0$, you can derive that $$ d_n=\sum_{k=0}^n a_ka_{n-k}, $$ so that $D(x)=\sum_{n\ge 0}d_nx^n$ satisfies $D(x)=A(x)^2$. Using our generating function equation for $A(x)$, we get that $$ D(x)^{1/2} = 1+xD(x)^{3/2} $$ You can then probability use Lagrange inversion to recover $d_n$. I am not quite experienced with Lagrange inversion, so I am not sure about the details here.

Answer 2

Okay, here is a direct generating function solution, with the Lagrange inversion details fleshed out. We need two separate generating functions for the even coefficients $|B_{2n}|$ and the odd coefficients $|B_{2n+1}|$.

---

Let $a_n=|B_{2n}|$, with the convention $a_0=1$. For any $n\ge 1$, a sequence $b$ of length $2n$ can be uniquely written as a concatenation $$ b = b_1+\color{blue}{(1)}+b_2+\color{red}{(2)}+b_3, $$ where

• $\color{blue}{(1)}$ is the last $1$ occurring as an entry in $b$.

• $\color{red}{(2)}$ is the last $2$ occurring as an entry in $b$ after the $\color{blue}{(1)}$.

• $b_1,b_2,b_3$ are the (possibly empty) sequences which $b$ is split into by deleting $\color{blue}{(1)}$ and $\color{red}{(2)}$.

For example, when $b=(\color{blue}1,2,3,2,3,4,5,\color{red}2,3,4)$, then $b_1$ is empty, $b_2=(2,3,2,3,4,5)$, and $b_3=(3,4)$.

You can check that $b_1,b_2$ and $b_3$ are all sequences of even length. Furthermore, when you subtract $1$ from each entry of $b_2$, and $2$ from each entry of $b_3$, then $b_1,b_2,b_3$ are all valid sequences. Therefore, the number of ways to choose $b$ is the number of ways to choose $b_1,b_2,b_3$, giving the recursive relation $$ a_n = \begin{cases} \displaystyle\sum_{i+j+k=n-1}a_ia_ja_k & n\ge 1\\ 1 & n=0\hspace{2.7cm} \end{cases} $$ Letting $A(x)=\sum_{n\ge 0}a_nx^n$, this implies the generating function equation $$ A(x)=1+xA(x)^3 $$ Using this, you can solve for $A(x)$, but the exact expression for $A(x)$ is quite messy, and does not easily lend itself to a formula for $a_n$. Fortunately, we can use Lagrange inversion to recover $a_n$:

Theorem: (Lagrange inversion) Let $f(x)$ and $g(x)$ be functions which are analytic at zero which are compositional inverses, i.e. $f(g(x))=x$, and for which $f(0)=g(0)=0$. Then $$[x^k]g(x)^n=\tfrac{n}k [x^{-n}]f(x)^{-k},\tag{$*$}$$where $[x^i]h(x)$ is the coefficient of $x^i$ in the Laurent series $h(x)$.

To see how this helps us here, let $\def \A {\tilde A}\A(x)=A(x)-1$, so that $$ {\A(x)}{(1+\A(x))^{-3}}=x $$ This means that $\A(x)$ is the compositional inverse of $f(x)=x(1+x)^{-3}$. Therefore, using $(*)$ with $n=1$, we get that for any $k\ge 1$, \begin{align} |B_{2k}|=a_k=[x^k]\A(x) &=\frac1k[x^{-1}]f^{-k} \\&=\frac1k[x^{-1}]\Big(x(1+x)^{-3}\Big)^{-k} \\&=\frac1k[x^{k-1}](1+x)^{3k} \\&=\frac1k\binom{3k}{k-1},\tag1 \\|B_{2k}|&=\frac1{2k+1}\binom{3k}k \end{align}

Next, let $d_n = |B_{2n+1}|$. Any sequence $b$ of odd length can be uniquely decomposed as $$ b = b_1 + (1) + b_2, $$ where $b_1$ and $b_2$ are (possibly empty) sequences of even length, and $(1)$ is the last occurrence of $1$ as an entry in $b$. Therefore, and odd sequence is a concatenation of two even sequences. Letting $D(x)=\sum_{n\ge 0} d_nx^n$, this gives the recursion $d_n=\sum_{i+j=n}a_ia_j$, which implies the generating function equation $$ D(x)=A(x)^2. $$ Again, we can recover $d_k$ via Lagrange inversion. First, recalling $\A(x)=A(x)-1$, $$ D(x) = A(x)^2 = (\A(x)+1)^2=\A(x)^2+2\A(x)+1 $$ We already know the coefficients of $\A(x)$, we just need the coefficients of $\A(x)^2$ to recover the coefficients $d_k$ of $D(x)$. To do this, use $(*)$ with $n=2$: \begin{align} [x^k]\A(x)^2=\frac2k[x^{-2}] \Big(x(1+x)^3\Big)^{-k}=\frac2k[x^{k-2}](1+x)^{3k}=\frac2k\binom{3k}{k-2}\tag 2 \end{align} Finally, for $k\ge 1$, \begin{align} |B_{2k+1}|=d_k=[x^k]D(x) &=[x^k]\A(x)^2+2[x^k]\A(x) \\&\stackrel{(1)+(2)}=\frac2k\binom{3k}{k-2}+\frac2k\binom{3k}{k-1} \\&=\frac1{2k+1}\binom{3k+1}{k+1} \end{align}