Problem

Source: MOP 2006 Homework - Black Group

Tags: analytic geometry, Ring Theory, combinatorics unsolved, combinatorics



Let $A_{n,k}$ denote the set of lattice paths in the coordinate plane of upsteps $u=[1,1]$, downsteps $d=[1,-1]$, and flatsteps $f=[1,0]$ that contain $n$ steps, $k$ of which are slanted ($u$ or $d$). A sharp turn is a consecutive pair of $ud$ or $du$. Let $B_{n,k}$ denote the set of paths in $A_{n,k}$ with no upsteps among the first $k-1$ steps, and let $C_{n,k}$ denote the set of paths in $A_{n,k}$ with no sharps anywhere. For example, $fdu$ is in $B_{3,2}$ but not in $C_{3,2}$, while $ufd$ is in $C_{3,2}$ but not $B_{3,2}$. For $1 \le k \le n$, prove that the sets $B_{n,k}$ and $C_{n,k}$ contains the same number of elements.