---
# System prepended metadata

title: 'Catalan Numbers vs. Loops '

---


```javascript=
for i1 = 1 to n do
    for i2 = 1 to min(i1,n-1) do
        for i3 = 1 to min(i2,n-2) do
            ...
            for in_1 = 1 to min(in-2,2) do
                for in = 1 to 1 do
                    print i1,i2,i3,...,in
```
Show that print statement is executed $C_n$ times,where $C_n$ denotes the $n$th Catalan number.

:::info
Consider each set of indices $I=(i_1,\ i_2,\ \cdots,\ i_{n-1},\ i_n$) from the loops. Let $i_j$ denote a $y$-coordinate for $1\le j\le n$. It is not hard to see that every set of $y$-coordinates $(i_n,\ i_{n-1},\ \cdots,\ i_2,\ i_1)$ (i.e., the reversed sequence of $I$) corresponds to a distinct monotone path from $(0,\ 0)$ to $(n,\ n)$ that does not cross the diagonal. The total number of such monotone paths is exactly $C_n$. Therefore, the "print" statement within the loops would be executed $C_n$. times.
Below give an example of $n=3$:

```javascript
for i1 = 1 to 3 do
    for i2 = 1 to min(i1,2) do
        for i3 = 1 to 1 do
            print i1,i2,i3
```
"print i1,i2,i3" within the loops above executes 5 times as below.
| index| 1 | 2 | 3 | 4 | 5 |
|:--:|:--:|:--:|:--:|:--:|:--:|
| i1 | 1 | 2 | 2 | 3 | 3 |
| i2 | 1  | 1  |  2 |  1  | 2 |
| i3 | 1  | 1  |  1 |  1  | 1 |

The reversed $5\ (=C_3)$ sequences $(i_3,\ i_2,\ i_1)$ are $(1,1,1),\ (1,1,2),\ (1,2,2),\ (1,1,3),$ and $(1,2,3)$, each of which corresponds to a monotone path from (0,0) to (3, 3)  that does not cross the diagonal as shown in the following. Each $𝑖_𝑗$ is treated as a $y$-coordinate in the figure.
(For even more precision, one can regard $𝑖_𝑗−1$ as the 
$y$-coordinate. For example, modifying $(1, 1, 1)$ to $(0, 0, 0)$ in the figure provides a more precise and intuitive representation.) For $C_n=5$, we have
![image](https://hackmd.io/_uploads/B1FwkOskyl.png)
![image](https://hackmd.io/_uploads/rkULgda1bl.png)


:::



:::success
Furthermore, each monotone path that does not cross the diagonal can be mapped to a sequence of Dyck words consisting of '(' and ')', where each right step corresponds to '(', and each upward step corresponds to ')'. This mapping highlights the connection between the paths and valid parentheses arrangements.
![image](https://hackmd.io/_uploads/H1qYk_j1yg.png)

:::

:::success
$C_n$ is the number of different ways $n + 1$ factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator, as in the matrix chain multiplication problem). For $n = 3$, we have the following five different parenthesizations of four factors:
$\qquad\qquad((ab)c)d\quad     (a(bc))d\quad     (ab)(cd)\quad     a((bc)d)\quad     a(b(cd))$
:::

:::success
$C_n$ is the number of full binary trees with $n + 1$ leaves, or, equivalently, with a total of $n$ internal nodes. For $n = 3$, we have
![image](https://hackmd.io/_uploads/BJkiE_j1Jg.png)
:::danger
Note that please map $a, b, c, d$ in the above example to the leaves here to realize the correspondence.
:::

Now, you might have interested in Catalan numbers. For more correspondences, please refer to
https://en.wikipedia.org/wiki/Catalan_number

