combinatoriek 1

Opgave - IMOSL 1999 vraag 21

Zij $n$ een natuurlijk getal. Een pad van $(0,0)$ tot $(n,n)$ in het $xy$-vlak is een aaneenschakeling van opeenvolgende eenheidsbewegingen ofwel naar rechts (die we een E-beweging noemen) ofwel naar boven (die we een N-beweging noemen), en alle bewegingen bevinden zich in het halfvlak $x\geq y$. Een stap in een pad is het voorkomen van twee opeenvolgende bewegingen van het type EN. Bewijs dat het totaal aantal dergelijke paden die precies $s$ stappen gegeven wordt door de formule
$$\frac1s\binom{n-1}{s-1}\binom n{s-1}.$$