Full transcript
0:02Buenos días, bienvenidos a la clase.
0:06Vamos a
0:08continuar
0:10hablando de funciones generatrices y
0:13esta vez haciendo uso de las reglas que
0:18dedujmos en la clase anterior
0:21que nos permiten
0:24eh convertir directamente desde la
0:30descripción de una clase combinatorial
0:35a eh las ecuaciones de funciones
0:40generatrices que nos permiten
0:42analizarlas. Ah, entonces vamos a partir
0:45recapitulando un poco lo que sabemos y a
0:47partir de ahí vamos a hacer algunos
0:50ejemplos importantes. Ah eh para
0:54recapitular un poco lo que tenemos, ¿no
0:56es cierto?, es que hemos definido
0:58clases combinatorias
1:01donde eh eh
1:05tenemos, por ejemplo, árboles o
1:09secuencias, palabras de un lenguaje
1:12formal, por ejemplo. ¿Okay?
1:15Y eh tenemos una serie de
1:20reglas que nos permiten bypasear el eh
1:24porque el camino normal habíamos dicho
1:26era escribir ecuaciones de la forma a
1:29sub n, bueno, si a su n lo definimos
1:31como el cardinal de a sub n y y y a sub
1:38n
1:40es el conjunto de todos los alfas e
1:44a
1:46tal que el tamaño de alfa igual a n, ¿no
1:48es cierto? Ya. Eh, y ahí escribimos
1:51ecuaciones para los a sub y a partir de
1:53ahí obteníamos las funciones
1:56generatrices con el operador gz que
1:58definimos, ¿cierto?, que está definido
2:01como la sumatoria de a sub n por z a la
2:06n para n mayor o igual que 0. Ya lo que
2:08estamos haciendo aquí es by pasear esto,
2:10e ir directamente para allá, ¿okay? eh a
2:13través de las reglas de composición que
2:15dedujimos.
2:21Y de hecho el albasada eh esto nos
2:25permitió establecer una definición
2:28alternativa de la función generatriz que
2:31en realidad es por supuesto equivalente,
2:33que es que la podemos definir también
2:34como la sumatoria para todo alfa en a de
2:39z elevado al tamaño de alfa. Así,
2:41simplemente, sin ningún coeficiente que
2:44lo multiplique. Ya. Lo que pasa es que,
2:47por supuesto, en esa sumatoria todos los
2:51eh zas que tengan la misma potencia se
2:55van a agrupar, ¿no es cierto? Y y y
2:59¿cómo se agrupan? Bueno, por supuesto,
3:00se agrupan todos los que eh
3:04corresponden a alfas que tienen el mismo
3:06tamaño, ¿no es cierto? Y al agruparse eh
3:09lo que queda es el AU N. Es el es el
3:12cardinal del conjunto de todos los alfa
3:15de A que tienen tamaño N. Así es que es
3:17esa es la demostración de la
3:18equivalencia. Hm. Pero como fórmula es
3:20mucho más simple y en muchos casos nos
3:22va a ayudar eh utilizar eh
3:27esta fórmula
3:29en lugar de la la que habíamos puesto
3:32originalmente, ¿no? Todo depende de un
3:34poco de del contexto.
3:37Entonces, ¿cuáles fueron las reglas?
3:39Decimos que si si a es la suma de dos
3:43clases combinatoriales,
3:47entonces su función generatriz es la
3:50suma de las respectivas funciones
3:51generatrices.
3:55A
3:57es el producto cartesiano de dos clases
4:00combinatoriales,
4:02su función generatriz
4:04es el producto cart el producto
4:06normativ, digamos, producto producto de
4:08funciones generatrices
4:14y sea
4:17ese conjunto de todas las secuencias
4:21de cero o más objetos de
4:24eh de la clase B.
4:28Entonces, A de Z
4:30es 1 parido por 1 - B de Z.
4:36Así es que eso lo
4:39eso lo teníamos y eh vamos a ver ahora
4:43algunas aplicaciones importantes,
4:52ya.
4:54Vamos a comenzar
4:56definiendo una clase atómica,
5:06¿ya? O sea, una clase que consiste de un
5:08solo átomo.
5:11Esa sería una clase B, digamos, que
5:13contiene un solo objeto de tamaño uno.
5:18Ya,
5:21eso es toda la clase.
5:36en una estructura de datos, eso podría
5:38corresponder a un a un nodo dentro de la
5:40estructura, ¿no es cierto? Por supuesto,
5:42una estructura que lo único que consiste
5:43de un nodo no es muy interesante, pero
5:47es el
5:48el ladrillo con el cual se puede
5:50construir un edificio.
5:52Entonces, ¿cuál es e
5:55ustedes cuál sería BDZ? ¿Cuál sería la
5:58función generatriz para esta clase
6:00atómica?
6:04Ah, yo creo que eso les les ayuda a
6:07pensarlo así, ¿no es cierto?
6:10Sumar sobre toda la clase Z elevado al
6:12tamaño del de cada objeto.
6:17Para esta clase tan simple, ¿cuál cuál
6:19vendría a ser su función generatriz?
6:23La constante uno.
6:26No, no, porque tú estás pensando en zer,
6:29¿no es cierto?
6:30Pero z a la 0 quría decir que el tamaño
6:32de alfa es cero. En realidad esta clase
6:34no tiene objeto de tamaño cero.
6:39Z a la 1. Entonces,
6:40Z a la 1. Correcto. Correcto. Z a la 1
6:43porque hay solo un objeto de tamaño uno,
6:45o sea, Z. Okay.
6:49Ya. Y ese ese Z lo vamos a ver mucho, en
6:54por supuesto en al empezar a hacer estas
6:56composiciones y cada vez que vemos Z,
6:59eso lo podemos interpretar como un nodo.
7:02Ah, está diciendo que ahí hay un nodo.
7:07Formemos ahora eh
7:13formemos asterisco.
7:26Esa es la clase que ponemos. La clase A
7:30sería si A es B asterisco,
7:34entonces eh ¿qué contiene esto?
7:38Cero o más repeticiones,
7:41o sea, eh objetos constituidos por cero
7:46átomos, por un átomo, por dos átomos,
7:48por tres átomos y así al infinito, ¿no
7:51es cierto? Entonces está aquí, sí está
7:53el objeto,
7:54el objeto de tamaño cero, está el objeto
7:57de tamaño uno, hay un objeto de tamaño
8:00dos que lo podríamos representar así,
8:03hay un objeto de tamaño tres.
8:06Entonces son como átomos con los cuales
8:07van vamos construyendo moléculas, por
8:09así decirlo.
8:12Entonces, eh si nosotros siguiéramos el
8:16camino original de a partir de aquí, ver
8:18cuánto vale la secuencia su n para n
8:20mayor o igual que 0, la secuencia sub n,
8:25perdón, eh, como secuencia, la secuencia
8:28sub n e sería la secuencia de los
8:31tamaños de todos estos objetos, ¿ya?
8:34Eh, perdón, no, no, no. Es la secuencia
8:36del número de objetos de cada tamaño.
8:38Ahí, ahí lo olvido el anterior. Esa
8:40secuencia de del número de objetos
8:44para cada tamaño. Entonces, para tamaño
8:46cero, ¿cuántos objetos hay? Uno. Ahí lo
8:48estamos viendo.
8:50Para objetos de tamaño uno, ¿cuántos
8:53hay? Solo uno.
8:56Objetos de tamaño dos, ¿cuántos hay?
8:57solo uno y así sucesivamente.
9:03Entonces, a partir de ahí, la secuencia,
9:08la función generativa de Z sería la
9:10sumatoria para n mayor o igual que 0 de
9:13a su n que vale 1 por z a la n, ¿no es
9:16cierto? Y nosotros sabemos que eso vale
9:171/ por 1 - z,
9:21pero también lo podemos hacer más
9:25directamente, ¿no es cierto? Siguiendo
9:29eh el otro camino de decir de recurrir a
9:33esta regla, a la tercera regla que dice
9:36que si a es B estrella, entonces AD Z es
9:391 parido por 1 menz, ¿no es cierto?
9:41Entonces, por ahí tendríamos que a Z
9:46es igual a 1/z,
9:52pero bd ya habíamos visto recién que
9:56vale z. Por lo tanto, a de zido
10:01por 1 men z. Okay, de acuerdo a lo lo
10:05cual, por supuesto, coincide con lo que
10:06habíamos encontrado antes. Tiene que ser
10:08consistente, pero hecho por un por un
10:10camino diferente, ¿no es cierto?
10:13Ya. Eh, vamos al siguiente.
10:19Formemos la siguiente clase.
10:28Una clase C que va a ser B.
10:33O sea, el átomo
10:35más B cruz B.
10:41¿Qué contiene esta clase? Esta clase
10:43contiene un átomo y contiene un objeto
10:46de tamaño dos, ¿no es cierto?
10:51que
10:53lo podemos asimilar
10:57a lo que podría ser una clase en que el
10:59objeto de tamaño dos lo interpretamos
11:02con un dominó
11:06y el objeto de tamaño uno vendría a ser
11:09lo que podríamos llamar un monomino.
11:12He.
11:26[suspiro]
11:28Tenemos entonces una clase que contiene
11:29esos dos
11:33esos dos objetos y ahora formemos
11:39una clase, llamémosla f cursiva
11:43que sea se estrella,
11:47o sea, cero o más repeticiones
11:51de eh
11:56de objetos de la clase C. ¿Ya?
11:59Entonces, ¿qué contendría
12:01la clase F? Primero contendría cero
12:04repeticiones, o sea, el objeto vacío.
12:09Después contendría eh una repetición.
12:13Bueno, entonces es eso
12:17y es eso. Puede ser cualquiera de los
12:19dos, pero solo uno, ¿no es cierto?
12:22Ya, ahora empieza a ponerse más
12:25interesante. Ahora, dos repeticiones.
12:29¿Qué quiere decir dos repeticiones? Que
12:31yo tengo que tomar eh
12:34eh un objeto de la clase P y colocarle
12:39a su a su a su derecha otro objeto de la
12:43misma eh perdón, un objeto de la clase C
12:46y a su derecha otro objeto de la misma
12:48clase C.
12:50Como la casa C tiene dos objetos, yo
12:53tengo eh cuatro maneras de hacer eso,
12:57dependiendo cuál objeto escoja en cada
12:58caso, ¿no es cierto? Entonces, podría
13:00ser que yo eligiera un objeto de tamaño
13:03uno y al lado otro objeto de tamaño uno.
13:06Esa es una posibilidad. Otra posibilidad
13:10es que haya un objeto de tamaño uno y al
13:13lado un objeto de tamaño dos. Ese es
13:16otro.
13:18Otro al revés. Primero un objeto de
13:20tamaño dos
13:22y después un objeto de tamaño, perdón,
13:27esto trata de ayudarme a dibujar y
13:29y no siempre es lo que yo quiero. Ya. Y
13:32por último, un objeto de tamaño dos
13:36con otro objeto de tamaño dos al lado.
13:42Y después empezaríamos
13:45con tres repeticiones
13:48las cuales habría
13:50eh,
13:52¿cuánto? Eh, ocho, ¿cierto? Claro, ocho.
13:58Tengo que en cada oportunidad tengo que
14:00elegir entre dos y tengo tres veces
14:02tienes que hacer eso tres veces.
14:04Entonces, 2 * 2 * 2 y así sucesivamente.
14:07Ah, entonces la la pregunta es eh bueno,
14:11¿cuál sería fz?
14:13Ya.
14:15Eh,
14:19entonces la pregunta es, ¿cuánto vale
14:21fz?
14:25Bueno, tenemos eh
14:29tenemos dos maneras de abordar esto. Ah.
14:32Eh, usando la metodología que que hemos
14:37desarrollado [carraspeo] recién, ¿ya?
14:40Eh, sería fácil porque f es c estrella,
14:43por lo tanto, f de zido
14:49por 1 - c de z.
14:53Ya.
14:56Y ah, y convenientemente se me olvidó en
15:00su momento, estamos a tiempo de de
15:02agregarlo, de decir cuánto sería CDZ.
15:07¿Cuánto sería C de Z? Ayúdenme con eso.
15:12Z + Z².
15:14Perfecto, muchas gracias. Z + Z².
15:18Entonces acá esto sería
15:211/ido por 1
15:24menos
15:26z + z², pero expandamos al tiro el
15:30no hagámoslo por pasos. Ya. Z + Z cu,
15:34¿no es cierto? Y eso es 1/-
15:39z - z².
15:42¿Han visto ustedes esa
15:46función generatriz antes? o algo muy
15:48parecido.
16:00Hace un par de clases atrás más o menos,
16:05¿eh? Sí, ya creo que eran los números
16:08catalanos, ¿no?
16:10Tibio, tibio.
16:12Ah,
16:13bueno, por ahí
16:14los de catalán es uno de los números con
16:16nombre que hemos visto. ¿Cuál es el
16:18otro?
16:20Esto era la función para los árboles
16:23no eso habría sido catalán.
16:25Ya. ¿Cuál es el otro? El que no es
16:26catalán.
16:28Vimos dos tipos de de números famosos.
16:35Fibonacci.
16:36Fibonacci, por supuesto.
16:38Esto es Fibonacci.
16:43O sea, esta clase F es enumerada por los
16:47números de Fibonacci.
16:49Eh, en la cuando vi Fibonacci
16:52arriba en el numerador no había un uno,
16:54había una Z. Ya. Eh, acá no hay Z. ¿Qué
16:58diferencia hace eso? Eh, si yo tomo una
17:01función generatriz y la multiplico por
17:03Z, todos los coeficientes se corren en
17:05uno, ¿no es cierto? Y se rellena con
17:07cero. Todo se multiplica por Z. Se
17:09corrió. ¿Ya? Entonces, quiere decir que
17:12si antes la
17:14sucesión comenzaba con AC, ahora va a
17:17comenzar por 0 AC. Eh, no todo se corre,
17:20pero es la misma sucesión en el fondo.
17:22Ya, o sea, ponerle o quitarle Zo la
17:23desplaza un poquito. Eh, ¿y por qué esta
17:27se desplaza? Porque la Fibonacci que
17:29vimos en la clase era partía con 01 y de
17:32ahí para adelante. En cambio, esta parte
17:34con 1 porque objetos, si ustedes pueden
17:37mirar aquí, objetos de tamaño cero no
17:41hay, perdón, eh,
17:46sí, si hay, pues, eh, objeto de tamaño
17:49cero hay, que es uno. Entonces, el z a
17:51la 0 tiene coeficiente uno. El z a la 1
17:56tiene coeficiente 1. Entonces esta parte
17:58con un 1 y de ahí para arriba. Ya. Eh,
18:04a partir de este de este de esta
18:07expansión que tengo aquí eh cuesta un
18:09poco ver cuántos objetos de cada tamaño
18:11hay porque no están juntos. Ah. Eh, aquí
18:15apareció
18:17un
18:18objeto, por ejemplo, aquí. Bueno, aquí
18:21están todos los de tamaño cero, aquí
18:22están todos los de tamaño uno. Esa parte
18:23es fácil. Los de tamaño dos también
18:26están todos porque son ese y, pero de
18:31tamaño tres no están todos a la vista
18:33aquí, pues porque aquí hay uno, aquí hay
18:36otro también. Esos son de tamaño tres,
18:39pero falta el que sería tres monóminos
18:42seguidos. Ese viene en la siguiente en
18:45la siguiente línea, porque en la
18:46siguiente línea van llegar las
18:47repeticiones de de tres objetos. Ya no
18:50alcanzamos a llegar ahí. Así es. No, no
18:52es tan fácil ver lo que ha simple vista,
18:54pero son los números de de Fibonacci y
18:57solo podemos explicar de
19:00de la siguiente manera. ¿Por qué son los
19:02números de Fibonacci?
19:11Ya,
19:13la idea es la siguiente. Supongamos eh
19:18que
19:21supongamos
19:27que queremos
19:31recubrir
19:35un espacio
19:39de ancho N
19:44con dominos
19:48y monominos.
19:53Ya, o sea, supóng ustedes que tienen un
19:58un una especie de pasillo de largo n y
20:00quieren embaldozarlo
20:01y y las baldosas son de ancho uno, que
20:04son los monominó, o de ancho dos, ¿ya? Y
20:07la pregunta es, ¿de cuántas maneras se
20:08puede hacer eso? ¿De cuántas maneras
20:10distintas se puede hacer ese embaldoado?
20:35Y eso lo podemos ver así. Supongamos que
20:38aquí yo tengo mi espacio de ancho n
20:43y supongamos que hay f n maneras
20:46distintas de de hacer este
20:48recubrimiento, hacer este embaldozado.
20:51Entonces, eso yo lo puedo eh ver
20:58de la siguiente manera.
21:01Esto se puede hacer de dos maneras.
21:05Si mi primer [resoplido]
21:07paso es colocar en el extremo izquierdo
21:10un monómeno,
21:12entonces lo que me resta por hacer
21:14después es que este espacio de tamaño n
21:17-1
21:19se recubra de todas las maneras
21:21posibles, pero el número de manera de
21:23hacer eso por definición es f sub n - 1.
21:27Y la otra alternativa que tengo es
21:30partir poniendo un domino al inicio.
21:33Y en ese caso el espacio restante
21:37es de tamaño n - 2
21:41y
21:42por lo tanto hay f sub n - 2 maneras de
21:46hacerlo. ¿Ya? Y estas dos alternativas
21:51por una parte eh son disjuntas.
21:56Si empieza de una manera, no puede
21:57empezar de la otra, ¿no es cierto? No
21:59hay intersección y son exhaustivas,
22:02cubren todas las posibilidades porque un
22:04embaldoado tiene que empezar con una
22:06maldosa de de tamaño uno o una maldosa
22:09de tamaño dos porque no hay más
22:10opciones. ¿Ya? Por lo tanto,
22:15f es la suma
22:20de las dos posibilidades que surgen,
22:23¿no es cierto? Ya, el que sea exhaustiva
22:26quiere decir que no falta ningún término
22:29y el que sea disjunta quiere decir que
22:31no hay que restar nada porque no hay
22:33intersección
22:35y esto no es otra cosa que Fibonacci.
22:40Entonces ahí está una explicación
22:42intuitiva de por qué esto es Fibonacci.
22:49¿Quedó claro? ¿Alguna pregunta sobre
22:51esto?
22:54Todo. Claro.
22:55Sí. Eh, bonita aplicación de esto. Y y
22:59esta otra es bien importante
23:02que son los árboles binarios, la
23:04enumeración de árboles binarios.
23:15Eh,
23:17la la numeración que nosotros hicimos eh
23:20cuando primero resolvimos este problema
23:22de contar cuántos árboles binarios hay
23:24de tamaño fue bastante laboriosa porque
23:26tuvimos que escribir una una ecuación de
23:30recurrencia que eh a primera vista se
23:33veía como inagarrable, pero que
23:37afortunadamente tenía la forma de una
23:39convolución, así que pudimos aplicar la
23:42la regla que tenemos para convoluciones
23:43y así se simplificó mucho. Ya. Y
23:46llegamos a la ecuación de de catalán.
23:48Acá con este enfoque es mucho más simple
23:51porque si yo tengo mi clase B que son
23:55que es la clase atómica que contiene un
23:58solo nodo
23:59y que habíamos dicho que B de Z
24:02era Z, ¿no es cierto?
24:05Si formo la clase A,
24:09la clase
24:12de los árbol de todos los árboles
24:14binarios
24:24eh formados
24:29con nodos de la clase B, ¿no es cierto?
24:35ya
24:38que eh esa sería, ¿no es cierto? Sería
24:42primero la el objeto vacío, ¿no es
24:45cierto?
24:47Un árbol que tiene cero nodos, que se lo
24:50representamos más bien por un cuadradito
24:52que una aguja, ¿ya? O el que el árbol
24:55que tiene solo un nodo o el árbol que
24:57tiene dos nodos así, ¿no es cierto?
25:01que ahí tengo dos o el que tiene tres,
25:10etcétera, clase infinita. Esa es la
25:12clase que quiero formar, pero esa la
25:14clase yo la puedo de describir de manera
25:17muy simple con una ecuación de clases
25:20que me dice que la clase A está
25:24constituida ya sea por
25:28un árbol
25:30pasivo, ¿no es cierto? un árbol que no
25:32tiene nodos, un árbol de tamaño cero. O
25:36bien,
25:37y esta es una unión disjunta porque eh
25:40la alternativa, por un lado están los
25:42árboles vacíos y por otro lado están los
25:44árboles no vacíos. Y los árboles no
25:46vacíos yo los puedo describir como que
25:48tienen una raíz que es un nodo de la
25:51clase B, ¿no es cierto?
25:54y, o sea, enumerado por Z y dos árboles
26:00colgando uno a cada lado, ya, que son
26:05árboles de la misma clase A.
26:09Y
26:11y esa es la ecuación. Todos los árboles
26:13son descritos por esa ecuación.
26:17Esto, su función generatriz es uno,
26:21¿cierto? Y esto, su función generatriz
26:25sería
26:27eh o más que la función generatriz, yo
26:30esto lo puedo describir como eh A cruz B
26:36cruz A, ¿no es cierto?
26:39y eso me conduce a eh z * b de z²,
26:48¿no? Y por lo tanto,
26:56por lo tanto,
26:58eh, ADZ,
27:02eh, perdón, me equivoqué aquí, profe,
27:04debería, o sea, vamos a corregir al
27:06tiro.
27:17Esto es A de Z²,
27:23¿ya? Porque es A el que está repetido. B
27:27es Z y A es A de Z. Así que entonces la
27:32ecuación que queda es 1 + Z * A de Z
27:39cuadrado
27:41y eso no es cosa que la ecuación de
27:43catalán.
27:46Así es que en el caso de los árboles
27:47binarios de una manera ultra expedita,
27:50¿no es cierto?, eh llegamos a la a la
27:54ecuación
27:57eh de catalán, ¿ya?
28:01Okay. Ya. A ver, ¿qué más? Eh,
28:07ah, creo que tengo otro ejemplo. Déjenme
28:09buscarlo
28:11antes de pasar a a a un tema bien
28:14interesante que ya viene.
28:18Es ya me encontrado el ejemplo
28:22y aprovecho
28:25ponerlo al tiro aquí. Ya, este vendría a
28:28ser entonces el número cinco. Ya, cinco.
28:34Contar triangulaciones.
28:50La pregunta es, ¿de cuántas maneras
28:52distintas
29:03se puede
29:05triangular
29:11un polígono?
29:19convexo
29:24con n + 2 vértices.
29:35Ya.
29:36por te voy a explicar aquí por
29:43porque ese es esa cifra de n + 2, ¿no es
29:46cierto? Y no porque decir un polígono de
29:48n vértices para n may igual que yo
29:50quiero partir con n igual a 0 y y
29:53polígonos de cero vértices no hay
29:56polígonos de un vértice
29:59supongo que sería un punto no más eso,
30:03¿no? No es muy interesante. Así que
30:04vamos a partir con el
30:07eh
30:09esta ha triangula un polígono que es un
30:12punto.
30:13Ya olvidémonos de esos casos. Partamos
30:16con el primer caso que sí parece tener
30:19sentido, que es el caso n = 0.
30:23Ya, el caso igual cer es un polígono con
30:27eh dos vértices, o sea, sería esto. Ese
30:31es el polígono.
30:33Y llamemos t sub n al número de
30:35triangulaciones.
30:37Bueno, hay solo una manera de triangular
30:39eso, pues ya está triangulado.
30:44Caso n = 1 sería con tres vértices. Es
30:46sería más interesante.
30:49En realidad no voy a dibujar ese
30:50puntito,
30:52sería algo así. Ya. Y ese también ya
30:57está triangulado. Hay solo una manera de
30:58hacerlo. Así que el primero que es
31:00interesante ese n = 2, que sería uno de
31:04cuatro vértices, ya digamos
31:09algo así. Ah,
31:12disculpe que sale medio tembloroso el
31:14dibujo. Bueno, y este este yo tengo dos
31:17maneras de triangularlo.
31:20Ya,
31:23déjeme dibujarlo dos veces.
31:34Profesor, perdón.
31:35Sí,
31:37queda triangular.
31:39¿Cómo?
31:40que es triangular.
31:41Aquí lo vas a ver
31:44inmediatamente.
31:46Eh,
31:48triangular es eh conectar vértices de
31:51modo que el polígono quede eh convertido
31:57en un conjunto de triángulos, ¿ya?
31:59Entonces, yo puedo hacer esto.
32:02Entonces, queda el triángulo
32:05eh [carraspeo] queda queda dividido en
32:07dos triángulos, ¿cierto? este triángulo
32:09de arriba y este triángulo de abajo.
32:11¿Okay? Y
32:15también yo podría hacer eso
32:17y ahí también queda dividido en dos
32:19triángulos y y es una triangulación
32:22distinta de la de la anterior, ¿ya? Así
32:25es que,
32:26¿y por qué no igual cer es un entonces
32:27no debería ser cero si no hay ningún
32:29triángulo?
32:31Ah.
32:36Ah. Podría ser. Ah, porque
32:44será podría ser de Yo creo que eso no
32:45cambia. Tengo me queda claro cómo cómo
32:50tú en ese caso
32:53eh
33:08No, yo creo que está bien. Yo está bien
33:09que es uno. ¿Sabes por qué? Porque dado
33:12cualquier eh cualquier eh polígono que
33:15queremos triangular, le tiramos un
33:17montón de líneas adentro e que no se
33:20intersecten
33:22y [carraspeo] las máximas que podamos
33:26hasta que quede dividido en un conjunto
33:29de triángulo. Ya en el caso que estamos
33:33viendo en IG 2 queda dividido en dos
33:36triángulos, ¿no es cierto? En el caso n
33:39= 1 queda dividido en un triángulo que
33:41está viendo. En el caso n = 0 tiene cero
33:44triángulos.
33:45Tiene cero triángulos. Ya no hay ningún
33:48triángulo,
33:49pero hay una manera de hacerlo.
33:52Ya.
33:53Ah, ya. Okay.
33:53Claro, hay una manera de dividir ese
33:55polígono en cero triángulos. Ya. Y como
33:58estamos contrando un número de maneras,
33:59por eso es que es uno. Es cierto que hay
34:01cero triángulos allí adentro, pero hay
34:03una manera de hacerlo.
34:05Esa es la esa es la razón por la cual es
34:07uno.
34:07Entonces este caso acá serían dos,
34:10¿no es cierto? Y
34:14bueno, y qué sé yo. Y entonces en un
34:17caso mucho más grande, por ejemplo, aquí
34:21seguramente va a dar muchas maneras, ¿no
34:23es cierto? Ya. Y podría decir ya podría
34:26ser este, perdón, esta está poniendo
34:29otro color.
34:33Ya podrí este va aquí, después
34:38ahí acá
34:41y después podría ser aquí. Ahí está
34:44dividido en un, dos, 3, cuatro
34:45triángulos, ¿no es cierto? Ya, pero como
34:48esa debe haber montones de otras maneras
34:50de triangular eso mismo. Y la pregunta
34:51es, ¿cuántas son? Okay, ese esa es la
34:55idea ya porque yo tengo muchas eh esta
34:59triangulación la hice de una forma, pero
35:00la podría haber hecho de otra forma. Por
35:02ejemplo, una manera que podría haber
35:03hecho es colocarme en el acá en ese
35:05vértice de arriba y tirar líneas hacia
35:09cada uno de los otros vértices. Acá,
35:11acá, acá. Es una manera, ¿no es cierto?
35:13Ya. Entonces, la pregunta, por supuesto,
35:15es de cuántas maneras son y eso lo
35:19podemos ver de la siguiente forma.
35:38Para evitar eh contar como
35:42triangulaciones distintas, algunas que
35:44que en realidad no lo son, lo que vamos
35:46a hacer es vamos a a tomar uno de los de
35:50los lados como la base del del
35:57polígono, ya designamos a un
35:58arbitrariamente uno de los lados lo
36:00designamos como la base del polígono y
36:04eh
36:07y eh
36:10entonces eh con eso evitamos que al
36:13tomar distintas lados como base me
36:15pudieran dar triangulaciones
36:17presuntamente distintas, pero que en
36:19realidad son la misma. Ya. Entonces, la
36:21idea va a ser que vamos a tomar una base
36:23aquí. Ya, esa es la base del polígono y
36:25sobre eso está construido todo el resto,
36:30por ejemplo. ¿Ya? Y eh
36:37entonces eh
36:42yo voy a
36:44Bueno, y vamos llamemos a llamemos T.
36:51Ya. Eh, esa parece que bastante raro,
36:55¿no?
36:57Ya. A ver,
37:04eso que peor. Ya, pero intenta hacer una
37:08T cursiva.
37:11Ya. recursió e que es la clase S.
37:36Ya.
37:37Entonces,
37:39ese
37:41esa base
37:43va a participar de un triángulo, ¿no es
37:45cierto? Para que sea una triangulación.
37:48Eh, entonces lo que tenemos que ver es
37:50cuál es el vértice opuesto de alguna
37:54manera que eh
37:57completa el triángulo al cual pertenece
37:59esto. Como estamos tratando de encontrar
38:02todas las triangulaciones posibles, cada
38:04uno de los otros vértices puede ser el
38:06que lo acompaña, ¿no es cierto? Eh, y
38:08hay que contar todos esos casos.
38:10Entonces, supongamos que fuera este
38:12vértice de aquí arriba, el que está
38:13acompañando la base en en una
38:15triangulación en particular. Entonces,
38:17yo tengo esto ya.
38:21Entonces, ahí tengo un triángulo. ¿Dónde
38:23están todos los demás triángulos? Bueno,
38:26está eh esta
38:30este polígono que apareció a la
38:32izquierda, ¿no es cierto? Al tirar esa
38:34línea, aquí apareció un polígono. Bueno,
38:37ese como queremos encontrar todas las
38:39triangulaciones posibles, una vez que yo
38:41ya fijé este triángulo, tengo que ver de
38:44triangular lo que quedó aquí a la
38:45izquierda. de todas las maneras
38:46posibles, ¿ya?
38:50Y acá a la derecha quedó otro polígono,
38:51en este caso mer triángulo, pero podría
38:53ha sido un polígono con muchos lados.
38:54Ya, ese polígono que queda al lado
38:57derecho también hay que estrangularlo de
38:59todas las maneras posibles para poder
39:00generar todas las triangulaciones
39:01posibles. Por lo tanto, lo que yo tengo
39:05aquí a la izquierda, lo que aparece, lo
39:06que falta poner a la izquierda para
39:10triangular e para generar todas las
39:12triangulaciones posibles, es poner aquí
39:15a la izquierda
39:20todas las triangulaciones posibles para
39:23ese polí. y acá a la derecha todas las
39:26triangulaciones posibles para ese
39:28polígono. Y eso me conduce
39:32a escribir una ecuación de clases que
39:35dice que el conjunto de todas las clases
39:37posibles, de todas las triangulaciones
39:39posibles. Ya. Y ahora, ojo, aquí no para
39:45un número dado
39:48eh vértices,
39:50no. Estas son, este es el conjunto
39:52infinito de todas las triangulaciones
39:54posibles, o sea, de todos los polinomes
39:55triangulados en el fondo, ¿ya? Tal como
39:59antes hemos dicho el conjunto de todos
40:00los árboles posibles, que conjunto
40:01infinito, ¿ya? Y después lo reducimos a
40:04tamaño n, pero en la primera prximación
40:07trabajamos con todo, ¿ya? Eh, entonces
40:10el conjunto de todas las triangulaciones
40:12posibles, todos los polinomios
40:13triangulados, va a tener esta
40:16estructura, va a tener este triángulo
40:19que está ahí al medio, pongámoslo de
40:21color naranja,
40:25¿ya? Y a la izquierda
40:30van a estar todas las triangulaciones
40:31posibles que yo pueda poner ahí y a la
40:33derecha todas las triangulaciones
40:35posibles que yo puedo poner acá.
40:37Ya. Y estas son todas las
40:39triangulaciones
40:41no vacías, ¿no se está garantizado que
40:44son no vacías porque tienen por lo menos
40:45el triángulo del medio.
40:49Y el caso base es este. Es la
40:52triangulación vacía. Ya. Triangulación
40:55que tiene cero triángulos.
40:58Y ahí tengo una ecuación.
41:01Esta ecuación de clases describe el
41:04conjunto de todas las
41:07de todos los eh
41:10polígonos
41:12triangulados. Ya. Y
41:16entonces aquí a partir de aquí yo puedo
41:19deducir que t de z
41:22va a ser igual a 1, ¿no es cierto?
41:25Porque eh esa triangulación vacía, su su
41:30función generatriz es 1
41:34más z, que representa un triángulo. Ya
41:38los nodos con los cuales yo estoy
41:40construyendo esto son los triángulos,
41:43¿eh? Y t al cuadrado porque hay una
41:47triangulación a cada lado.
41:51Y esa ecuación la acabamos de ver. Esta
41:53es la ecuación de catalán,
41:57¿ya? Así es que de aquí inmediato
42:00podríamos decir que el número
42:04de maneras
42:08de triangular
42:16un polígono
42:21de n + 2 lados
42:24convexo
42:29de n + 2 lados
42:31es 1/ido por n + 1 2n sobre n, ¿cierto?
42:36Porque esos son los números de catalán.
42:40Las triangulaciones también entonces
42:42entran dentro de la categoría de las eh
42:49de las de los objetos que nosotros
42:53podemos enumerar. eh con este método que
42:56hemos encontrado y que nos da los
42:58números de catalán. Okay,
43:01ya. Entonces, eh
43:05avancemos. Vamos a dar ahora a como
43:10tiempo. Sí,
43:12lo siguiente que vamos a ver aquí cuánto
43:15comencemos. Saltémonos una página y
43:17vamos al tiro a la siguiente. Eh, vamos
43:19a hablar de recubrimientos con dominó.
43:22Ya trujimos un poco de estos dominos,
43:24pero ahora no vamos a olvidar de los
43:26monominos y vamos a trabajar
43:28exclusivamente con domino.
43:40Y esto está tomado directamente del
43:43libro de Graham, Kanut y Batashnik.
43:49Matemáticas concretas. ah uno de los dos
43:51libros que le he dado como referencia,
43:54así que
43:56les recomiendo que vayan a leerlo ahí,
43:58que es la fuente.
43:59Caso que yo me equivoque en algo, no lo
44:02describa bien, ahí está mucho mejor
44:04descrito de lo que yo puedo hacer. Ah,
44:06pero veámoslo porque es un problema bien
44:09interesante que plantean ahí con Patashn
44:12que lo hacen de una manera bien, yo
44:13diría, como audaz en cuanto al enfoque
44:16de solución.
44:18E ya. Entonces vamos a suponer,
44:24supongamos
44:26que tenemos
44:31dominos, dominos regulares, ¿no es
44:33cierto?
44:35Eh, que están boca abajo. Ah,
44:46face downía en inglés. Eh, ¿qué crees
44:49que está en boca abajo? Que no veo
44:50cuántas pintas tienen. Esa ese por eso.
44:53Ah, o sea, eh, yo veo solo como que
44:56están todos en blanco.
44:58Para que no hay manera de distinguir un
45:00dominado de otro. Así ya. Y
45:05o sea, ya eh son por tanto son así.
45:10Así se ven los dominos. Ya. Eh, estos
45:13dominados
45:21pueden estar
45:23en posición
45:28horizontal
45:33o vertical,
45:37¿ya? O sea, pueden estar así,
45:40pero también pueden estar puestos así.
45:46Y el problema
45:52es de cuánta o la pregunta
46:06se puede
46:09recubrir
46:13un rectángulo.
46:19de 2 por n
46:22con estos dominos.
46:48Ya voy voy a usar la anotación de graja
46:50crónicotasnica, que se es básicamente la
46:54misma que hemos usado, solo que ellos
46:56usan letras normales para identificar a
47:00las clases en vez de cursiva.
47:03Eh, y viendo el tipo de lechas que
47:06aparece después, prefiero seguir su
47:09práctica en esta en esta sección. Ah,
47:15para no enredarme. Así que ya. Entonces,
47:18eh, la idea es que yo tengo yo tengo un
47:22rectángulo de altura dos y ancho n que
47:26quiero recubrir con dominó, ¿no es
47:28cierto?
47:30Entonces, eh, por ejemplo, ya yo podría
47:33decir, mire, aquí tengo este espacio.
47:37Entonces,
47:39podría haber un dominado vertical aquí,
47:41por ejemplo, y aquí podrían haber dos
47:44horizontales
47:45y acá otro par de horizontales
47:49y acá vertical,
47:52vertical y un par de horizontales aquí,
47:55por ejemplo.
47:57Eso es un ejemplo.
47:59Y esto es de ancho 1 2 3 4 5 6 7 8 9,
48:03¿no es cierto?
48:05Y de altura dos, por supuesto. ¿Ya?
48:08Entonces, un ejemplo de cómo yo podría
48:10recubrir un rectángulo de 2x 9, pero hay
48:13muchísimas otras maneras de hacerlo.
48:16Entonces, ¿cómo yo puedo eh enfocar
48:18esto? Bueno, este problema lo podemos
48:21resolver de inmediato de una manera más
48:24bien clásica, ¿no es cierto? Que sería
48:28decir, mire, eh si este
48:32este es un recubrimiento de 2 * n,
48:36entonces lo que yo puedo ver es cómo
48:38comienza ya. Y tiene dos maneras de
48:41comenzar. El primero como en el ejemplo
48:45anterior que acabo de poner, comenzar
48:46por un dominó vertical. Y en ese caso el
48:51resto tiene que ser un recubrimiento. Si
48:54si este era de largo n, el resto tiene
48:57que ser un recubrimiento de largo n - 1,
49:00¿no es cierto?
49:01Y la otra posibilidad
49:03es partir colocando un dominó horizontal
49:07y un dominatoriamente
49:10que ir acompañado de otro domino
49:11horizontal debajo. No hay no hay manera
49:15de de hacerlo distinto, ¿no es cierto?
49:17Y en ese caso el resto
49:20es eh tiene que ser
49:23de ancho n - 2. Y nuevamente estas dos
49:27posibilidades son
49:30disjuntas, ¿no es cierto? Y son
49:32exhaustivas. Por lo tanto, si yo llamo
49:36TDN
49:38al número de maneras
49:42ya de recubrir este
49:47el rectángulo
49:51de 2* n.
49:54A partir de ahí, yo puedo escribir de
49:56inmediato la ecuación que dice
50:01que el número de maneras de recurrir un
50:03rectángulo de ancho n es igual al número
50:07de maneras recurrir un rectángulo de
50:09ancho n - 1, ¿no es cierto? ahí arriba
50:12más el número de maneras de recurrir un
50:14de recurrir un rectángulo de ancho n -
50:172. Ya. Y si fuera un rectángulo de ancho
50:20cero, hay unas un un recubrimiento de un
50:24rectángulo que colapsa a ser solo una
50:26línea, ¿no es cierto?, vertical. Hay es
50:31un recubrimiento vacío, pero hay una
50:32manera de hacerlo que es no poner nada y
50:34listo. Y
50:37si fuera un rectángulo de ancho uno, ahí
50:40cabe exactamente un dominó vertical y
50:43nada más. O sea, hay una manera de
50:44hacerlo también. Y eso,
50:48como ustedes ya a esta altura se habrán
50:49dado cuenta, por lo repetitivo
50:52es que esto es Fibonacci.
50:54Así es que la solución en realidad ya la
50:57tenemos.
50:58Y no es raro porque en realidad acabamos
51:01de hacer este mismo problema hace unos
51:03minutos porque a pesar de que se ve
51:06distinto, este es el mismo problema que
51:07vimos de los dominóos y los monominó.
51:09Piensen que esto eh en lugar de verlo
51:13así como una
51:16eh un recubrimiento de un rectángulo dos
51:18por n, tomáramos una fuente de luz hacia
51:23abajo y viéramos la sombra de los
51:25dominos. Ah, y la sombra de los
51:28dominóos, cuando el dominó está
51:29vertical, esa sombra es un monominó. Y
51:32cuando hay un par de dominó
51:33horizontales, ¿no es cierto? La sombra
51:36de eso hacia abajo es un dominó. En
51:39cuando hablamos de dominos monominó,
51:41entonces estamos hablando de cómo
51:42recubrir un espacio HN con dominos y
51:44monominos, que fue el problema que
51:45resolvimos. Así que no es raro que que
51:48que salga esto como
51:51respuesta, ¿no es cierto? Entonces, ¿por
51:52qué lo estamos haciendo? Porque hay otra
51:55esto porque en este capítulo como les
51:57digo, tomado de Graham Patashnik,
52:00hay otra manera de verlo y esa es la que
52:03nos interesa.
52:06Y a la pasada vamos a encontrar
52:07resultados que hasta ahora no habíamos
52:08visto.
52:13La idea ah es llamar T sin n T no más.
52:19Y este y este es el que vendría a ser el
52:21T cursiva en la anotación anterior. Es
52:24la clase
52:26de todos los recubrimientos de altura
52:28dos.
52:43de cualquier ancho,
52:52¿ya?
52:55O sea, una clase infinita.
52:57Entonces, esta clase, ¿qué es lo que
52:58contiene? Esta clase contiene de partida
53:04el el recubrimiento vacío, ¿no es
53:06cierto? Cuando la clase cuando el
53:08rectángulo se ha hecho cero. Es una
53:10línea vertical que yo la puedo
53:13representar así como una línea vertical
53:14aquí. Ahí está. Ya.
53:17Ahora, esa línea se parece muchísimo a
53:20un uno
53:21y está bien porque se comporta como un
53:24uno, ¿no es cierto? Cuando lo
53:25transformemos en función generatriz, la
53:28función generatriz de un recurrimiento
53:30de ancho cero es uno, porque hay una
53:35sola manera de hacerlo, es un zero.
53:39Ya se parece a un uno y está bien porque
53:41se comporta como un uno.
53:45Y
53:47luego vienen los recubrimientos
53:52de ancho uno que vendrían a ser que
53:56vendría a ser solo ese.
53:59Hay un recubrimiento de ancho uno y
54:01luego los recubrimientos de ancho dos
54:04que son dos.
54:07Uno es cuando yo tengo dos dominos
54:09horizontales,
54:12eh, y el otro es cuando tengo dos
54:15dominos verticales.
54:18Ambos son de
54:19ancho dos y luego los de ancho tres que
54:24comenz podríamos comenzar con los tres
54:30verticales
54:33y o podría haber un vertical con dos
54:37horizontales al lado. También puede ser,
54:40¿no es cierto?
54:41o
54:44dos horizontales
54:46con un vertical al lado
54:49y creo que no hay más recobrimiento de
54:51tamaño tres, no, no hay otra manera de
54:54hacer un rectángulo de ancho tres con
54:56estos dominados.
54:58Ya. Bueno, y todo lo que sigue ah, es un
55:01conjunto infinito.
55:04Entonces, este
55:06conjunto
55:09lo podemos
55:11eh
55:13lo podemos
55:16esta esta serie infinita de de
55:19recubrimientos
55:21la podemos agrupar.
55:24¿De qué manera? Por un lado, dejamos a
55:27todos los recubrimientos
55:30que eh, o sea, todos los recumentos de
55:33hecho cero, que es solo ese. Ya. Y
55:36después descartado eso, o sea, es el
55:38recubrimiento vacío. Tengo los
55:40recubrimientos no vacíos.
55:42Los recubrimientos no vacíos
55:46pueden comenzar por un rectángulo
55:47vertical
55:49y en ese caso lo que viene a
55:50continuación a la derecha es un
55:53recubrimiento
55:56ya de cualquier ancho. Recuerden que
56:00estamos formando todos los
56:01recubrimientos posibles. Así es que en
56:03ese t que acabo de escribir ahí están
56:05desde el recubrimiento vacío en
56:06adelante. Está bien, porque si al al
56:09concatenarle a la derecha
56:12un recubrimiento vacío, lo que queda es
56:14un simple dominado vertical que no tiene
56:17nada a la derecha, lo cual está bien. Ya
56:19es una de las posibilidades.
56:21Y la otra posibilidad es que esto
56:22comience con dos
56:27con dos horizontales
56:33y lo que viene de ahí a continuación es
56:36cualquier recubrimiento
56:38de tamaño
56:40cero o mayor que cero.
56:45Y esto lo puedo escribir
56:48como que la clase t es igual
56:52a digamos uno, o sea, recurriento vacío
56:58más
57:03un dominical
57:09o bien dos dominos horizontales seguidos
57:11de t.
57:13Y aquí tengo una ecuación de clases,
57:17¿cierto?
57:18Y esto es de la forma
57:28t = 1 + xt, ¿cierto? Donde x sería lo
57:35que está entre paréntesis ahí. Y esto se
57:38puede desenrollar.
57:49Eh, entonces t es 1 + x
57:59y t es 1 + xt por la misma ecuación,
58:05o sea, 1 + x + x² t, ¿cierto?
58:13x seguido de X
58:15y acá desenrollo nuevo. Entonces, 1 + x
58:19+ x²
58:221 + xt,
58:25eso va a ser 1 + x + x²
58:31+ x³
58:34t.
58:35y así sucesivamente, o sea, por esta vía
58:38llegamos a 1 + x + x² al infinitum, o
58:45sea, la sumatoria de x a la
58:50a la k para k mayor o igual que 0.
58:55Y eso es,
58:57no, antes de llegar a eso, borremos
59:00último,
59:05ya porque antes de llegar a eso, esto
59:08que estamos viendo aquí no es otra cosa
59:10que x estrella.
59:13Cero o más repeticiones de
59:17cero o más repeticiones de de x.
59:20Ya. Y
59:24ahora si t es esa suma infinita,
59:29eh xt
59:32sería eh
59:35x + x² + x³, etcétera, ¿no es cierto? O
59:40sea,
59:42yo multiplico a la izquierda por x cada
59:44uno de estos términos de esta sumatoria.
59:49Y si ahora yo
59:52formo t - xt,
59:57¿cierto? La serie completa t menos la
1:00:00serie XT. Eh, se cancela casi todo lo
1:00:03que queda es uno
1:00:05y esto de la izquierda es eh 1 - x * t y
1:00:10eso es igual a 1. Y de ahí yo puedo
1:00:14despejar
1:00:16y
1:00:17decir que t es 1/ido por 1 - x, ¿ya? que
1:00:23corresponde con lo que hemos
1:00:24desarrollado antes como funciones
1:00:25generatrices. Aquí la el paso audaz es
1:00:28que lo estamos incluso manejando como eh
1:00:31como una como algo puedo escribir para
1:00:33las propias para las mismas clases, no
1:00:35no para las funciones generatrices, sino
1:00:36que para las clases mismas, ¿no? Eh,
1:00:39ahora, ¿qué significa 1 parido por 1- x
1:00:41cuando x es una clase combinatorial?
1:00:43¿Ya? Eh, bueno, lo que pasa es que
1:00:45podemos tomar esto como una definición.
1:00:52Podemos tomar esto.
1:01:07O sea, yo puedo definir 1 partido por
1:01:11por 1,
1:01:13no
1:01:16-
1:01:19puedo definirlo
1:01:22como 1 + x + x² + x³, etcétera.
1:01:30O sea, sumatoria de x a la y para y
1:01:34mayor o igual que 0.
1:01:37Puedo tomar eso como la definición de de
1:01:401 parido por 1- x0
1:01:43o más repeticiones de objetos de la
1:01:45clase x.
1:01:47Y en este caso
1:01:54t es 1/ido por 1 men un domino vertical
1:02:01más dos dominos horizontales,
1:02:07¿ya?
1:02:10O lo que es lo mismo o lo que les decía
1:02:12recién es
1:02:15un domino
1:02:19vertical más
1:02:22dos dominos horizontales
1:02:24estrellas.
1:02:27¿Ya?
1:02:29Y
1:02:31y yo puedo decir, puedo afirmar
1:02:35de que esto es intuitivamente obvio,
1:02:46ya porque
1:02:56Y por qué digo que es intuitivamente
1:02:59obvio? Tomemos un recubrimiento
1:03:01cualquiera.
1:03:14Ya. Por ejemplo,
1:03:17un domino vertical,
1:03:22un par horizontal,
1:03:24otro par horizontal.
1:03:28vertical
1:03:30vertical
1:03:33par horizontal
1:03:35terminando con un vertical. Es un
1:03:37recurrimiento cualquiera, ¿no es cierto?
1:03:40Entonces, ahora yo puedo venir
1:03:44y eh
1:03:47tomando un destacador puedo pintar de
1:03:53color naranja, por ejemplo,
1:03:56los dominos verticales que veo
1:04:00ya
1:04:01y
1:04:03eso corresponde a esto, ¿no es cierto? y
1:04:05puedo venir y pintar de otro color,
1:04:07verde, digamos, los dominos horizontales
1:04:10que veo.
1:04:12Y eso serían estos. Ya. Y lo que estamos
1:04:15viendo aquí
1:04:17es
1:04:20una secuencia, lo que estamos viendo
1:04:22aquí abajo
1:04:24es una secuencia de dominóos de de un
1:04:29tipo o del otro entre mezclados de
1:04:31cualquier manera, ¿ya? O sea, es una
1:04:33repetición de objetos de esta clase. Sí,
1:04:38en cada oportunidad yo tomo un objeto de
1:04:40esta clase y lo escribo. Tomo la
1:04:42siguiente alguno de esta clase y lo voy
1:04:44escribiendo. Ya. Y en cada oportunidad
1:04:46tengo las dos opciones, pero puede ser
1:04:48cualquiera de los de la clase. Así que
1:04:50si esto lo veo como una palabra escrito
1:04:54en un alfabeto, este es como un alfabeto
1:04:56que tiene dos letras. Ya, la letra A es
1:04:59un domino vertical, la letra B es un par
1:05:02horizontal y ese es mi ese es mi
1:05:06alfabeto y yo quiero formar el conjunto
1:05:09de todas las palabras que puedo escribir
1:05:11con ese alfabeto y esta es una de esas
1:05:13palabras, ¿no es cierto? Y así hay, por
1:05:15supuesto, infinitas palabras yo puedo
1:05:17escribir con letras de este alfabeto,
1:05:19comenzando por la palabra vacía y
1:05:22después las palabras de una letra A o B.
1:05:25Después las palabras de dos letras, A,
1:05:27A, A, B, BA, BB y así sucesivamente. Ya.
1:05:32Y ese es el
1:05:34esa es la esa es la la intuición detrás
1:05:37de lo que tenemos acá. Ah, ahora esto es
1:05:43a nivel de todavía son eh ecuaciones de
1:05:46de clases. Ah, vamos ahora acercándonos
1:05:49a las funciones generatrices.
1:05:51Eh,
1:05:53entonces vamos a decir lo siguiente.
1:05:55Supongamos
1:06:01eh, ¿qué queremos saber?
1:06:05¿Cuántos
1:06:14recubrimientos
1:06:21tienen
1:06:23un cierto número
1:06:31de dominos verticales?
1:06:35y dominos horizontales.
1:06:40Ya. Por ejemplo, ¿cuántos recubrimientos
1:06:43hay que tengan? Como lo que estamos
1:06:45viendo ahí, ¿cuántos recubrimientos hay
1:06:47que tengan eh en este caso, casualmente
1:06:52cuatro dominos verticales y cuatro y ah,
1:06:55no, son más. ¿Ya? Entonces, ¿cuántos
1:06:58recubrimientos hay que tengan cuatro
1:06:59dominos verticales, los que están
1:07:00marcados naranja, y seis dominos
1:07:03horizontales, los que están marcados en
1:07:05verde. Ya, ese es uno, pero puede haber
1:07:07muchísimo, ¿no es cierto? Entonces,
1:07:09¿cómo yo puedo eh responder esa pregunta
1:07:12bien específica? Ya eh [carraspeo]
1:07:18hasta ahora la descripción que yo he
1:07:21logrado generar en base a esto es
1:07:24completamente detallada.
1:07:27me está diciendo dónde está cada dominó
1:07:29y en qué posición está. Para responder a
1:07:32la pregunta de cuántos recubrimientos
1:07:33tienen un cierto número de dominos de un
1:07:35tipo y del otro, no necesito todo ese
1:07:39esa minuciosidad. De hecho, lo que
1:07:41necesito es ignorarla. Ah, por ejemplo,
1:07:45si estos
1:07:51si estos dominos horizontales no
1:07:53estuvieran aquí, sino que estuvieran más
1:07:55acá al final, ¿ya? Para el caso da lo
1:07:58mismo porque el número de dominos
1:08:00horizontales no cambia, ¿no es cierto?
1:08:01Entonces, yo tengo que contar este y
1:08:04tengo que contar la otra. Tengo que de
1:08:05alguna manera conseguir que se agrupen
1:08:08ya. Y lo mismo, da lo mismo la posición
1:08:11donde estén los los dominos marcados
1:08:14naranja, lo que importa es cuántos son,
1:08:18que son cuatro.
1:08:20Entonces, la forma que tengo de lograr
1:08:23que todas estas cosas se agrupen y que
1:08:26las todas las que se ven distinto se
1:08:28transformen en lo mismo para fines de
1:08:30agruparlas es considerar que esta
1:08:33multiplicación de dominó, que en
1:08:34realidad es una concatenación, ¿no es
1:08:36cierto? Eh, es como colocar letras de un
1:08:39alfabeto una al lado de la otra. ah eh
1:08:42que esta multiplicación
1:08:44tratarla como que fuera conmutativa,
1:08:47porque hasta ahora esta multiplicación
1:08:50no es conmutativa,
1:08:52ya un vertical con dos horizontales al
1:08:55lado es distinto de dos horizontales con
1:08:59un vertical al lado, pero yo necesito
1:09:03que se consideren
1:09:05la misma para fines de agruparla.
1:09:08Entonces, y eso lo lo consigo haciendo,
1:09:10como les digo, que la multiplicación sea
1:09:12conmutativa. Esa es la eso es lo que
1:09:14vamos a hacer. Entonces, eh
1:09:18para esto
1:09:25vamos
1:09:28a suponer
1:09:32que la operación de multiplicación que
1:09:35estamos viendo aquí
1:09:41de dominos
1:09:46es conmutativa.
1:09:52Ya.
1:09:55Entonces,
1:09:57la ecuación que dice que t es 1 menos
1:10:03vertical más dos horizontales
1:10:07superpuestos
1:10:10se transforma
1:10:12en se se convierte en realidad en 1
1:10:18parido por 1 menos
1:10:21vertical más horizontal. al cuadrado,
1:10:27¿ya? Pues lo mismo,
1:10:30lo que importa que son dos, ¿ya? Y esto
1:10:33ahora yo lo puedo expandir como la
1:10:36sumatoria para acá es mayor o igual que
1:10:38er0 de
1:10:41vertical
1:10:43más horizontal al cuadrado elevado a la
1:10:46k, ¿no es cierto?
1:10:48cero o más repeticiones.
1:10:51Y
1:10:53ahora que la multiplicación es
1:10:54conmutativa, yo puedo aplicar el teorema
1:10:56del binomio. Hacemos esto como un
1:10:58pequeño paréntesis. el teorema del
1:10:59binomio
1:11:05que me dice que
1:11:09a + b a la k
1:11:13es la sumatoria 0 menor o igual que i
1:11:17menor o igual que k
1:11:19de k sobre i
1:11:22a a la i b a la k - i no es cierto eso
1:11:26teema del binomio.
1:11:29Y si yo lo quiero poner como en forma
1:11:33eh
1:11:34simétrica, yo puedo escribir esto como
1:11:37la sumatoria sobre todo y j mayor o
1:11:40igual que 0 tal que i + j = n, no,
1:11:43perdón, igual a k en este caso
1:11:46de de
1:11:50coeficiente binomial simétrico y com j
1:11:54por a a la i b a la Ja,
1:12:00así es que con ese paréntesis
1:12:03puedo pasar a escribir que t
1:12:07es la suma para k mayor o igual que 0
1:12:11y ahora expando con el binomio. Entonces
1:12:13la suma sobre todo i j mayor o igual que
1:12:180 tal que i + j = k
1:12:23de i j
1:12:28eh el a sería
1:12:31vertical vertical a la i
1:12:34y el b sería horizontal al cuadrado,
1:12:37entonces sería horizontal
1:12:40a la 2j.
1:12:44Ya. Y ahora nuevamente
1:12:48esto que ya lo hemos hecho varias veces,
1:12:49así es que debería ser como casi
1:12:51automático ya es este barrido sobre
1:12:55todos los hij mayor igual que 0 tal que
1:12:57má j = k. A medida que yo voy variando
1:13:00el K, en realidad termino barriendo todo
1:13:03el cuadrante, todo y J mayor o igual que
1:13:050. Así es que esto
1:13:08puedo escribir como la sumatoria sobre
1:13:11todo i y i y i j mayor o igual que 0
1:13:15de i com j
1:13:18vertical
1:13:20a la i
1:13:26horizontal a las 2 jto
1:13:38Y fíjense lo que tenemos aquí.
1:13:43Aquí tengo
1:13:47el
1:13:49exponente I, que me está diciendo que
1:13:51hay dominos verticales.
1:13:54Y acá tengo este exponente
1:13:582J
1:14:00que me dice que hay 2 J dominos
1:14:02horizontales
1:14:06e y por y todo entonces y y acá
1:14:10está el coeficiente que los multiplica,
1:14:13lo cual entonces me quiere quiere decir
1:14:15que si yo he agrupado todos los
1:14:18recubrimientos que tienen y dominos
1:14:20verticales
1:14:22y 2 Ja,
1:14:25dominos horizontales.
1:14:27Al agruparlos, el número de sumandos que
1:14:30se agrupan, eh multiplicando a esas dos
1:14:34potencias de dominó es y com j.
1:14:37O sea, esto no es otra cosa que el
1:14:40número de maneras
1:14:45de recubrir
1:14:49usando
1:14:53y dominos verticales
1:14:57y 2 J dominos, perdón, horizontales.
1:15:10Ya. Y eso
1:15:14responde
1:15:16la pregunta que habíamos planteado.
1:15:19Supongamos que queremos saber cuántos
1:15:20recorrimientos tienen un cierto número
1:15:22de verticales y horizontales. No,
1:15:26aquí podemos decir que el número el
1:15:29número de recubrimientos que tienen i
1:15:31dominóos verticales y 2 j dominos
1:15:34horizontales es i J. El coeficiente
1:15:39binomial simétrico de I J.
1:15:43Eh,
1:15:47y esto
1:15:50y esto yo diría que es nuevamente
1:15:53intuitivamente obvio.
1:16:01Ahora, es bien interesante esto porque
1:16:05estos problemas de recubrimiento con
1:16:06dominos, ¿no es cierto?, o con dominos y
1:16:08monuminos.
1:16:11Eh,
1:16:13es e
1:16:17no no en la
1:16:20el par de veces anteriores que lo
1:16:21habíamos visto dentro de esta misma
1:16:22clase nos conducía directo a Fibonacci,
1:16:25pero aquí estamos pasando por un paso
1:16:28intermedio
1:16:30en donde
1:16:32hemos llegado a los coeficientes
1:16:33binomiales, que ¿qué tienen que ver los
1:16:36coeficientes binomiales al final con
1:16:38Fibonache? Pero aparecen los
1:16:39coeficientes binomiales y lo que yo les
1:16:41digo es que intuitivamente obvio. ¿Por
1:16:44qué es intuitivamente obvio? Ah eh,
1:16:47supongamos
1:16:52que
1:16:55queremos saber
1:17:02de cuántas maneras
1:17:09podemos escribir
1:17:16palabra en un lenguaje formal
1:17:20con
1:17:22i letras
1:17:24A
1:17:27y J
1:17:29letras
1:17:31B.
1:17:32Ya,
1:17:34por ejemplo,
1:17:36mire, yo quiero = 2
1:17:39eh j = 3.
1:17:43Ya. Entonces, yo podría tener ya una
1:17:45podría ser a A BB, ¿no es cierto? Esa
1:17:48tiene 2A y 3B, pero también podría ser
1:17:53AB
1:17:55o podría ser B A
1:17:59BB.
1:18:00Ya, hasta pa A.
1:18:05Ya. Y por último, ya podríamos terminar
1:18:08con B
1:18:10A, ¿cierto? Están todas ahí. La pregunta
1:18:13es, ¿cuántas son?
1:18:15Ya. Eh,
1:18:19si tomamos nuestro destacador aquí
1:18:22podemos marcar las letras P con verde,
1:18:29ya las A con naranja.
1:18:35Ya. Y ahí la pregunta sería, ah, y
1:18:40y el ancho
1:18:44el ancho de todo esto tiene que ser I +
1:18:46J, ¿no es cierto?
1:18:51Porque hay I letras A y J letras B. Así
1:18:54que en total es I + J. Y la pregunta es,
1:18:57¿de cuántas maneras? ¿De cuántas
1:18:59maneras? Si yo tengo este espacio de
1:19:01ancho y ma j, de cuántas maneras yo
1:19:04puedo eh pintar y de estos espacios en
1:19:08naranja y los restantes en verde. Ya.
1:19:14Eh, en fondo esto un problema
1:19:18combinatorio o de, ¿no es cierto?
1:19:21Básico. De cuántas maneras yo puedo
1:19:23elegir y objetos para pintar los
1:19:25naranjas dentro de I + J o
1:19:28simétricamente de cuántas maneras yo
1:19:30puedo escoger J objetos para pintarlos
1:19:33de verde eh dentro de I + J. Ya. Bueno,
1:19:37el número de maneras
1:19:42el número de maneras
1:19:46por definición de los coeficientes
1:19:47binomiales, es
1:19:51i + j sobre i, ¿no es cierto? ¿De
1:19:53cuántas maneras yo puedo escoger i
1:19:55objetos dentro de i + j?
1:19:58O lo que es lo mismo, de cuántas maneras
1:20:00yo puedo escribir escoger j objetos
1:20:02dentro de + j.
1:20:04Eh, eh es lo mismo, ¿no?
1:20:08Y ambas corresponden a lo que nosotros
1:20:10hemos definido como el coeficiente
1:20:12binomial simétrico y com j.
1:20:14Así que ahí tengo la solución. Por eso
1:20:17es que i + j. Una vez que yo elijo cuál
1:20:20es i posiciones pintar naranja, cuál es
1:20:22J posición pintar verde, de cuánta
1:20:24manera lo puedo hacer de I+ J manera. Y
1:20:26por eso es que es intuitivamente obvio
1:20:28que el número de maneras de hacer estos
1:20:30recubrimientos tiene que ser I + J.
1:20:33Ya,
1:20:36ya. Entonces, hemos encontrado que este
1:20:38problema de recubrimiento de dominó nos
1:20:40conduce coeficientes binomiales.
1:20:43Pero, ¿y qué pasa con con de dónde de
1:20:47dónde aparece Fibonacci? Ah, miren aquí.
1:20:51Y me quedan pocos minutos, pero en esos
1:20:53pocos minutos alcanzo a mostrarlo. ¿Cómo
1:20:55aparece Fibonacchi aquí?
1:20:57Supongamos ahora
1:21:08que
1:21:10no nos interesa
1:21:15distinguir
1:21:20entre
1:21:23horizontal
1:21:25y vertical.
1:21:28Ya, o sea, no nos interesa si el dominó
1:21:30está así o así. Lo que nos interesa es
1:21:32que es un dominó. Ya. Si yo elimino esa
1:21:36distinción,
1:21:37entonces ya no estoy hablando de que en
1:21:40un recubrimiento hay dominos verticales
1:21:42y y dos jizontales. Estoy hablando que
1:21:45en una recubrimiento hay n dominos, ¿no
1:21:49es cierto? Porque ya no distingo unos de
1:21:51otros. ¿Cómo logro eliminar la
1:21:54distinción entre uno y otro? Muy fácil.
1:21:58reemplazando ambos por el mismo símbolo.
1:22:01Si ambos son reemplazados por el mismo
1:22:02símbolo, entonces no tengo manera de
1:22:05distinguirlos en la enumeración,
1:22:07¿cierto? Entonces,
1:22:11para esto
1:22:16reemplazamos
1:22:21ambos dominos.
1:22:27por el mismo símbolo.
1:22:30Ah,
1:22:42ambos dominos.
1:22:46por por el mismo símbolo
1:22:54Z. Lo llamamos Z. Entonces, donde había
1:22:57un dominó vertical decimos, hay un
1:22:59domino. Donde había un dominó horizontal
1:23:02decimos, hay un dominó. ¿Ya? Y entonces
1:23:07nuestra
1:23:09t, que era, habíamos dicho acá
1:23:17que era 1 parido por 1 menos vertical
1:23:20menos horizontal al cuadrado, ¿cierto?
1:23:25que era 1 parido por 1 men vertical más
1:23:31horizontal al cuadrado. Ahí vamos.
1:23:35Al eliminar la distinción entre un tipo
1:23:37de dominio y el otro, ahora t es 1/o por
1:23:401 men z + z cu. O sea, que es lo mismo
1:23:46que 1/ por 1 - z - z cu, o sea,
1:23:51Fibonacci.
1:23:56F aparece en el último minuto cuando
1:23:58eliminamos la distinción entre los
1:23:59dominos. Ahí, ahí está. Okay.
1:24:04Eh, perfecto. Y esto parece entonces un
1:24:06buen momento para
1:24:09para concluir esta esta clase. Entre
1:24:13paréntesis
1:24:15escondido. Aquí hay una identidad de
1:24:17números de Fonchip, ¿cierto? Porque eh
1:24:21aliminar la distinción entre uno y otro,
1:24:26yo lo que genero es un agrupamiento.
1:24:29¿Ya? Entonces, lo que estoy diciendo es
1:24:31que al agrupar
1:24:33cosas
1:24:35de este tipo,
1:24:39¿ya? Al poner aquí Z, entonces quedaría
1:24:43Z a la i y acá quedaría z a la 2J, ¿ya?
1:24:47O sea, sería z a la i + 2j.
1:24:51Entonces, cuando eh el z a la i + 2j
1:24:55está multiplicado por i + j. Pero otro
1:24:58por por otra parte esta misma serie yo
1:25:00sé que si la expreso como sumatoria
1:25:02sobre n mayor o igual que 0, ya de en
1:25:06que acá lo que tengo simplemente es un
1:25:07dominó z a la n, el coeficiente que
1:25:10multiplica es un número de fon.
1:25:12Entonces, si yo tengo dos expresiones
1:25:14para la misma serie, eh yo puedo
1:25:17identificar términos y ahí va a aparecer
1:25:20una identidad de en que va voy a poder
1:25:24expresar un número de fh en término de
1:25:26una sumatoria de coeficientes
1:25:28binomiales. Así que les dejo como
1:25:31ejercicio ahí que tratan de descubrir
1:25:34cuál es esa identidad. Ah eh poco
1:25:37probable que sea una identidad nueva.
1:25:39Hay miles y miles de identidades de
1:25:42número de Fibonacci que se conocen y hay
1:25:43incluso un journal que se llama el
1:25:45Fibonacche Quarterly que que publica
1:25:47cosas, así que sería muy poco probable
1:25:49que esta no hubiera sido descubierta,
1:25:50pero igual le dejo como un ejercicio
1:25:53interesante a partir de aquí tratar de
1:25:55encontrar cuál es la identidad del
1:25:57número de Fibonacci que vincula número
1:25:59de Fibonacci con coeficientes binomiales
1:26:00que está escondida dentro de lo que
1:26:02acabamos de hacer. Y eso por hoy eh
1:26:07sería todo ya.
1:26:10Muchas gracias por por haber venido.
1:26:14Gracias, profesor. Profesor, tengo una
1:26:15duda.
1:26:16Dime no más.
1:26:18Eh, esto es más arriba así en las
1:26:20triangulaciones que me quedé con la
1:26:21duda.
1:26:23El polinomio. Usted hizo un triángulo.
1:26:25Es un polígono. Polígono.
1:26:27Polígono. Claro. Hace un triángulo y lo
1:26:29dividen después en dos subproblemas. El
1:26:32triángulo más dos subpremas.
1:26:34¿Por qué no se podría trazar una línea
1:26:35no más y dividirlo directamente en dos
1:26:37subremas?
1:26:40Oh, oh, oh, oh.
1:26:46Porque necesitáis agregar a un
1:26:48triángulo, según yo, ¿o no?
1:26:50Claro, porque por esa vía es posible que
1:26:52nunca aparezcan triángulos. Tengo que
1:26:54garantizar que por lo menos un triángulo
1:26:57porque tengo una triangulación no vacía,
1:26:59así que tiene que haber por lo menos un
1:27:00triángulo. Entonces, yo yo identifico
1:27:03ese un triángulo y y y completo todo lo
1:27:05que falta. Ah, ahora lo que él dice,
1:27:08¿por qué no podría haber tenido una pura
1:27:10líneair?
1:27:12Eh,
1:27:17ah,
1:27:20tengo que pensar un poco más, ¿no?
1:27:22¿Alguien tiene respuesta?
1:27:25O sea, a mí se me ocurre de que al final
1:27:27llegaríamos al caso base, que era como
1:27:29la línea sola y si no estamos agregando
1:27:33un triángulo en cada paso que estamos
1:27:35haciendo como el paso recursivo,
1:27:37entonces no estamos agregando nada, no
1:27:39simplemente estamos aplicando una
1:27:41función es como, okay, aplícala dos
1:27:43veces, pero no estamos agregando nada,
1:27:46como que eso se me ocurre a mí, sobre
1:27:47todo el
1:27:48No, yo yo estoy pensando la misma
1:27:50sentido, pero me cuesta un poco
1:27:52precisarlo. Mira, vamos a pensarlo. Pero
1:27:56buena pregunta. Gracias.
1:27:59Con eso cerramos la clase. Ya estamos
1:28:01pasados en la hora.
1:28:04Muchas gracias. Que bonita semana
1:28:07también. Buena semana.