Prove that following numbers are equal:

(Uunordered) pairs of lattice paths with $n+1$ steps each, starting at $(0,0)$, using steps $(0,1)$ or $(1,0)$, ending at the same point and only intersecting at the beginning and end

and same pairs of paths with $n-1$ steps (starting at $(0,0)$, using steps $(0,1), (1,0)$ each such that one path never rises above the other path.

is it possible to write it as $c_n = \sum\limits_{i = 0}^{n-1} c_{n-1-i}c_i$ (where, for example, first factor ($c_{n-1-i}$) represents number of steps on the $x-$line and second factor is the number of steps on the $y-$line)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.