Математикадан республикалық олимпиада, 2012-2013 оқу жылы, 11 сынып

Екі тасбақа бір уақытта координатасы $(0, 0)$ нүктеден шығып, әр жүрісте бір уақытта бір бүтін координатаға оңға немесе жоғары қарай жүреді (яғни $\left( {x,y} \right)$ нүктесінен $\left( {x + 1,y} \right)$ немесе $\left( {x,y+1} \right)$ нүктесіне). Егер тасбақалар соңғы рет $\left( {0,0} \right)$ нүктесінде кездескен болса, олар $\left( {n,n} \right)$ нүктесіне қанша әдіспен жете алады? ( Д. Елиусизов )

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

Решение: Рассмотрим любые два путя из $(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.$