MathDB

Number of paths from A to C which cross AC from below

Source: India tst 2002 p18

July 13, 2012

geometrygeometric transformationreflectionsymmetrycombinatorics unsolvedcombinatorics

Problem Statement

Consider the square grid with

A=(0,0)

and

C=(n,n)

at its diagonal ends. Paths from

A

C

are composed of moves one unit to the right or one unit up. Let

C_n

(n-th catalan number) be the number of paths from

A

C

which stay on or below the diagonal

AC

. Show that the number of paths from

A

C

which cross

AC

from below at most twice is equal to

C_{n+2}-2C_{n+1}+C_n