Buenas Nicolás,
Te recomiendo que llames de alguna manera a los vértices inicial y final, pongamos y respectivamente.
Estoy de acuerdo contigo que hay precisamente caminos cualesquiera de longitud que inician en . Pero hay muchos de ellos que, luego del paso , ya están en el vértice y por lo tanto no van a poder terminar en el vértice tras agregar un paso. Es por eso que no funciona tu conteo (ese "paso" que agregas a cada uno de los caminos no es siempre posible, y esto te lleva a contar en exceso).
Hay diversas maneras para resolver este ejercicio. Comento en lo que sigue una posibilidad, que es mediante recurrencias.
Si llamas , y a la cantidad de caminos que inician en el vértice , tienen longitud y terminan respectivamente en los vértices
, , o entonces como todos los caminos de longitud que empiezan en son , la regla de la suma nos dice que .
Por simetría tenemos que . Reemplazando en la primera igualdad tenemos que .
Además todo camino de longitud que termina en viene de o bien de , por lo que
, y como tenemos que . Reemplazando nuevamente tenemos que , y cancelando un factor común obtenemos que con dato inicial .
Hemos obtenido una recurrencia lineal de orden 1 no homogénea. Su solución homogénea es y al buscar una particular de la forma encontramos . Luego y como resulta que . Esto significa que y que . De esta manera obtenemos la respuesta .
En la última clase de consultas hubo un estudiante que ha planteado una manera alternativa, que consiste en lleva a palabras binarias poniendo si nos movemos en un sentido o si nos movemos en sentido contrario. Hay que contar las palabras de largo cuya suma es de la forma para algún entero . Es un modo alternativo.
En términos probabilísticos, si te tomas paseos al azar en el triángulo vas a notar que, a medida que la longitud de los caminos crecen al infinito, un tercio de los caminos van a terminar en cada vértice. Entonces sabemos que asintóticamente la sucesión crece como . El largo impar "favorece" a terminar en y el par "desfavorece"; de ahí que tenemos los y sumando y restando en la solución de la recurrencia. Esto es un enfoque "intuitivo" hacia la solución.
Cordiales saludos,
Pablo.
Te recomiendo que llames de alguna manera a los vértices inicial y final, pongamos y respectivamente.
Estoy de acuerdo contigo que hay precisamente caminos cualesquiera de longitud que inician en . Pero hay muchos de ellos que, luego del paso , ya están en el vértice y por lo tanto no van a poder terminar en el vértice tras agregar un paso. Es por eso que no funciona tu conteo (ese "paso" que agregas a cada uno de los caminos no es siempre posible, y esto te lleva a contar en exceso).
Hay diversas maneras para resolver este ejercicio. Comento en lo que sigue una posibilidad, que es mediante recurrencias.
Si llamas , y a la cantidad de caminos que inician en el vértice , tienen longitud y terminan respectivamente en los vértices
, , o entonces como todos los caminos de longitud que empiezan en son , la regla de la suma nos dice que .
Por simetría tenemos que . Reemplazando en la primera igualdad tenemos que .
Además todo camino de longitud que termina en viene de o bien de , por lo que
, y como tenemos que . Reemplazando nuevamente tenemos que , y cancelando un factor común obtenemos que con dato inicial .
Hemos obtenido una recurrencia lineal de orden 1 no homogénea. Su solución homogénea es y al buscar una particular de la forma encontramos . Luego y como resulta que . Esto significa que y que . De esta manera obtenemos la respuesta .
En la última clase de consultas hubo un estudiante que ha planteado una manera alternativa, que consiste en lleva a palabras binarias poniendo si nos movemos en un sentido o si nos movemos en sentido contrario. Hay que contar las palabras de largo cuya suma es de la forma para algún entero . Es un modo alternativo.
En términos probabilísticos, si te tomas paseos al azar en el triángulo vas a notar que, a medida que la longitud de los caminos crecen al infinito, un tercio de los caminos van a terminar en cada vértice. Entonces sabemos que asintóticamente la sucesión crece como . El largo impar "favorece" a terminar en y el par "desfavorece"; de ahí que tenemos los y sumando y restando en la solución de la recurrencia. Esto es un enfoque "intuitivo" hacia la solución.
Cordiales saludos,
Pablo.