Full transcript
0:02Buenos días, bienvenidos a la clase.
0:06Hoy día vamos a continuar eh con el
0:10análisis de árboles de búsqueda
0:11binarias, del número de árboles de
0:12búsqueda binaria que estamos haciendo.
0:19En realidad de árboles binarios, más que
0:20busqué binario. Análisis del número
0:24de árboles binarios.
0:40En la clase pasada habíamos llegado a
0:42encontrar una expansión en serie
0:47para la función generatriz del número de
0:49árboles de de árboles binarios. Y esa
0:52función generatriz tenía esta forma,
0:55eh, 1/2
0:57sobre n + 1
1:00por -1 a la n
1:03* 2 a la 2n + 1
1:08por z a la n. Ya. Y habíamos eh a partir
1:13de ahí extraído el coeficiente, ¿no es
1:17cierto? E
1:20ya todo esto que está aquí multiplicando
1:22al z a la n
1:25es
1:26el número que andamos buscando.
1:30Okay. Entonces, a su n,
1:33que es el coeficiente que multiplica z a
1:36la n de z. Eso significa esta anotación.
1:41Es eh como les decía, 1/2 sobre n + 1
1:46por -1 a la n.
1:48por 2 a la 2n + 1 y nada más hasta ahí.
1:52Ah eh y pudimos comprobar evaluando
1:56numéricamente esta fórmula que
1:58efectivamente coincide con los números
2:01que deberían dar. Así que tenemos
2:03bastante confianza que está bien solo,
2:05como les dije al final de la clase
2:06pasada, que es una fórmula que todavía
2:08necesita
2:10un poco de simplificación, ¿no?
2:19Y de qué manera lo vamos a hacer.
2:21Recordemos qué cosa es eh
2:24qué fórmulas tenemos para el coeficiente
2:26binomial, especialmente cuando lo que va
2:29en la parte superior no es un entero.
2:31Ah.
2:32Entonces, recordemos
2:38que eh alfa sobre n
2:42lo podemos escribir como eh alfa a la n
2:48descendente dividido por n factorial,
2:51donde alfa a la n descendente es alfa *
2:54alfa - 1, etcétera, hasta alfa - n + 1
3:01dividido por n factorial, ¿no es cierto?
3:03Y
3:06entonces aquí son n factores.
3:15Esa es la fórmula que tenemos. Entonces,
3:181/2
3:20sobre n + 1
3:25sería cuánto, sería 1/2 medio, ¿cierto?
3:291/2 - 1
3:341/2 - 2
3:37hasta
3:391/io
3:41eh menos
3:44n + 1 que es lo que hay abajo, más 1 eh
3:49se cancela. Ahí hay un -1 con un +1 que
3:51se cancela y queda un medio men n
3:56esto divido por n factorial.
3:58Okay.
4:01Eh, calculemos cuánto vale cada uno de
4:03estos factores. El primero es 1/2.
4:06El segundo e un un 1/2 un 1/ -1 es -
4:101/2.
4:14El tercero sería 1/2 - 4/2 sería -3/2.
4:23Ya. Y el último, si lo calculamos con
4:26cuidado, va a ser menos 2n - 1
4:31medios
4:33y todo eso dividido por n factorial.
4:36Okay.
4:45Okay. E
4:48bien, eh, ¿cuántos factores hay arriba?
4:50eh n + 1, ¿no es cierto?
4:53porque corresponde a esto, a n + 1
4:57factores.
4:59Por lo tanto, si saco todos los
5:02denominadores dos que hay ahí, me va a
5:04quedar un 2 a la n + 1 abajo
5:10y hay un -1 a la e
5:14y de estos n más subctores hay hay n que
5:17que tienen signo menos, así es que hay
5:19un -1 a la nquas
5:25cosas para fuera, lo que me queda es 1 *
5:283 * 5, ¿no es cierto? 1 * 3 * 5 los
5:34imparé
5:36hasta eh 2n - 1
5:42y eso dividido por n factorial. ¿Okay?
5:48Entonces, lo que vamos a hacer ahora es
5:50lo siguiente. Vamos, bueno, vamos a
5:52reescribir esto
6:01y vamos a escribir el 1, el 3, el 5, eh,
6:07hasta el 2n - 1.
6:13Y
6:16a ver, espérense un poquito. Tengo un
6:18error que he venido acarreando aquí. E
6:22no me había dado cuenta.
6:24Este no es n factorial,
6:27sino que es
6:29n + 1 factorial,
6:33¿cierto? por lo que les dije antes,
6:35porque corresponde a esto. Ya, disculpen
6:38eso. Así que aprovechemos de corregirlo
6:42y alguien que lea después este apunte no
6:44va a saber que estuvo malo en algún
6:46momento.
6:49Más uno
6:52que también.
6:59Okay. Entonces, tengo eso.
7:02Intencionalmente lo escribí un poquito
7:03más espaciado y aquí tengo un n + 1
7:07factorial.
7:08Ya. ¿Y por qué escribí eso espaciado?
7:12Porque ahora quiero agregar lo que
7:14falta. Entonces, voy a poner aquí el
7:17dos,
7:19el 4,
7:20el 6, ¿no es cierto? Y el 2n.
7:27Entonces agregué
7:29n n factores,
7:34cada uno de ellos tiene un factor dos,
7:36así que si lo si saco para fuera ese
7:37factor dos, me va a quedar un 2 a la n
7:41y al quitarle un factor 2 a cada uno de
7:43ellos va a quedar 1 por 2 por 3 hasta
7:46por n, o sea, n factorial.
7:51Ya, eso ya se está empezando a ver un
7:53poquito mejor.
7:57Entonces, ¿esto cómo está quedando? Eh,
8:01queda como 1 di 2 a la 2n + 1, ¿cierto?
8:08Juntando los dos, 2 a la n y 2n + 1 que
8:11están abajo, hay un -1 a la n.
8:17Arriba lo que yo tengo es un 2n
8:19factorial.
8:24Y abajo lo que tengo es un
8:29n factorial por un n + 1 factorial. Ah,
8:32lo voy a escribir como n factorial
8:35cuadrado y el n + 1 restante lo dejo
8:38afuera. Ahí. Eso.
8:42Y ahora vamos a ir a reemplazar a en
8:47este lugar aquí, en esta fórmula,
8:51porque todo lo que estado haciendo es
8:52trabajar con este 1/io sobre n + 1.
8:55Entonces, lo que obtuve aquí ya lo voy a
9:00eh multiplicar por -1 a la n * 2 a la 2n
9:02+ 1.
9:05De hecho, ni siquiera debería
9:06escribirlo, ¿no? Porque ustedes lo van a
9:08ver de inmediato. Este -1 a la n va a
9:10cancelar a este -1 a la n que hay aquí y
9:14este 2 a la 2n + 1 va a cancelar a este
9:182 a la 2n + 1 que está acá. Así que en
9:20realidad eh lo que queda es esto. Ya.
9:24Entonces vamos directamente ahí mejor.
9:30Por lo tanto,
9:33a su
9:34es
9:362n factorial.
9:39dividido por n factorial al cuadrado
9:42y multiplicado ahí abajo por n + 1 y eso
9:47es 1 di por n + 1
9:512 n sobre n
9:56y estos esta es la solución
10:02esta es la solución que es bien conocida
10:04para el número de árboles binarios con n
10:07nodos es 2n sobre n dividido por n + 1
10:12son los números de catalán
10:20ya y los hemos encontrado entonces a
10:22través de este proceso que comenzó por
10:26escribir una
10:28ecuación de recurrencia que contenía una
10:32convolución
10:34aplicar funciones generatriz, lo cual
10:36nos llevó a una ecuación
10:38eh bastante más compacta que se podía
10:41resolver algebraicamente y a partir de
10:45ahí obtuvimos una la función generatriz
10:47que la expandimos en serie usando el
10:48termo del binomio y llegamos a a esta
10:51fórmula que hemos eh
10:54eh simplificado hoy día para llegar a a
10:57esto que es la
11:00fórmula bien conocida
11:02para el número de árboles binarios con n
11:06dos.
11:11Okay.
11:16¿Alguna pregunta sobre esto?
11:21Me alegro de de ver las cámaras de
11:24algunos de ustedes, particular la conocí
11:26en persona el otro día en el pasillo. No
11:30la reconocí en el primer momento porque
11:33hasta entonces solo había sido un
11:34rectángulo negro, pero
11:37siempre me me da mucho gusto encontrarme
11:40con mis estudiantes, sobre todo en este
11:41curso que rara vez nos vemos en persona,
11:44¿no?
11:46Bien, antes de de pasar a a lo que
11:51quiero llegar a ver en esta clase, eh,
11:54le vamos a dar otra mirada al mismo
11:55problema.
12:13Es,
12:15a ver, tenemos lo que podemos llamar la
12:17ecuación de catalán
12:28que dice que a de Z
12:31es 1
12:33+ Z * A Z²,
12:37¿no? Esa esa fue la ecuación compacta
12:40que yo les decía a la que habíamos
12:41llegado que la resolvimos
12:43algebraicamente. Una ecuación de segundo
12:45grado.
12:47Descartamos una de las dos soluciones
12:49que encontramos porque no cumplía con la
12:51condición de borde y eh nos quedamos con
12:56con la solución que sí nos servía.
12:58¿Okay?
13:01Hay un teorema que
13:04solo lo voy a enunciar, no lo no lo
13:06vamos a demostrar, que es el teorema de
13:09inversión de la granche.
13:16Si ustedes están interesados en en los
13:18detalles, les recomiendo que vayan a ver
13:20el libro de de Flly Cic Analytic
13:24Combinatorics, que en los links del
13:27curso hay un puntero a la a una versión
13:30digital.
13:33Eh,
13:35que dice lo siguiente. Si a de Z
13:39cumple una ecuación de la forma z
13:43por fi de A de Z,
13:47ya esa Z no quedó muy bien. A ver,
13:52eso igual también quedó rara.
13:58Ahí está mejor. Z por fi de A de Z.
14:03Eh, sí, es una función, pero es una
14:05función que depende solo de AD Z. No
14:07depende de Z, por ejemplo,
14:08independientemente, sino que solo de AD
14:10Z. ¿Ya? Entonces,
14:16A sub n se puede obtener de la siguiente
14:18manera. Así que a sub n, que es el
14:21coeficiente de z a la n dentro de z,
14:23como dijimos,
14:26se puede obtener como u no partido por n
14:30por el coeficiente que multiplica a u a
14:33la n - 1
14:36dentro de fi de u
14:40a la n.
14:42Esa función fi
14:46la loamos en un parámetro u, la elevamos
14:48a la n y extraemos el coeficiente que
14:51multiplica a u a la n - 1. Eso se divide
14:53por n y da exactamente el coeficiente
14:56sub n que andamos buscando.
14:59Veamos si nos sirve en este caso
15:02para
15:03profe.
15:04Sí.
15:05¿Qué significa eso de los paréntesis
15:08cuadrados que encierran a Zn y a U
15:10elevado n- 1?
15:12Gracias, gracias por la pregunta. Eh,
15:14como les decía, esto notación,
15:18esta notación significa el coeficiente
15:22que multiplica a z la n dez. Entonces,
15:25la idea es que yo expando a de Z en
15:26serie,
15:28veo el término eh veo el término de
15:32grado n dentro de la expansión que Z
15:35tiene exponente n y veo que coeficiente
15:38la está multiplicando y ese coeficiente
15:41es lo que entrega esta anotación.
15:44Okay. Entonces,
15:46sí, sintiendo, me acordé.
15:48Me permite extraer cualquier coeficiente
15:50dentro de una serie.
15:54Entonces, para aplicar este teorema,
16:03eh necesitamos
16:10que la ecuación
16:15sea de la forma
16:21a Z.
16:24igual z
16:26por
16:29algo que represente a una función
16:33que depende
16:37depende dice ahí solo de AD Z. Tenemos
16:42que ponerla así.
16:44Eh,
16:46esta ecuación que tenemos aquí
16:53no lamentablemente no corresponde
16:56exactamente a a ese formato.
17:00Eh, porque esta esto no depende solo de
17:05este aquí, esto no es de la forma z por
17:08una función que depende solo de Z. Si yo
17:11saco un factor Z para fuera, como
17:12necesito hacerlo, lo que va a quedar es
17:141/ z + a z²
17:18casi. Ah, depende de AD z, pero también
17:21depende de Z en el 1/ido por Z y por lo
17:23tanto falla. Ah, entonces lo lo que yo
17:25necesitaría sería poder sacar el Z para
17:29fuera
17:31e y
17:34y y que lo que quede eh dependa solo de
17:38Z. Okay. Eh, no depende de la variable
17:41Z. Entonces, ¿cómo lo puedo hacer?
17:44Resulta que en este caso, y eso esto lo
17:46vamos a ver más adelante, pero se los
17:49anticipo porque nos da la intuición.
17:52Esta ecuación que estamos viendo aquí
17:56tiene un gran paralelo con con lo que es
18:00la estructura de los árboles mismos.
18:02Eh, más adelante vamos a ver de que esta
18:04ecuación yo la puedo leer de la
18:05siguiente manera. Puedo decir,
18:08todo árbol binario ya consiste ya sea de
18:14puede ser una hoja,
18:17ya una hoja tiene cero nodos, ¿no es
18:22cierto? Porque eh el árbol consiste de
18:24nodos internos, que son los que yo estoy
18:25contando, y hojas que están colgando,
18:28que no las estoy contando. Entonces, un
18:31el árbol puede ser una simple hoja y en
18:35ese caso eh es un Z al acero, ¿no es
18:38cierto? Porque es un ese árbol que es
18:42una simple hoja tiene eh
18:46es un árbol, un árbol que tiene cero
18:49nodos, por eso tiene 1 por Z a la 0 y
18:53nada más. Entonces uno este uno
18:55representa esa hoja. Y la otra
18:57alternativa que es de junta, por eso
19:00suma, es que contengo un nodo raíz y ese
19:04nodo raíz es eh yo lo represento por Z
19:09porque es un nodo que tiene un es un
19:12objeto que tiene un solo nodo interno,
19:14por lo tanto es un objeto de tamaño uno,
19:18entonces 1*ado por z a la 1. Ya, el
19:21exponente es el que me va indicando el
19:22tamaño de los objetos.
19:24Entonces, un Z. Y a eso están colgando
19:27dos árboles, uno a cada lado
19:29recursivamente.
19:31Entonces, y esos son los ese es el ADZ
19:33al cuadrado que ustedes ven. Ya son los
19:36dos árboles que están colgando. Entonces
19:38esto tiene un paralelo muy cercano con
19:40lo que es la estructura del árbol. Un
19:42árbol puede ser una hoja o bien una raíz
19:44con dos árboles colgando. Más adelante
19:46vamos a ver que lo podemos leer así casi
19:48de corrido. Ah, y vamos a ver cuál es la
19:50el fundamento matemático para que eso yo
19:53lo pueda hacer. Pero esto se lo se los
19:54anticipo desde ya. Ah, entonces si
19:59yo quisiera que esta fórmula yo le
20:01pudiera sacar un factor Z fuera y no me
20:03quedara este 1 dividido por Z que me
20:06complica, lo que yo podría hacer es
20:08decir, mire, voy a contar tanto las
20:11hojas como los nodos internos. Ambos yo
20:14los voy a contar. Entonces, un nodo
20:16interno se representa por Z porque es un
20:19nodo de los que estoy contando, eh, que
20:22tiene tamaño uno. Y las hojas, si yo las
20:25cuento, en ese caso también van a ser un
20:28nodo que estoy contando de tamaño eh
20:31uno, así que también va a ser un Z a la
20:331. Y este uno va a dejar de ser un uno
20:36en mi fórmula, va a pasar un a ser un Z
20:39y de esa manera yo lo voy a poder
20:40factorizar. Entonces, esa es la
20:42intuición. Así que déjenme decirle ahora
20:45eh escribir ahora lo que lo que vamos a
20:46hacer. No, pero la intuición es de ahí y
20:49de ahí viene el que va a aparecer un Z
20:50en lugar del uno. Entonces, para
20:56obtener
20:58una ecuación de esta forma,
21:10consideremos
21:15árboles
21:21en que los nodos
21:24externos,
21:28llamamos las hojas,
21:33eh también se cuentan como nodos.
21:46Entonces para n = 1,
21:53yo ese sería mi único árbol, ¿no?
21:57Entonces esto sería eh este sería la sub
22:00nun n vale 1. En este caso para n = 2.
22:05¿Qué pasa con n = 2? No hay ningún árbol
22:08que tenga dos nodos. Si es que yo estoy
22:10contando tanto nodos internos como
22:13externos, ya e porque el siguiente árbol
22:17que viene después de este es el que
22:18tiene un nodo, una pequeña raíz y dos
22:21hojas colgando, pero ese tiene tres
22:23nodos, así es que dos nodos no hay. Ya.
22:28Eh, para n para tres nodos sí hay, que
22:32sería este,
22:38¿ya? Y este hay uno solo.
22:41Y después el siguiente tendría que tener
22:43cinco.
22:45Cuatro no hay. Ya. Y ese sería
22:49este, por ejemplo.
22:54Ya. Ese tiene cinco. Eh, y este otro.
23:06Ya. Y de estos hay dos y así
23:09sucesivamente.
23:11Y como les decía, por esta vía eh
23:16llegamos a tener una ecuación, si
23:17hacemos todo la el análisis, ya eso se
23:20los puedo dejar como ejercicio. Si si
23:23repetimos el mismo análisis, pero ahora
23:24estamos contando tanto hojas como nodos,
23:27como si fueran eh lo mismo, ¿ya? Eh, yo
23:31llego a una ecuación que dice que a de z
23:37+ z a z²
23:43y por lo tanto, o sea, eso sería z * 1 +
23:49de z²
23:53y por lo tanto
23:56a de z yo lo puedo escribir como
23:59z por de a de z
24:07igual a 1 + u².
24:10Esa sería mi función phi 1 + u².
24:15Ya. Y ahora yo puedo aplicar el teorema
24:18de inversión de la grancha.
24:28eh
24:30que dice que a su n
24:33va a ser igual a 1 parido por n por u a
24:37la n - 1
24:41eh
24:43de
24:45f a la n, ¿cierto?
24:49Y esto sería
24:511/ido por n por el coeficiente que
24:54multiplica a u a la n - 1
24:57dentro de 1 + u²
25:02a la n. Ah, porque de u es 1 + u².
25:07Y esto yo lo puedo expandir por el termo
25:08del binomio. Entonces, esto sería el
25:10coeficiente que multiplica a u a la n -
25:131
25:15dentro de la sumatoria para k mayor o
25:18igual que 0 de n sobre k
25:28de n sobre k por u a la 2k.
25:33Ya, el teorema del binomio
25:36decía que eh 1 + x a la nandía como
25:40sumatoria de n sobre k por x a la k,
25:42pero en este caso x es uado, por eso es
25:45u a la 2K.
25:47Y y ahora eh
25:56ahora eh
25:59necesito
26:05que K
26:10eh perdón que 2k
26:14sea igual a n - uno,
26:18¿cierto? Porque yo quiero ver dentro de
26:21esta serie que tengo aquí
26:25qué coeficiente está multiplicando a u a
26:29la n - 1. Entonces, tengo que ver cuando
26:322k vale n - 1, tengo que ver cuál es el
26:34coeficiente que lo multiplica. ¿Okay?
26:38Eh, y esto y esto cuándo se cumple esto
26:43si solo
26:45eh nón
26:49si k
26:52es
26:55n - 1 medio, ¿no es cierto? Claro, cosa
26:58despejarlo,
27:00pero esto implica que n debe ser
27:06impar. ¿cierto?
27:15Porque el n - 1 tiene que ser par, K
27:17tiene que ser entero, ¿ya?
27:20Eh,
27:22entonces eh
27:26c porque recorre solo los entero eh si
27:29vale n -1 medios, entonces n-1 tiene que
27:32ser par, por lo tanto n debe ser impar,
27:38¿ya?
27:39Y en ese caso
27:45a su n va a ser igual a 1/ido por n.
27:50De acuerdo a lo que dice el teorema de
27:52inversión de la gran, me dice que eh
27:58va a ser 1 par por n por el coeficiente
28:00que multiplica a n - 1
28:03dentro de esa expansión. Y ese
28:05coeficiente que
28:08eh multiplica a n - 1 es n sobre k para
28:14k = n - 1/2. Ah, entonces va a ser
28:19n sobre
28:22n - 1/.
28:26Esa es la solución.
28:28Para n
28:31impar
28:34y
28:37para n par.
28:40Esa sería la solución.
28:42Ya.
28:44Eh,
28:46ahora eso se parece un poco a la fórmula
28:48que encontramos antes, pero no es lo
28:50mismo, ¿no es cierto? ¿Y por qué? Porque
28:51aquí yo estoy contando todos los nodos.
28:54Entonces, eh tratemos de recuperar la
28:56fórmula anterior. Ah, en esta fórmula,
29:06n
29:08es el número total
29:11de nodos,
29:15contando
29:18los nodos internos y las hojas. Okay.
29:27A lo mejor yo no debería usar la letra N
29:29ahí porque así que ya es demasiado
29:31tarde. Eh, entonces pongámosle otro
29:34nombre. Si llamamos
29:39I al número de nodos internos, que era
29:44lo que antes llamábamos n,
29:46pongámosle i por interno, ¿ya? Que son
29:49estos.
29:52Sabemos que
29:55que el número de hojas
30:01siempre
30:03siempre
30:05es igual
30:08a I + 1.
30:11Todo árbol con ínodos internos tiene I+
30:14hojas. Ustedes
30:16tienen que haber pasado por 63001 en
30:18donde demostramos eso una y otra vez de
30:20distintas maneras. Eh eh siempre hay una
30:24hoja más que el número de nodos
30:25internos. Eh por lo tanto,
30:30el nmula
30:33es el número de nodos internos, que es i
30:38más el número de hojas que es i + 1. Por
30:40lo tanto, es 2i + 1.
30:44¿Okay?
30:46Eh,
30:52y y eso implica que el número
30:56de árboles binarios
31:04con i nodos internos.
31:17es
31:19eh
31:211
31:23parido por n, ¿no es cierto? En la
31:25fórmula de arriba. Bueno, n es 2 + 1,
31:27así que va a ser 1/ido por 2i + 1
31:31por n, que es 2i + 1,
31:36sobre e n - 1/2,
31:42pero n es 2i + 1, por lo tanto al
31:44restarle 1 queda 2i y al dividir por 2
31:46queda i sobre i.
31:49Eso ya se parece más a la fórmula de de
31:52catalán, ¿ya? Pero no es exactamente,
31:56pero no falta mucho para llegar ahí. Ah,
32:00eh, esta fórmula la podemos a ver si
32:04expandamos el coeficiente
32:08binomial. Bueno, a ver, pongamos aquí,
32:10pongamos el 2i + 1 aquí abajo,
32:15¿ya? Y el coeficiente binomial de arriba
32:18lo expandimos, sería 2i + 1,
32:222i
32:242i - 1, ¿no es cierto? Así.
32:28Hasta llegar
32:29a 2i + 1 - i que a i + 1 + 1, o sea, i +
32:342.
32:36Hasta ahí llega.
32:39Y abajo yo tengo el i factorial, o sea,
32:411 * 2 hasta por i. Okay.
32:45Y aquí eh
32:49voy a
32:54Bueno, primero cancelo eso. Ya. Listo. Y
32:57acá voy a agregar un i + 1
33:04y acá también un i + 1.
33:10Okay.
33:14Esto que el lo que queda arriba, 2i 2i -
33:181 hasta i+ 1
33:21eh es e
33:24es 2i eh
33:28a la i descendente y abajo tengo un i
33:30factorial, o sea, todo esto de aquí
33:34es un 2i sobre i
33:39lo que sobra abajo, lo que no quedó
33:41incluido es un I+ 1. Así es que
33:45así es que
33:49queda eh
33:531/o por i + 1
33:58eh 2 y sobre i
34:06que es
34:08catalán,
34:10¿no es cierto?
34:13con i en lugar de n. Ah, pero bueno, por
34:17este tema de la anotación, eh, ese es el
34:21es exactamente la fórmula que estabas
34:22buscando, ¿no es cierto? Donde ahí es el
34:24número de nodos internos, lo que antes
34:25llamábamos en en en el otro análisis.
34:27Así que por esta vía llegamos al mismo
34:29resultado, por supuesto, como debía ser,
34:32pero en un camino que que puede ser un
34:35poquito más directo porque no hicimos no
34:37tuvimos que expandir en serie la raíz
34:39cuadrada y eso.
34:42y que nos sirve como un poco
34:44precalentamiento porque más adelante
34:45vamos a ver
34:47un más adelante vamos a analizar el
34:49número de de árboles rotulados generales
34:52que también se resuelve por la misma por
34:55el mismo método este de usar el teorema
34:57de inversión de la granche. ¿Ya?
35:00Bien, y ahora y ahora sí vamos a llegar
35:03a la lo que yo quería realmente ver en
35:04esta clase. Esto era continuación del
35:06anterior, que son los llamados métodos
35:09de enumeración simbólica, que es algo
35:13métodos de enumeración simbólica,
35:22que es algo que fue desarrollado en su
35:23momento esencialmente por la por la
35:26escuela francesa,
35:30eh,
35:32principalmente por Philip Flayo Olé, si
35:35ustedes circulan por el pasillo del
35:37tercer piso de la la poniente del DC,
35:39hay una sala que se llama sala Flayolé,
35:42que es en honor a a Philip.
35:45Eh, Philip, lamentablemente falleció
35:47hace ya algunos años y nos dejó un un un
35:54una cantidad impresionante de trabajo eh
35:57que ustedes pueden eh apreciarle un poco
36:01si leen el libro, como les dije, de
36:04Analytic Combinatorics, que es es Fly
36:08Swick, pero realmente el grueso de esa
36:11obra es es de Philip Flolé.
36:14Entonces, les quiero contar cuál fue
36:16esta idea que en su momento fue bastante
36:20bastante revolucionaria dentro del área.
36:22Ah, porque lo que yo les he mostrado
36:24hasta ahora de escribir ecuaciones de
36:27recurrencia y luego resolverlas eh menú
36:29usando funciones generatrices, es lo que
36:32viene de esencialmente de KUS, que y de
36:37sus libros de The Art of Computer
36:38Programming.
36:40Donal Cuz eh comenzó a analizar
36:43algoritmos de esa manera eh a mediados
36:46de
36:47de los 60 por ahí o principio de los 60,
36:52siglo pasado, por supuesto. Y
36:55pero eh posteriormente apareció esto y
36:59muchos de los problemas que habían sido
37:00antes resueltos de manera muy laboriosa
37:03eh empezado a resolverse muy muy
37:05directamente gracias a estas ideas.
37:07Entonces, les voy a contar de qué se
37:08trata. Eh, por supuesto el mismo con
37:13mucho entusiasmo hace uso de estos
37:15métodos también. Ahora, eh,
37:19¿cómo funciona esto? Eh, pensemos el
37:21problema de numerar árboles binarios.
37:24Eh, lo que sucede es [risas] que existe
37:26un universo ahí de de árboles binarios
37:29posibles, ¿no es cierto? Entonces, por
37:30ejemplo, tenemos ese, tenemos ese,
37:34tenemos
37:37ese por ejemplo, etcétera, infinitos,
37:39por supuesto. Ya,
37:42pongámosle un nombre. a cursiva. Ah, eso
37:44trata de hacer una cursiva. Eh, la idea
37:47es que ese es el ese es el conjunto de
37:50todos los árboles binarios posibles.
37:51Incluye también el árbol el árbol eh
37:55vacío. Es que tiene cero nodo. Cuesta un
37:57poco verlo ahí, pero está ah eh si
37:59ustedes quieren verlo ahí vale más la
38:01pena dibujarlo, dibujar explícitamente
38:03la hoja, ¿no es cierto? Ya. Entonces,
38:06¿qué es lo que hacemos nosotros a partir
38:08de aquí? dijimos, yo quiero saber dentro
38:12de ese conjunto cuántos árboles hay que
38:15tengan tamaño n, que tengan exactamente
38:17n nod no nodos. Y para eso escribimos
38:20una ecuación ah eh sumatoria, qué sé yo,
38:25que tiene una convolución y a eso le
38:28aplicamos la función generatriz en Z.
38:32Y eso nos llevó a una ecuación de la
38:35forma a Z igual algo, ¿ya?
38:39que pudimos resolver y encontrar la
38:41solución del problema.
38:45Eso es el enfoque, digamos, clásico.
38:49La la novedad a partir de lo que les
38:52contaba trabajo principalmente de Flolé
38:55es que él nos da una manera de partir
38:58del conjunto a cursiva
39:01y llegar directamente
39:07por inspección a escribir la la ecuación
39:11respectiva sin pasar por la ecuación de
39:14recurrencia.
39:16Ya,
39:18esto de alguna manera
39:21eh tiene un análogo eh en la forma como
39:26los eléctricos usan la transformada de
39:29la PL para analizar circuito. ¿Hay algún
39:32eléctrico entre los aquí presentes?
39:35No. E,
39:38¿qué es lo que se hace para analizar un
39:39circuito?
39:41Con las leyes de Kirchof se escribe un
39:43conjunto de ecuaciones diferenciales,
39:46ya en que bueno, por supuesto, las
39:49resistencias dan ecuaciones en que hay
39:51un factor constante no más, ¿ya? Eh,
39:54pero las
39:57inductancias y los condensadores aportan
40:01derivadas y aportan integrales al
40:03escribir esta ecuación. Ah, si hay
40:05integrales, uno deriva y obtiene una
40:07ecuación puramente diferencial.
40:09Eh, y esa ecuación hay que hay que
40:11resolverla y para eso uno mete eh
40:15transformar a la plaz y la transformar
40:18de la plaz lo que hace es que las
40:20derivadas me las transforma en
40:23expresiones algebraicas, o sea, no son
40:25diferenciales, son algebraicas.
40:26Entonces, yo a partir de este conjunto
40:29de ecuaciones diferenciales obtengo un
40:31conjunto de ecuaciones algebraicas que
40:33son mucho más fáciles de de resolver. Ya
40:35la resuelvo. Ahí la variable que usan
40:37normalmente es la variable S. Entonces
40:39dicen que pasan del dominio del tiempo T
40:41al dominio de las S, que es el dominio
40:43de la transformada, la resuelven y luego
40:45saben cómo invertir y obtener de vuelta
40:47las ecuaciones en el dominio del tiempo.
40:49Eh, pero después de hacer esto unas
40:51cuantas veces, uno ya se acostumbra y
40:53por inspección sabe cuál es la ecuación
40:56algebraica que tiene que resultar y
40:58entonces ya no escribe más las
40:59ecuaciones diferenciales. Observa el
41:02circuito y escribe ecuaciones
41:05ecuaciones diferenciales, ¿ya? Perdón.
41:08ecuaciones algebraicas en ese y se salta
41:11el paso intermedio. Algo parecido pasa
41:13aquí. Vamos a observar la estructura de
41:17los objetos que están en la clase A y a
41:19partir de esa estructura vamos a saber
41:20qué ecuación escribir ahí al lado
41:23derecho. ¿Ya? Entonces, esa esa es la
41:26idea, eh es la intuición y es, como
41:29digo, una idea super potente.
41:32Y y acompáñenme ahora a a a unas cuantas
41:36definiciones que espero que no sea muy
41:38latoso, pero son necesarias. Ya vamos a
41:41definir
41:43lo que es una clase combinatoria.
41:47Esa cursiva es una clase combinatoria.
41:57Ya es un conjunto finito o enumerable.
42:03Puede
42:06ser finito, por supuesto, pero también
42:08puede ser infinito. En este caso tiene
42:10que ser el numerable
42:14[suspiro][grito ahogado]
42:16sobre el cual
42:22se puede definir
42:26una función
42:33tamaño
42:37en inglés size.
42:42Y esa la escribimos como el tamaño de
42:44alfa, así como valor absoluto, ¿ya? Y
42:47eso se define para todo alfa en la clase
42:50combinatoria A.
42:52Eh, y esa función tamaño tiene que tener
42:55las siguientes propiedades.
42:58Tal que
43:00uno el tamaño de alfa es mayor o igual
43:04que er0 para todos los objetos en la
43:06clase.
43:07No hay objeto de tamaño negativo.
43:11y dos,
43:12eh, si para todo n mayor o igual que 0
43:19definimos
43:23a cursiva sub n,
43:25ya lo definimos como el conjunto de los
43:28objetos de la clase combinatoria
43:32tal que el tamaño del objeto es igual a
43:34n, ¿ya? Entonces separamos los objetos
43:37por tamaño.
43:40Entonces
43:44a su n es finito.
43:50¿Okay?
43:51Eh,
43:55el esto quiere decir entonces que la
43:58clase combinatoria puede ser infinita,
44:01pero el número de objetos dentro de esa
44:02clase que tienen un cierto tamaño tiene
44:04que ser finito.
44:06Si tomamos a los árboles binarios como
44:08ejemplo en la clase combinatoria a de
44:11los árboles binarios hay infinitos
44:13árboles binarios, pero si yo restrinjo a
44:16que son árboles que tienen que tener
44:17tamaño cinco, por ejemplo, ya, eh donde
44:22el tamaño es el número de nodos
44:23internos, eh ese
44:27objet
44:28eh eh objetos de ese tamaño hay solo una
44:31cantidad finita, ¿ya? Y en caso de los
44:34árboles ciertamente se cumplan.
44:37Y como notación
44:47vamos a llamar a sub n
44:50al cardinal
44:52de
44:54a cursiva subn, o sea, a sub n es el
44:57cardinal del conjunto de objetos de
44:59tamaño n. En otras palabras, ¿cuántos
45:02objetos hay de tamaño n?
45:04Eso coincide con el uso que nosotros le
45:05hemos dado, ¿no es cierto? Nosotros
45:06llamamos a su n al número de árboles de
45:09tamaño n. Exactamente. El cardinal del
45:12conjunto a su N, donde azu n son los
45:14árboles restringidos de aquellos que
45:15tienen tamaño N.
45:18Okay. Y ahora ya vamos
45:24la secuencia de enumeración.
45:35de la clase
45:39a es la sucesión
45:44a su n para todo n mayor o igual que no
45:51y ahí estamos enganchando con lo que
45:52habíamos visto antes. Entonces,
45:56ya, ¿qué relación tiene esto con las
45:57funciones generatrices?
46:16Bueno, si yo tengo que su n es el
46:19cardinal
46:21de a cursiva su n,
46:26¿ya? O sea, el cardinal
46:30del conjunto de todos los alfa en A,
46:34tal que el tamaño de alfa n.
46:41Yo puedo definir
46:48a de Z
46:50como la generatriz en Z de a su n. ¿Ya?
46:54Y si necesito
46:56enumerar otras clases BC, etcétera,
47:00puedo decir BZ es la generatriz en Z de
47:03B sub N, C de Z la generatriz en Z de C
47:08sub N y las que necesite. ¿Okay?
47:12Entonces, eh estas funciones
47:14generatrices van a enumerar
47:17a los objetos, a la cantidad de objetos
47:19que hay de cada tamaño dentro de una
47:22clase combinatoria.
47:24Eh,
47:26entonces
47:34si,
47:38perdón,
47:41entonces tengo propiedades como la
47:42siguiente. Si la clase A
47:46es la unión
47:49disjunta de las clases B y C, ¿ya?
47:53Eh, este símbolo de suma
47:58aplicado a clases combinatoriales,
48:02eh vamos a usar el símbolo de suma para
48:04indicar una unión disjunta.
48:10Ya. Eh, ¿por qué son importantes las
48:13uniones disjuntas? porque me permiten
48:20concluir que me permiten contar los
48:22objetos simplemente sumando los que hay
48:24en B con los que hay en C. Como es
48:26disjunta, no hay intersección. Entonces,
48:29yo sé que si los cuento por separado y
48:31luego sumo, estoy contando exactamente
48:33los objetos que hay. Si hubiera
48:34intersección, tendría que sumar ambos y
48:36después restar la intersección, el
48:38cardinal de la intersección, pero como
48:40es unión disjunta, no tengo ese
48:41problema.
48:43Eh, y esto implica que a de z
48:51+ c.
48:53O sea, si yo tengo eh una clase que es
48:56la unión de dos clases, su función
48:57generatriz es la suma de las funciones
48:59generatrices. Es decir, yo tengo eh una
49:03clase que es el producto cartesiano de
49:07dos clases, ¿ya?
49:10Entonces, su función generatriz
49:13es el producto de las respectivas
49:15funciones generatrices.
49:19Y vamos a ver por qué esto es cierto.
49:23Vamos a hacer aquí, vamos a hacer un
49:25pequeño paréntesis
49:30hasta aquí. Adelante, eh,
49:34porque tengo la tengo las siguientes
49:36propiedades.
49:42Eh, yo sé el cardinal de BA C.
49:50Eh, si hago la unión disjunta, el
49:53cardinal de la unión disjunta es la suma
49:54de los cardinales, ¿no es cierto?
50:04Y
50:06y el cardinal de B cruce.
50:11Eh, si yo tengo una clase B y una clase
50:15C y yo formo B cruc, lo que estoy
50:18formando es objetos compuestos que
50:21consisten de un objeto tomado de B con
50:24un objeto tamaño de C eh, a continuación
50:27despegado como en un par ordenado, ¿no
50:29es cierto?
50:30y
50:32la enumeración me dice que bueno, por
50:36cada objeto de la clase B, yo lo puedo
50:39hacer un par ordenado con cada objeto de
50:41la clase C. Por lo tanto, el número
50:43total de objetos resultante es el
50:44producto.
50:45Entonces el producto aquí tengo
50:55ya eh
51:01y si definimos
51:08una clase
51:10neutra,
51:14llamémosla
51:17una e cursiva,
51:19que es la clase
51:25que contiene
51:29un
51:30único
51:32objeto
51:35de tamaño cero.
51:40¿Ya?
51:41Entonces,
51:45si yo tengo un objeto de tamaño cero,
51:48esta clase excursiva,
51:51yo lo puedo, ese objeto de tamaño cero,
51:53yo lo puedo llamarsilon
51:57y también
51:59eventualmente lo puedo designar por el
52:01número uno. Ah, ambas cosas tiene
52:04sentido.
52:05Esto eh
52:07esto eh
52:11de alguna manera eh tiene que ver
52:14también con la teoría de lenguajes
52:16formales. Eh eh yo puedo ver estos
52:19objetos como strings.
52:21Entonces un objeto del tamaño cero es un
52:24string de largo cero que en teoría de
52:27lenguajes formales se suele designar
52:29porsilon.
52:30Y tiene característica que si yo tengo
52:32un objeto, un string, y le concateno a
52:34la derecha eh queda el mismo objeto
52:38inicial, ¿cierto? Y si lo concateno a la
52:41izquierda con épsilon, también pasa lo
52:43mismo. ¿Ya? Entonces el es un neutro, es
52:47un elemento neutro para la operación de
52:49concatenación. Hm. Y esa operación de
52:53concatenación le la escribimos con una
52:56anotación multiplicativa, ¿ya? Eh, y el
53:01neutro multiplicativo típicamente se
53:03designa por el número uno. Entonces, por
53:06eso también a veces objeto se designa
53:08por uno, sentido que al multiplicarse
53:10por él, en sentido de concatenarse,
53:13el eh eso no cambia el objeto inicial,
53:16ya es un elemento neutro para esta
53:18operación. Entonces, eh
53:23eh entonces está la propiedad que si yo
53:25tengo una clase A y le hago producto
53:29cruz con esta clase neutra, el resultado
53:32es isomorfo con que si yo
53:40eh tomara la clase neutra y le hiciera
53:44cruz con a y todo eso es isomorfo
53:49al a mismo. Ah, o sea, hacer producto
53:52cruz con con la clase neutra e no cambia
53:56al objeto y a partir
54:03de eh de la definición de producto de
54:06clases
54:11producto cartesiano, ¿no es cierto?
54:19[suspiro]
54:21Podemos definir potencias.
54:32Yo puedo decir que una clase que la
54:35potencia de una clase B a la N
54:39va a ser la clase neutra. Si n es ig a 0
54:45y va a ser b a la n - 1 cruz b.
54:50Eso no parece una b aquí
54:56100 es mayor que 0.
54:59Ya. Y si eso yo lo expando, esto va a
55:02ser B cruz B cru b
55:10n veces. ¿cierto? Eso eso es una clase b
55:14elevado a la n
55:17= 0 es la clase neutra.
55:20Y a partir de aquí
55:29podemos definir
55:36una secuencia.
55:43B estrella
55:47que es
55:50la clase neutra
55:52más b o b a la 1 más b cuadrado más p
55:59cubo y así a infinito.
56:03Esa es la clase de cero o más
56:06repeticiones de objetos de la clase B.
56:09Ya. Ahora, hay que tener cuidado al
56:11definir B estrella porque
56:15eh
56:17estas uniones que están eh representadas
56:19por estos signos más tienen que ser
56:20disjuntas,
56:22¿ya? Eh, y por lo tanto eh no puede el
56:27objeto B, la clase B, digo, no puede
56:30contener el objeto eh de tamaño cero, no
56:35puede contener épsilon, ¿ya? Porque si
56:37contuviera éilon, estaría éilon repetido
56:40en todos en todos los términos, ya no
56:42sería un disjunta.
56:44Entonces,
56:46eh
56:47hay una condición aquí suponiendo
56:55queilon
56:59no pertenece a la clase B,
57:03¿ya? Y aquí tenemos el cierre
57:05paréntesis.
57:14Entonces, con eso tengo una tercera
57:16propiedad que dice que si la clase A es
57:19igual a B estrella,
57:22entonces
57:26A de Z
57:28es 1
57:32partido por 1 men dez.
57:39suponiendo
57:45queilon
57:48no pertenece a B.
57:50Ya, ninguna de estas cosas obvia, eh,
57:53las vamos a demostrar las propiedades 1,
57:56dos y tres.
58:00E,
58:02okay. Entonces, veamos cómo serían estas
58:05demostraciones.
58:12No son no son para nada complicadas,
58:18¿eh?
58:21para propiedad uno,
58:26si a la clase A es la unión disjunta de
58:29B y C,
58:34entonces
58:36como es una unión disjunta, el número de
58:38objetos de tamaño N en la clase A
58:42consiste de todos aquellos objetos de
58:44tamaño N en la clase B más todos
58:46aquellos objetos de tamaño N en la clase
58:48CC, ¿cierto? O sea, si hay un objeto de
58:52tamaño Na, tiene que ver tiene que
58:54provenir de B o de C y no puede provenir
58:58de ambas porque porque son disjuntas,
59:00¿ya? Eh, y eso de inmediato implica que
59:04A de Z
59:07es B de Z
59:10+ CZ. Así que esa es superfácil, ¿no es
59:13cierto? Ah, pero de inmediato vayan
59:17viendo ustedes lo que esto implica. Lo
59:20que esto implica es que si yo tengo eh
59:23una clase que es formada por la unión
59:25disjunta de dos clases, entonces en el
59:28dominio de las funciones generatrices,
59:30la función generatriz A que numera la
59:33clase A cursiva
59:35es igual a la suma de las funciones
59:36generatrices de P y C, de las clases B y
59:41C. O sea, una suma en el dominio de las
59:44clases combinatorias se traduce en una
59:47suma en el dominio de las funciones
59:48generatrices. Ya. Entonces, por
59:52inspección de de la estructura de de la
59:55clase A, yo puedo ir empezar a escribir
59:57las ecuaciones respectivas en el dominio
59:59de la función generatrices.
1:00:02Eh, la segunda propiedad
1:00:05dice
1:00:07que el
1:00:10si la clase A es el producto cartesiano,
1:00:13aquí está, si la clase A es el producto
1:00:16cartesiano de B con C, entonces eh las
1:00:20funciones geratrices respectivas se
1:00:22multiplican.
1:00:23O sea, un producto cartesiano en el
1:00:26dominio de las clases combinatorias se
1:00:30traduce en un producto eh en el dominio
1:00:33de las funciones generatrices.
1:00:40Supong considéramos un cierto alfa en en
1:00:43A. Ya, como
1:00:47A es la el producto cartesiano de B con
1:00:52C, entonces A tiene que tener esta
1:00:55forma. Alfa, perdón, tiene que tener
1:00:56esta forma. Alfa tiene que ser par
1:00:58ordenado.
1:00:59Beta, gama, digamos, con beta en B.
1:01:06y gama en C.
1:01:09Okay.
1:01:11Entonces,
1:01:13mi AD Z
1:01:15por definición es la sumatoria de a su n
1:01:18por z a la n para n mayor o igual que 0,
1:01:21¿ya? Donde A sub n es el número de
1:01:25objetos
1:01:27de tamaño n que hay en la clase a
1:01:29cursiva, ¿cierto?
1:01:31Pero como cada objeto que está en la
1:01:34clase a cursiva es la concatenación de
1:01:38un objeto tomado de B y otro objeto
1:01:40tomado de C, el número de objetos de
1:01:44tamaño N yo lo puedo
1:01:50escribir.
1:01:54Este a sub n eh
1:01:58tiene que ser cada objeto
1:02:01de la clase,
1:02:03cada objeto que está enumerado dentro de
1:02:05ese número a su nene que ser la
1:02:08concatenación de un objeto de tamaño,
1:02:14digamos, I dentro de B y un objeto de
1:02:19tamaño J dentro de C, tal que y + J sea
1:02:23N.
1:02:24Porque la suma porque el tamaño final
1:02:26tiene que ser n. Ah, pero los tamaños se
1:02:28suman. Si yo concateno un objeto de
1:02:30tamaño i con uno de tamaño j, el objeto
1:02:33resultante tiene tamaño i + j, pero ese
1:02:35i + j tiene que ser igual a n. Y eso lo
1:02:38tengo que hacer de todas las maneras
1:02:39posibles. Entonces, va a ser la
1:02:40sumatoria
1:02:42de sobre todo i y j mayor o igual que 0
1:02:46de tal que i + j es ig a n.
1:02:50Ya.
1:02:54¿De qué? De B sub i
1:02:59por c sub J.
1:03:02Porque por cada objeto de tamaño I, si
1:03:06yo tengo una cierta cantidad de objetos
1:03:07de tamaño I y una cierta cantidad de
1:03:11dentro de B y una cierta cantidad de
1:03:13objetos de tamaño J dentro de C por cada
1:03:18uno de de la clase B, yo puedo combinar
1:03:21con cada otro de la clase C. Entonces,
1:03:23estoy con todas las combinaciones
1:03:24posibles. Por lo tanto, el resultado es
1:03:26del producto PI por C sub J. Ya, siempre
1:03:30que más j sea igual a n. Así que tengo
1:03:32eso. Y ahora esto yo lo puedo escribir
1:03:37como la sumatoria para n mayor o igual
1:03:40que 0 de una
1:03:44sumatoria
1:03:46sobre todo i j mayor o igual que 0 tal
1:03:49que i + j = n
1:03:53de b sub i
1:03:55y el z a la n como n es ig a i + j puedo
1:03:58escribir p su i por z a la i por c sub
1:04:02j* z a la
1:04:04Ya.
1:04:06Y ahora esto
1:04:09lo vamos lo lo hemos hecho antes, pero
1:04:11lo voy a repetir aquí para que
1:04:14asegurarme que que quede bien entendido
1:04:17y pues lo vamos a seguir haciendo
1:04:18después y y después ya va a ser como
1:04:21automático.
1:04:23La cosa es la siguiente. ¿Qué pasa con
1:04:26esta sumatoria?
1:04:30¿Qué significa esto? Ya. Eh, esto es una
1:04:34triple sumatoria en realidad,
1:04:37eh, porque es sumatoria sobre N, sobre i
1:04:39y sobre J. Ya. Bueno, pero en realidad
1:04:44eh mire, mire lo que significa.
1:04:46Supongamos que yo tengo aquí
1:04:49I y aquí tengo J. Ya. Y aquí tengo
1:04:52entonces
1:04:590 1 2 3 0 1 2 3 etcétera.
1:05:06¿Ya? Entonces para n = 0, ¿cuáles son
1:05:10los i j mayor o igual que suman cer? Hay
1:05:13uno solo que es este.
1:05:16Ya. Después para n = 1, ¿cuáles son los
1:05:20i y j mayor o igual que 0 que suman 1?
1:05:24Bueno, hay dos. Es el i = 0 j = 1, que
1:05:28es ese,
1:05:30y el i = 1 j = 0, que es ese. Entonces,
1:05:34juntemos estos dos. Esos dos van. Esos
1:05:37este corresponde a n = 0. Este otro
1:05:40corresponde a n = 1. ¿Qué pasa n = 2?
1:05:44Bueno, yo tengo el 02,
1:05:47tengo el 1 y tengo el 2. Eso corresponde
1:05:52a n = 2. Ya. Y
1:05:55la demostración de la convolución, ¿o
1:05:56no?
1:05:58Eh, exacto. Es una convolución
1:05:59finalmente. Sí.
1:06:02Entonces vamos y si vamos avanzando en
1:06:05ese en esa dirección, en el fondo vamos
1:06:07a terminar cubriendo todo el cuadrante.
1:06:10Ya vamos lo vamos cubriendo diagonal por
1:06:12diagonal,
1:06:14pero vamos a cubrir todo el cuadrante
1:06:16anyway. Ah, da lo mismo en qué orden lo
1:06:18hagamos. Aquí lo estamos haciendo
1:06:19diagonal por diagonal, pero podríamos
1:06:21ido en cualquier otro orden y mientras
1:06:23terminemos cubriendo todo el cuadrante
1:06:25está bien. Por lo tanto, eh esta triple
1:06:29sumatoria la podemos simplificar y decir
1:06:32que es simplemente la sumatoria sobre
1:06:35todo y j mayor o igual que 0
1:06:39debe sub i * z a la i c sub j * z a la
1:06:43j. ¿Ya? Y esto, esta doble sumatoria es
1:06:48doble a pesar de que no se ve como doble
1:06:50porque tiene dos subíndices
1:06:51independientes, ¿no es cierto? Es
1:06:53separable en dos sumatorias. Una es la
1:06:56sumatoria sobre todo y mayor o igual que
1:06:580 de s no es b a la i. Y hay un error de
1:07:02notación
1:07:05es B sub i ahí igual que el C sub*
1:07:10z a la I multiplicado por sumatoria
1:07:15sobre todo j mayor o igual que 0 de C
1:07:18sub J* Z a la J.
1:07:21Pero esto es B de Z, el cual se
1:07:24multiplica por esto otro de acá que es
1:07:26CD Z.
1:07:28Y eso es exactamente lo que queríamos
1:07:30demostrar, ¿no es cierto? Que A de Z, ya
1:07:34eso implica que A de Z es bz
1:07:38por C de Z QD. Ya, eso era lo que
1:07:42queríamos demostrar.
1:07:46[carraspeo]
1:07:47Y
1:07:51en tercer lugar,
1:07:54la propiedad de astro.
1:07:57Si A es B estrella, entonces A de Z es
1:08:001/Z.
1:08:06Entonces, lo que hasta ahora
1:08:07recapitulando, lo que hemos visto es que
1:08:10las uniones disjuntas, o sea, las sumas
1:08:13de clases combinatorias se traducen en
1:08:15sumas de funciones generatriz, que los
1:08:17productos cartesianos de funciones de de
1:08:20clases combinatorias se traducen por
1:08:22productos de funciones generatrices. Y
1:08:24aquí vamos a ver que la estrella,
1:08:27el asterisco aplicado una clase
1:08:29combinatoria, o sea, la clase que tiene
1:08:31consta de cero o más repeticiones de
1:08:33objetos de de esa clase eh se traduce
1:08:38por 1/z,
1:08:40donde bz es la función generatriz de la
1:08:42clase original. ¿no? Eh,
1:08:46la clase A dijimos que era
1:08:53la clase neutra
1:08:56más p
1:08:59más b²ad, etcétera. Ya. De hecho, este
1:09:03lo puedo escribir como B a la cer
1:09:10entre paréntesis.
1:09:16¿Cuál es la se parece? ¿Cuál es la cuál
1:09:19es la
1:09:21Vamos, vamos directo ya? ¿Qué es A de Z?
1:09:28Como a de Z, recuerden que queilon
1:09:34no pertenece a B, ¿ya? Entonces, esto es
1:09:37una unión disjunta, por lo tanto se
1:09:40traduce por una suma.
1:09:42una suma de qué, con qué y con qué. El
1:09:44primer sumando es la función generatriz
1:09:47de la clase neutra. ¿Cuál es la función
1:09:49generatriz de la clase neutra? Esa
1:09:52cáncer neutra contiene un solo objeto de
1:09:54tamaño cero. Por lo tanto, el número, yo
1:09:58tengo que hacer la sumatoria del número
1:09:59de objetos de cada tamaño multiplicado
1:10:01por z elevado al tamaño. Eh, pero de los
1:10:05tamaños posibles hay solo uno que
1:10:07existe, que es el tamaño uno, perdón,
1:10:09tamaño cero. Y hay un objeto de ese de
1:10:12ese tamaño, o sea, va ser 1 por Z a la
1:10:150. Z0 es 1, o sea, va a ser uno. Ya. La
1:10:20la
1:10:22función generatriz de la clase neutra es
1:10:24uno. Y si y si ese lo escribimos más
1:10:28bien como uno, que es la otra anotación
1:10:31que también se usa, con mayor razón es
1:10:34más
1:10:36evidente o más fácil recordar por último
1:10:39de que la clase uno tiene con función
1:10:42generatriz el uno.
1:10:45y B tiene como función gen de Z y B² que
1:10:50es Bru B por lo que acabamos de mostrar
1:10:53antes tiene B cuad
1:10:57y así sucesivamente
1:10:59y esa sumatoria
1:11:02está 1/o por 1 men bz
1:11:06que es lo que estábamos tratando de
1:11:08mostrar ya así es que con esto tenemos
1:11:13un pequeño
1:11:16repertorio de eh
1:11:20reglas de composición en el fondo que me
1:11:24dicen que si si mi objeto eh pertenece a
1:11:29la clase a una clase que está construida
1:11:32como suma de clases unión disjunta, eso
1:11:35va a generar suma en la función
1:11:37generatriz. Si si están concatenados,
1:11:40¿no es cierto? a través de producto
1:11:41cartesiano, entonces va a dar producto y
1:11:45si hay repetición de cero o más, eso va
1:11:48a dar uno parido por 1 menos, ¿ya? Y
1:11:51esas son el tipo de reglas que a mí me
1:11:53van a permitir por inspección observar
1:11:56la estructura de la clase original y a
1:11:58partir de ahí escribir directamente las
1:12:00funciones generatrices respectivas. Ya
1:12:04nos quedan unos minutos, así es que
1:12:05alcanzamos a ver un enfoque alternativo.
1:12:21Ya. E bueno,
1:12:25hemos definido
1:12:30e a dez
1:12:33como la sumatoria de a sub n por n para
1:12:36n may que
1:12:38sí.
1:12:39Eh, cuando uno tiene eso de que bueno,
1:12:43una geométrica le da 1 sobre 1 - bdz,
1:12:45eso no es cuando bd es menor que 1.
1:12:48Eh, esto es puramente formal. Ah, de
1:12:51hecho no tiene sentido decir que BDZ sea
1:12:53menor que uno porque BDZ es una es una
1:12:56serie formal. Ah, no es un número
1:12:59complejo o para decir que está dentro
1:13:01del radioconvergencia. Esto es una son
1:13:03identidades puramente formales,
1:13:06muy excepcionalmente de vez en cuando
1:13:08vamos a a darles una interpretación en
1:13:12los complejos, pero normalmente no es
1:13:14necesario. Nos basta quedarnos como una
1:13:17con esto como una manipulación de
1:13:18símbolos formales.
1:13:21Antes hemos visto que que el uno parido
1:13:24por 1 menos es la la única posible
1:13:29solución que cumple con la con la línea
1:13:32anterior.
1:13:34Y de hecho eh podemos incluso tomar como
1:13:39definición
1:13:41cómo defino yo 1 parido por 1 menz. Lo
1:13:44defino con esta como esta serie.
1:13:51Ya. Ahora hemos definido así la función
1:13:54generatriz donde como les decíamos donde
1:13:59a su n es el cardinal
1:14:02de a sub n
1:14:05eh y y a sub n
1:14:09es el conjun es el
1:14:12es el conjunto de todos los alfa en a
1:14:16tales que el tamaño de alfa es n, ¿no es
1:14:18cierto? Lo hemos definido de esa manera.
1:14:21Bueno, podemos tener una definición
1:14:23alternativa,
1:14:32que es que a de Z
1:14:35es la sumatoria para todo alfa en a
1:14:41de Z elevado al tamaño de alfa.
1:14:45Una definición
1:14:47mucho más simple
1:14:50es la suma para todo alfenada, ¿no? La
1:14:52suma ya no es para n mayor o igual que
1:14:53cer. La suma es sobre todos los objetos
1:14:55de la clase, ¿ya? y ya va son
1:14:59equivalente.
1:15:14Porque [carraspeo]
1:15:17porque este A de Z
1:15:22los eh yo estoy sumando sobre todo los
1:15:25objetos de A, ¿no es cierto? Pero yo
1:15:28podría agruparlos por tamaño. Entonces
1:15:31yo digo, voy a ir sumando por tamaño por
1:15:33tamaño para todo n mayor o igual que0 y
1:15:38agrupados por tamaño. Va a quedar así,
1:15:40va a quedar son todos los alfa en A
1:15:44tal que el tamaño de alfa es igual a n,
1:15:48¿no es cierto? Por z elevado al tamaño
1:15:50de alfa.
1:15:52Ahí están agrupados.
1:15:56Y ahora que están agrupados, esto lo
1:15:58puedo escribir como la sumatoria para
1:16:00todo n mayor o igual que 0
1:16:03de la sumatoria para todo alfa en A, tal
1:16:08que el tamaño de alfa es n de C elevado
1:16:10al tamaño de alfa, pero pero el tamaño
1:16:12de alfa es n por por construcción, ¿no?
1:16:18Por lo tanto,
1:16:20el z lo puedo sacar para fuera la
1:16:22sumatoria.
1:16:24sumatoria para n mayor o igual que 0
1:16:28de z la n por la sumatoria
1:16:32de 1 para todo alfa en a tal que el
1:16:36tamaño de alfa es n,
1:16:39¿cierto?
1:16:42Pero
1:16:45esto que está aquí,
1:16:50si yo sumo uno para cada objeto de A que
1:16:55tiene tamaño n, lo que me resulta es el
1:16:58número de objetos de A que tiene tamaño
1:17:00N, que es lo que yo llamo AU n, ¿no es
1:17:03cierto? Y por lo tanto,
1:17:07esto termina siendo igual a la
1:17:09sumatoria.
1:17:11de su n por z a la n.
1:17:16Ya, eso demuestra que
1:17:21esta
1:17:22esta definición
1:17:25de la función generativa asociada a a la
1:17:27clase A es equivalente a esta otra
1:17:30definición. Y esta de acá es eh a menudo
1:17:36eh más fácil de trabajar con ella. Ah,
1:17:39entonces para mostrar por qué eso puede
1:17:41pasar,
1:17:44eh, esto simplifica
1:17:52algunas demostraciones,
1:18:01por ejemplo,
1:18:06ya
1:18:08eh,
1:18:11por ejemplo, para demostrar que el
1:18:12tamaño se que si A es B + C, eso implica
1:18:18que A de Z es la suma.
1:18:24Ya. Eh,
1:18:27bueno,
1:18:29A de Z por definición
1:18:33es la suma, por la segunda definición
1:18:36sobre todo alfa en A,
1:18:38tal que de z elevado al tamaño de alfa,
1:18:41¿cierto?
1:18:43Pero entonces esto va a ser la suma para
1:18:46todo alfa. Eh, como a es b + c, alfa es
1:18:49b + c
1:18:51de z elevado al tamaño de alfa.
1:18:56Y como esa es una unión disjunta, yo lo
1:18:58puedo separar en dos sumatorias. La
1:19:00sumatoria sobre B de Z elevado al tamaño
1:19:03de alfa más la sumatoria sobre C.
1:19:10Es elevado al tamaño de alfa.
1:19:13Y eso no es otra cosa que BDZ.
1:19:16más CDZ.
1:19:19Ya.
1:19:21Y asimismo otras otras demostraciones
1:19:24también eh se simplifican bastante si
1:19:27las operamos con esta definición. Así
1:19:29que a menudo vamos a recurrir
1:19:33a esta definición alternativa
1:19:36más que esta otra,
1:19:40ya sin olvidarla porque en ocasiones nos
1:19:43convite más la otra también, pero tengo
1:19:45dos definiciones, puedo elegir la que me
1:19:47convenga más. Y con eso, a pesar que
1:19:50todavía nos quedan unos pocos minutos,
1:19:52creo que es momento preciso para
1:19:54concluir esta clase, porque en la clase
1:19:57que viene vamos a empezar a ver
1:19:59aplicaciones de
1:20:01de de este enfoque que les decía yo de
1:20:07que introdujo Philip Layolé para eh la
1:20:10enumeración de clases combinatorias,
1:20:15así que
1:20:17con eso concluimos la clase
1:20:20y eh nuevamente felicitaciones a los
1:20:25puntuales que que vinieron
1:20:26personalmente. Espero que los demás
1:20:28estén eh
1:20:32eh rigurosamente viendo los videos o
1:20:36leyendo los apontes para que no se vayan
1:20:38quedando atrás los que no pudieron venir
1:20:40hoy día, que
1:20:42se mantengan al tanto de lo que estamos
1:20:44viendo en clase
1:20:46y de esa manera les va a ir bien en el
1:20:48curso. Muy bien, hasta luego, entonces.
1:20:54Ciao