Республиканская олимпиада по математике, 2013 год, 11 класс

Две черепахи одновременно выходят из точки с координатами $(0, 0)$ и на каждом шагу одновременно переходят на одну из целочисленных координат вверх или вправо (то есть из ${(x, y)}$ в ${(x+1,y)}$ или в ${(x,y+1)}$). Сколько существует способов им добраться до точки $(n, n)$, если последний раз они встречались только в точке $(0, 0)$? ( Д. Елиусизов )

Комментарий/решение

Решение: Рассмотрим любые два путя из $(0,0)$ в $(n,n).$

Один из них будет начинаться с $\uparrow$ и заканчиваться $\rightarrow,$

а другой будет начинаться с $\rightarrow$ и заканчиваться $\uparrow.$

То есть это два путя вида $(1,0) \rightsquigarrow (n,n-1)$ и $(0,1) \rightsquigarrow (n-1,n).$ Таких пар путей у нас $\dbinom{2n-2}{n-1}^2.$

Найдем количество пар таких пересекающихся путей. Для этого рассмотрим биекцию которая "меняет местами" часть пути начиная с первого пересечения этих путей. По итогу кол-во пар таких пересекающихся путей равно кол-ву пар путей вида $(1,0)\rightsquigarrow (n-1,n)$ и $(0,1) \rightsquigarrow (n,n-1).$ Таких путей $\dbinom{2n-2}{n-2}^2.$

Откуда ответ $\dbinom{2n-2}{n-1}^2-\dbinom{2n-2}{n-2}^2.$