Counting problem, number of moves

372 Views Asked by At

In a game, you are standing somewhere and a move consists of either moving forward any number of steps, not moving at all, or moving $1$ step backwards. If you complete $n$ moves, find the number of sequences that end with you in your starting position and which never go behind your starting position.

If the "never go behind the starting position" condition weren't there, the answer would just be $\binom{2n-1}{n-1}$. However I'm not on sure how to proceed from here.

2

There are 2 best solutions below

0
On

The answer is given by the Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$.

A combinatorial reduction of the present problem to the interpretation of $C_n$ as the number of "balanced" strings containing $n$ pairs of parentheses is as follows. Given a sequence of $n$ moves, we transform each move (i.e. an integer) $m\geqslant-1$ into a string of $m+1$ opening parentheses, followed by a closing parenthesis: $$-1\mapsto\color{blue}{\texttt{)}},\quad 0\mapsto\color{blue}{\texttt{()}},\quad 1\mapsto\color{blue}{\texttt{(()}},\quad 2\mapsto\color{blue}{\texttt{((()}},\quad 3\mapsto\color{blue}{\texttt{(((()}},\quad\ldots$$ Clearly, this transformation is invertible (and one-to-one).


There's also an "assume nothing known" approach using generating functions. Let $c_{n,k}$ be the number of sequences of $n$ moves that take you $k$ steps forward (here $n,k\geqslant 0$). Then $$c_{0,k}=[k=0]=\begin{cases}1,&k=0\\0,&k\neq 0\end{cases};\qquad c_{n+1,k}=\sum_{j=0}^{k+1}c_{n,j}.$$

Now consider the "generating function" $g(x,y)=\sum_{n,k\geqslant 0}c_{n,k}x^n y^k$ as a formal power series (to stay ignorant of convergence issues; we could also consider it as an ordinary function, but then we would need to show its analyticity around $(0,0)$, for the "composition" argument below to be justified). Let $g(x):=g(x,0)$ (thus, $g(x)=\sum_{n\geqslant 0}c_{n,0}x^n$ is the "generating function" of the numbers we actually need). Then

\begin{align*} \frac{g(x,y)-1}{x}&=\sum_{n,k\geqslant 0}c_{n+1,k}x^n y^k \\&=\sum_{n,k\geqslant 0}x^n y^k\left(c_{n,0}+\sum_{j=0}^k c_{n,j+1}\right) \\&=\sum_{n\geqslant 0}c_{n,0}x^n\sum_{k\geqslant 0}y^k+\sum_{n,j\geqslant 0}c_{n,j+1}x^n\sum_{k\geqslant j}y^k \\&=\frac{1}{1-y}\left(\sum_{n\geqslant 0}c_{n,0}x^n+\sum_{n,j\geqslant 0}c_{n,j+1}x^n y^j\right) \\&=\frac{g(x)}{1-y}+\frac{g(x,y)-g(x)}{y(1-y)}, \end{align*} $$\text{i.e.}\quad\big(y(1-y)-x\big)g(x,y)=(1-y)\big(y-xg(x)\big).$$

Now - the "composition" argument! - we put $y=xg(x)$ here (this is a formal power series with no constant term, so all the compositions are well-defined). The RHS becomes identically zero, and since $g(x,y)$ is not, we must have $y(1-y)=x$.

Choosing the solution $y$ that gives $g(x)$ as a power series, we get $$g(x)=\frac{1-(1-4x)^{1/2}}{2x}.$$

It remains to use the binomial series for $(1-4x)^{1/2}$, or just recognize this generating function.

0
On

There is a bijection between walks of your type with $n$ moves, and Dyck paths. Encode a walk of your type as a sequence of $n$ integers $(a_1,\dots,a_n)$, where $a_i\in \{-1,0,1,\dots\}$ for each $i\in \{1,\dots,n\}$. To get the corresponding Dyck path, replace each $a_i$ with a sequence of $(a_i+1)$ up steps and $1$ down step. Note your path stays to the right of the origin if and only if the corresponding Dyck path stays above the $x$-axis. Of course, the number of Dyck paths is $\frac1{n+1}\binom{2n}n$.