Contar caminos 'malos' usando reflexión.
El Principio de Reflexión es una técnica combinatoria muy potente que usas principalmente para contar caminos en una cuadrícula que están limitados por una frontera específica. Atribuido a Désiré André, este método transforma un problema de conteo difícil —contar caminos que se quedan dentro de cierta región— en un problema de resta que involucra caminos sin restricciones. La idea central es establecer una correspondencia uno a uno (biyección) entre los caminos "malos" (los que violan la condición de la frontera) y un conjunto de caminos sin restricciones entre un punto inicial reflejado y el punto final original.
Esta técnica es fundamental para resolver el Teorema del Escrutinio (Ballot Theorem) y para obtener la fórmula de los números de Catalan. La vas a ver seguido en competencias como el AIME y el USAMO cuando trabajas con caminatas aleatorias, caminos de Dyck o caminos en cuadrículas donde el camino debe quedarse arriba o abajo de una línea diagonal (por ejemplo, $y=x$). Al reflejar la parte del camino que llega hasta el primer punto donde se viola la condición a través de la línea de la frontera, conviertes la restricción geométrica en una propiedad simétrica que puedes contar fácilmente usando coeficientes binomiales básicos.
El truco clave depende de la simetría de la cuadrícula. Si un camino toca o cruza una línea de frontera prohibida $L$, nota que existe un punto específico de "primer contacto". Al reflejar el segmento del camino desde el origen hasta este