2003 Putnam A5

A Dyck $n$-path is a lattice path of $n$ upsteps $(1,1)$ and $n$
downsteps $(1,-1)$
that starts at the origin $O$ and never dips below the $x$-axis.
A return is a maximal sequence of contiguous downsteps that terminates
on the $x$-axis. For example, the Dyck 5-path illustrated has two returns,
of length 3 and 1 respectively.

\begin{tikzpicture}[scale=.5]
\fill (0,0) circle (.2); \fill (1,1) circle (.2); \fill (2,2) circle (.2);
\fill (3,1) circle (.2); \fill (4,2) circle (.2); \fill (5,3) circle (.2);
\fill (6,2) circle (.2); \fill (7,1) circle (.2); \fill (8,0) circle (.2);
\fill (9,1) circle (.2); \fill (10,0) circle (.2);
\draw (0,0) -- (2,2) -- (3,1) -- (5,3) -- (8,0) -- (9,1) -- (10,0) -- cycle;
\draw (-.3,-.1) node[anchor=north] {$O$};
\end{tikzpicture}

Show that there is a one-to-one correspondence between the Dyck $n$-paths

with no return of even length and the Dyck $(n-1)$-paths.

Dyck $n$-path 是 $n$ 向上的格子路径 $(1,1)$ 和 $n$

下台阶$(1,-1)$

从原点 $O$ 开始，并且永远不会低于 $x$ 轴。

返回是终止的连续下步的最大序列

在 $x$ 轴上。例如，所示的 Dyck 5 路径有两个返回，

长度分别为3和1。

\begin{tikzpicture}[规模=.5]
\填充(0,0)圆(.2); \填充(1,1)圆(.2); \填充(2,2)圆(.2);
\填充(3,1)圆(.2); \填充(4,2)圆(.2); \填充(5,3)圆(.2);
\填充(6,2)圆(.2); \填充(7,1)圆(.2); \填充(8,0)圆(.2);
\填充(9,1)圆(.2); \填充(10,0)圆(.2);
\draw (0,0) -- (2,2) -- (3,1) -- (5,3) -- (8,0) -- (9,1) -- (10,0) -- 循环；
\draw (-.3,-.1) 节点[anchor=north] {$O$};
\结束{tikz图片}

表明 Dyck $n$ 路径之间存在一一对应关系
没有返回偶数长度和 Dyck $(n-1)$-路径。