Dejemos que $a(n,k)$ sea el número de todos los caminos de Motzkin de longitud $n$ con $k$ pasos hacia abajo y ningún paso horizontal en las alturas positivas. La OEIS A008315 afirma que $a(n,k)=\binom{n}{k}-\binom{n}{k-1}.$ ¿Dónde puedo encontrar una prueba sencilla de este hecho?
Respuesta
¿Demasiados anuncios?
Dejemos que $A(n,k)$ sea el conjunto de caminos de Motzkin que describe.
Dejemos que $B(n,k)$ sea el conjunto de paseos de $(0,0)$ a $(n,n-2k)$ cuyos pasos son todos $(1,1)$ o $(1,-1)$ y que nunca bajan del $x$ eje.
Definir $f:A(n,k)\to B(n,k)$ de la siguiente manera. Dada una trayectoria de Motzkin, sustituir todos los pasos horizontales del suelo por $(1,1)$ pasos. Por ejemplo,
/\/
/\ ==> /\ /
/ \ _ _ /\ _ / \/
A(9, 3) B(9, 3)Afirmo que $f$ es una biyección. El mapa inverso es el siguiente: dado un camino $P$ en $B(n,k)$ , llama a un paso superior de $(x,y)$ a $(x+1,y+1)$ "crítico" si $P$ nunca vuelve a una altura de $y$ después de ese paso. Sustitución de todos los pasos críticos hacia arriba en $P$ con pasos horizontales da una trayectoria $Q$ en $A(n,k)$ para lo cual $f(Q)=P$ .
Por último, el principio de reflexión permite enumerar caminos en $B(n,k)$ para ser exactamente $\binom nk-\binom n{k-1}$ . Es decir, tomar el conjunto de todos los $\binom{n}k$ caminos de $(0,0)$ a $(n,n-2k)$ y restar los caminos malos que en algún momento van por debajo del $x$ eje. Si se refleja que los malos caminos en la primera vez que se sumergen por debajo, se obtiene una correspondencia biyectiva con todos los caminos de $(0,0)$ a $(n,2k-n-2)$ , contados por $\binom{n}{k-1}$ .
