Difference between revisions of "User:Richard Pinch/sandbox-12"
From Encyclopedia of Mathematics
(Start article: Dyck path) |
m (→Dyck path: typo) |
||
| Line 1: | Line 1: | ||
=Dyck path= | =Dyck path= | ||
| − | A [[lattice path]] on the square lattice from the origin $( | + | A [[lattice path]] on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path |
never passes below the line $y=x$. | never passes below the line $y=x$. | ||
Revision as of 14:58, 26 December 2017
Dyck path
A lattice path on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path never passes below the line $y=x$.
The number of Dyck paths of length $2n$ is given by the $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$
References
How to Cite This Entry:
Richard Pinch/sandbox-12. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-12&oldid=42596
Richard Pinch/sandbox-12. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-12&oldid=42596