Full transcript
0:03Buenos días y bienvenidos a la clase.
0:06Ah,
0:09hoy día vamos a hacer un último ejemplo
0:12de aplicación de funciones generatrices
0:16antes de introducir eh otro tipo de
0:19función generatriz que también va a
0:20resultar muy útil. Ah, el ejercicio que
0:24vamos a ver aquí ya que ver todo lo que
0:27hemos visto hasta ahora, ¿no es cierto?
0:29de numerar árboles binarios, de las
0:31recubrimientos de dominóz, h
0:35de dar vuelto, etcétera. Ya. Eh, este va
0:40a ser el problema de contar
0:43triangulaciones.
0:57La idea es la siguiente. Supongamos que
1:00tenemos un cierto polígono
1:03convexo,
1:08por ejemplo, es. Entonces, la pregunta
1:10es,
1:12¿cómo lo podemos triangular? Ah,
1:14entonces eh
1:17por ejemplo,
1:18una posible triangulación es así,
1:23¿cierto? Así.
1:26Así. Esa sería una posible
1:28triangulación,
1:30eh, pero no es la única. Ah, si el mismo
1:33polígono
1:38ahí tratando de que se parezca ya,
1:41eh, lo dibujamos, lo podríamos
1:44triangular así, ¿ya? Y tal como esto,
1:48hay muchas otras. Entonces, la pregunta
1:50es, ¿cuántas son? Ya, de cuánta manera
1:52es distinta. Entonces, anotemos eso. Hm.
1:55Entonces, la pregunta es eh de cuántas
1:58maneras distintas
2:12se puede triangular.
2:29eh
2:30de n + 2 vértices. Vamos a poner ustedes
2:33van a ver por qué vamos a ponerlo así
2:38con n mayor o igual que 0.
2:42Ya.
2:46Eh, ¿por qué n + 2? Eh, porque eh
2:53como ustedes eh están ya habituados eh
2:56nuestro nuestras enumeraciones solemos
2:59hacerlas a partir de n = 0 en adelante,
3:01¿no es cierto? Entonces, ¿cuál sería el
3:04caso de un polígono para n = 0? eh
3:08n = 0 eh serían un polígono de dos eh
3:14vértices, o sea, simplemente una línea,
3:18¿no es cierto? Ahí están los dos
3:19vértices. Los dos extremos de esa línea
3:21son los dos vértices del polígono. Y
3:26a ver, llamemos
3:29de cuántas maneras distintas llamemos
3:31TUN. Pongámosle nombre, ¿no es cierto?
3:34Eh, ¿cuánto sería el TU aquí? sería uno,
3:37¿no es cierto? Sub0 es 1. Hay una sola
3:40manera de triangular eso, no poner nada
3:43y está triangulado.
3:45Para n = 1, eso sería un polígono con n
3:49+ 2, o sea, tres vértices. Eso es un
3:51triángulo.
3:53Ya,
3:55para triangular un triángulo no necesito
3:57agregar ninguna línea porque ya está
3:58triangulado, ¿no es cierto? Entonces,
3:59nuevamente hay una manera de hacerlo.
4:03El primer caso, el primer caso
4:07interesante es el caso n = 2, porque ahí
4:12eh yo tengo
4:15este trapezoide, ¿no es cierto?,
4:18que tengo
4:21dos maneras de triangularlo. Ah,
4:28una es así y la otra es así, o sea, t su
4:36igual 2 en este caso y así podemos
4:38seguir, ¿no es cierto?
4:42Entonces,
4:46la pregunta es, ¿cómo podría ser el caso
4:50general? Ya. Entonces, digamos que sea,
4:56pongámosle una T cursiva,
5:02eh la clase
5:05de todas las triangulaciones posibles,
5:19¿ya? O sea, igual como lo hemos hecho
5:21antes, no vamos a poner eh todas
5:24triangulaciones de de n vértices, ¿ya? O
5:27de n más dos vértices, sino que vamos a
5:29poner todas las triangulaciones
5:30posibles, sea la cantidad de vértices
5:32que sean. Y luego podemos afinar y y
5:36separar por el número de vértices, ¿no
5:38es cierto? Y y en y extraer coeficientes
5:41y ahí tener la solución. Pero la
5:42enumeración la hacemos de todo, la clase
5:44infinita, ¿ya? Lo mismo que hicimos para
5:46los árboles binarios, para los vueltos,
5:48para todo, ¿no? Entonces, si t cursiva
5:51es la clase de todas las triangulaciones
5:53posibles, la pregunta es, ¿qué
5:55estructura tienen esas triangulaciones?
5:57Eh, y
6:00la idea es la siguiente. Supongamos que
6:04yo tengo aquí mi
6:07polígono que voy a triangular
6:14ahí. Ya.
6:17Eh, y
6:24tengo un vértice,
6:27perdón, un un una un lado del polígono
6:31designado como la base. Ah, supongo que
6:34este que estoy poniendo más en en
6:36negrita.
6:39Okay.
6:40Entonces, eh yo puedo eh
6:46estoy tratando de encontrar una
6:48formulación recursiva. Ah, entonces lo
6:49que yo puedo hacer es ver a cuál
6:53triángulo pertenece la base, ¿cierto?
6:56Porque cualquier triangulación
6:58eh va a contener la base. ¿Aquí?
7:01Entonces, miren, eh, por ejemplo, si
7:03volvemos aquí atrás,
7:06aquí ya la base está contenida en ese
7:09triángulo de la derecha, mientras que
7:11acá la base está contenida el triángulo
7:12de la izquierda, ¿ya? Y cuando yo tengo
7:15muchos más vértices, la base puede estar
7:19contenida en un triángulo que incluya a
7:23a este vértice, por ejemplo, o a ese
7:25vértice o a ese vértice, incluso a este
7:29vértice ahí. No, es cierto, incluso este
7:32otro ahí.
7:35Entonces, en general, lo que yo puedo
7:37decir
7:39es que
7:46la base va a estar
7:51contenida en un triángulo que involucra
7:56a uno de los eh vértices.
8:00Pero seg una posibilidad, porque después
8:02esa misma posibilidad hay que
8:03considerarla para todos los restantes
8:05vértices de los cuales este podría ser
8:08el extremo superior, ¿no es cierto? Ya.
8:11Eh, pero supongamos que es este vértice,
8:12es este triángulo. Una vez que yo tengo
8:14identificado el triángulo al cual
8:16pertenece la base, lo que tengo aquí a
8:18la izquierda
8:22es un polígono complexo que hay que
8:23triangular y lo que tengo aquí a la
8:25derecha es otro polígono complexo que
8:27hay que triangular. Entonces, y esto hay
8:29que hacerlo de todas las maneras
8:30posibles. Y esto hay que hacerlo de
8:31todas las maneras posibles. O sea, por
8:33lo tanto, toda triangulación,
8:39ya toda triangulación
8:43se puede expresar
8:45como eh un cierto triángulo que tiene
8:50una base,
8:52¿no es cierto?,
8:53y tiene
8:56su triángulo construido sobre esa base y
8:59a la izquierda
9:04hay una triangulación que es esta
9:09y a la derecha hay otra triangulación
9:11que es esta.
9:13Okay. Ahora, eso es suponiendo que
9:19aparte de la base existe eh un tercer
9:22vértice para formar un triángulo, ¿no es
9:24cierto? O sea, eso supone que el número
9:27de
9:29vértices totales es por lo menos tres,
9:31¿no es cierto?
9:32Entonces, de esta formulación recursiva
9:35que ha excluido eh un caso, que es el
9:39caso cuando hay solamente dos vértices,
9:42¿no es cierto? Esto que yo acabo de
9:44escribir ahí es para tres o más, pero
9:46cuando hay solo dos vértices, en ese
9:47caso, eso es un caso aparte
9:50que es, por supuesto, disjunto con los
9:51anteriores, por lo tanto lo puedo
9:52escribir con más y es este el caso en
9:56que hay solo una base nada más, o sea,
9:59una línea. El caso n = 2, perdón, el
10:02caso n = 0, que significa que hay dos
10:05vértices. Okay. Entonces, esta es mi
10:09esta es mi fórmula recursiva.
10:12Y
10:13si ustedes recuerdan
10:16aquí, hagamos un paréntesis para
10:19recordar lo que pasaba con los árboles
10:20binarios.
10:28En los árboles binarios, yo tenía que la
10:30clase de todos los árboles era, ya sea
10:33un árbol vacío
10:36o si no
10:38un nodo raíz con un árbol a la izquierda
10:42y otro árbol a la derecha, ¿cierto? Y
10:46eso daba origen a los números de
10:48catalán. Bueno, lo que estamos mirando
10:50aquí
10:52es exactamente la misma ecuación.
10:55ya comparada con esa y por lo tanto el
10:59la solución va a ser la misma. Eso
11:01implica
11:03que
11:04la solución son los números de catalán.
11:10O sea, el número de maneras de
11:12triangular un polígono complexo con n +
11:162 vértices para n mayor o igual que 0
11:18son los números de catalán. 1/ por n + 1
11:23* 2n sobre n coeficiente binomial. Hm.
11:27Así que ese era el ejemplo que se me
11:29había quedado en el tintero y que quería
11:31eh
11:33quería verlo con ustedes antes de pasar
11:38a eh ver eh el siguiente tema que lo
11:43vamos a introducir de inmediato aquí.
11:46A ver, eh, hasta ahora
12:00visto, hemos trabajado, hemos trabajado
12:07con funciones generatrices, ¿no es
12:10cierto?
12:13de la forma a dez
12:17igual sumatoria de a sub n por z la n
12:21para n mayor o igual que 0, ¿no es
12:22cierto? Y también esto lo hemos
12:25expresado a veces como sumatoria para
12:27alfa en una cierta clase de z elevado al
12:31tamaño de alfa, ¿no es cierto? Eh, y
12:34ahora
12:36a partir de ahora estas funciones
12:38generatrices
12:40eh para distinguirla de las que vamos a
12:42ver a continuación, las vamos a llamar
12:45funciones
12:46generatrices.
12:49Bueno, a veces las llamamos funciones
12:50generatrices, no va, pero cuando
12:52queremos distinguirlas de otras las
12:53llamamos funciones generatrices
12:54ordinarias.
12:58¿Ya? ¿Por qué? Porque ahora vamos a
13:02introducir
13:04las funciones
13:06generatrices
13:11exponenciales.
13:21FG E.
13:29La definición no es muy distinta.
13:32Eh, una función general exponencial la
13:34vamos a llamar agorro de Z para
13:36distinguirla de la de las que no llevan
13:39el gorrito ese y que son ordinarias.
13:42Y en vez de poner g cursiva sub z de n,
13:46eh lo vamos a llamar e cursiva sub z de
13:50azu n por exponencial.
13:54Y la definición es que esto es la
13:56sumatoria para n mayor o igual que 0 de
13:59a sub n por z a la n pero dividido por n
14:03factorial.
14:06Y lo que es lo mismo, la sumatoria para
14:09todo alfa en una cierta clase a de Z
14:14elevado al tamaño de alfa, ¿no es
14:16cierto? Pero ahora dividido por el
14:18tamaño de alfa factorial.
14:28Ya, estas son las funciones generatrices
14:30exponenciales. Antes de entrar a ver las
14:33propiedades y la álgebra relacionada con
14:35las funciones generatrices
14:36exponenciales,
14:38eh
14:41tenos un poquito de intuición de por qué
14:43queremos hacer esto.
14:45Los objetos con los que hemos estado
14:47trabajando hasta ahora, por ejemplo,
14:49árboles binarios, ya son eh lo que se
14:53llama objetos no rotulados porque eh
14:57cada uno de los átomos es representado
15:00por un puntito negro, ¿no es cierto?
15:02Conectado con líneas con otros puntitos
15:03negros y lo único que importa es qué
15:05forma tiene, qué estructura tiene esta
15:07este objeto constituido por estos
15:10átomos, ¿no es cierto? Pero cada átomo
15:12es indistinguible de cada otro átomo.
15:15Ah, no hay diferencia entre un puntito
15:17negro y otro puntito negro.
15:20Eh,
15:22eso eh me resulta útil. Bueno, hasta
15:25hemos visto que que nos ha permitido
15:26resolver una serie de problemas, ¿no es
15:27cierto? Pero cuando empezamos a estudiar
15:31eh estructuras de datos y queremos hacer
15:33análisis de estructuras de datos, a
15:35veces eh eso no nos basta. Necesitamos
15:39eh distinguir eh de acuerdo al contenido
15:42de de esos átomos, al contenido de esos,
15:44¿no? Entonces, eh en hay otros modelos
15:47en donde cada átomo estáene está
15:52rotulado, tiene una etiqueta y eso
15:55permite distinguirlo de otros átomos.
15:57¿Okay? Entonces, ¿qué es lo que pasa?
15:59Por ejemplo, cuando un árbol binario lo
16:02utilizamos para guardar información y se
16:03transforma en un árbol de búsqueda
16:05binaria donde cada eh eh todos los eh
16:12datos que están en el subárbol izquierdo
16:13son menores que el dato que está en la
16:15raíz, ¿no es cierto? Y el dato que está
16:16en la raíz es menor que todos los datos
16:18que están en su árbol derecho. Ya para
16:21poder decir eso, eso eh la raíz y todos
16:24los átomos tienen que contener un dato,
16:26¿no es cierto? Eh, así que ahora ya no
16:29son puntos negros indistinguibles unos
16:31de otros, no, son totalmente
16:33distinguibles porque contienen datos
16:34distintos. Ah, ahora en en muchas
16:38aplicaciones, ¿cuánto es el valor del
16:41dato que hay ahí en la raíz, por
16:43ejemplo, versus lo que están en los
16:45subárboles?
16:46El valor exacto no importa. Ah, podría
16:49ser, por ejemplo, un árbol en donde yo
16:52almaceno nombres de personas, ¿ya?
16:54Entonces, hay un nombre de una persona
16:55en la raíz, un nombre persona en el hijo
16:58izquierdo, un nombre persona en el hijo
16:59derecho. ¿Okay? Eh, y y
17:04yo puedo hacer el análisis de eso, pero
17:06podría ser el mismo árbol donde en vez
17:08de haber nombre de persona en los nodos,
17:10ahora hay hay números reales. Entonces,
17:12hay un número real en la raíz, un número
17:14real en el dijo izquierdo, un número
17:15real en el dijo derecho. Y lo que
17:17importa entonces ya no es tanto el valor
17:19exacto, que si era un string, que si es
17:20un número real, podría ser un número
17:22entero, ¿ya? Eh, sino que la relación de
17:24orden que hay entre ellos, porque lo que
17:26importa es que lo que sea que está como
17:28hijo izquierdo tiene que ser menor que
17:30la raíz. lo que sea que hay como hijo
17:32derecho tiene que ser mayor que la raíz.
17:34Entonces es la relación de orden la que
17:36importa más que el valor específico que
17:38hay. Y por lo tanto, entonces cualquier
17:41asignación de de datos sobre estos
17:43nodos, eh esos esos datos yo los puedo
17:47sustituir por los números del uno al n,
17:50¿cierto? Siempre yo puedo rotular
17:55los nodos de modo que los rótulos sean
17:58estrictamente los números del uno al n.
18:01Ah. Eh, y siempre yo puedo hacer eso
18:04preservando la relación de orden que
18:06había, ¿no es cierto? O sea, si si aquí
18:09había un número menor que el de allá,
18:10cuando yo estoy distribuyendo los
18:11números del uno al n, acá voy a poner un
18:13número que sea menor que el de allá. Y
18:16todas estas relaciones de orden me van a
18:17determinar una única manera de
18:19rerrotular. Eh, como ustedes son gente
18:22que conoce de estructura de datos, eh,
18:24la manera de hacerlo es hacer un
18:26recorrido en inorden para el árbol, ¿no
18:28es cierto? Eh, asignando los números 1 2
18:313 hasta n a medida que yo me los voy
18:32encontrando en el recorrido en orden.
18:35¿Okay? Entonces, para todos los fines,
18:38eh yo siempre voy a poder suponer que
18:41los rótulos que yo le asigno a los
18:42átomos son los números de luna alenete.
18:45¿Ya? Entonces, supongamos que yo tengo
18:48eh un una cierta estructura constituida
18:50por n átomos y yo la he eh yo sé cómo
18:54enumerar esa estructura usando funciones
18:56generatrices ordinarias porque los
18:57átomos son indistinguibles. Pero ahora
18:59yo vengo y digo, "No, ahora van a ser
19:02distinguibles. Yo le voy a hacer una
19:03asignación de rótulo del lun al n." Ya.
19:06Bueno, de cuántas maneras distintas yo
19:08tengo que puedo asignar estos números
19:10del uno al n, ¿no es cierto? En algunos
19:12casos va a haber una sola porque yo
19:14tengo que cumplir una restricción, pero
19:15en caso general, en el caso general los
19:18nmeros se pueden distribuir de todas las
19:19maneras posible, ¿ya? Eh, y luego veré
19:22cuáles de ellas cumple las restricciones
19:24y cuáles no, pero la asignación en
19:26general puede ser eh de todas las
19:29maneras posibles. ¿Y de cuántas maneras
19:31posibles yo puedo asignar n rótulos a n
19:34nodos? Eh, de n factorial manera, ¿ya?
19:38Porque una vez que tomo uno y lo asigno
19:39aquí, para los restantes me van quedando
19:41n - 1. Entonces acá puedo el siguiente
19:44lo puedo rotular con n - un rótul nada
19:47más. Ya. Y ahora que ya usé dos rótulos,
19:50me van quedando n - 2 y y como todas
19:52estas selecciones son independientes, se
19:54van multiplicando, entonces queda n * n
19:57- 1 - 2 hasta 1, o sea, n factorial y de
20:00ahí aparece ese factorial. Entonces, ya
20:03eso es para cancelar el hecho de que yo
20:06hago esto, para cancelar el hecho que yo
20:08hago esta asignación de todas las
20:09maneras posible, eh, por otro lado,
20:11divido por el número y y vuelvo a estar
20:13en un contexto muy parecido al que ya
20:15tenía. Esa es la intuición detrás de
20:17todo esto. Pero antes de llegar a esa
20:20intuición y de por qué todo esto
20:21funciona, vamos a ver algunas
20:23propiedades de de esta nueva función
20:26generatriz.
20:33Bueno, la primera que no debe ser
20:35ninguna eh sorpresa
20:38es la linealidad.
20:46Ya. e
20:50la
20:55la definición de esto por ser a través
20:58de una serie ya eh
21:02me permite concluir sin problema que la
21:05función exponencial en de lambda a sub n
21:11más mu, por ejemplo, es lambda por la
21:16exponencial en z de a sub n más mu por
21:20la exponencial en z de b sub n, ¿no es
21:23cierto? Yo puedo aplicar
21:26linealmente esto,
21:29una segunda propiedad y eso era lo mismo
21:31era para las funciones geratrices
21:32ordinarias.
21:34La con la segunda ya nos eh ya nos
21:38apartamos ah eh
21:42de lo cómo eran las
21:46funciones ordinarias, porque vamos a ver
21:48qué pasa cuando yo hago una derivada.
21:50¿Qué pasa cuando yo hago de A de Z de a
21:54corro de Z?
21:57Ya, eso va a ser de AD de Z
22:01de la sumatoria de A sub n z a la n
22:07partido por n factorial para n mayor o
22:09igual que 0, ¿no es cierto?
22:11Ya. Eh,
22:15eso va a ser igual a eh la sumatoria
22:22ya de
22:25Bueno, a ver si
22:28derivemos al tiro. Ya va a ser la
22:31derivada de lo de adentro, ¿no es
22:32cierto? Que va a ser n por a sub n por z
22:37la n - 1, ¿cierto? dividido por n
22:41factorial para n mayor o igual que 0.
22:44Ya. Ahora,
22:49eh el primer término de esta sumatoria
22:51es cero, ¿no es cierto?
22:54Porque la función generativ con un
22:55término constante y después viene el
22:57término que contiene Z, después el Z
22:59cuadrado, etcétera, ¿no es cierto?
23:00Ustedes conocen la expansión en serie de
23:02Taylor de una función generatriz.
23:04Entonces, el primer término es
23:05constante, por lo tanto, el derivador se
23:06va.
23:08Entonces, sin ningún problema, yo puedo
23:09hacer que esta sumatoria parta de uno en
23:11adelante. ¿Okay? ¿Ya? Y una vez que yo
23:14sé que esta sumatoria parte de uno en
23:15adelante, yo sé que entonces acá abajo
23:19en el en el denominador hay por lo menos
23:21un factor. Ah eh abajo hay un n por n -
23:261, etcétera, pero eh por lo menos hay
23:27uno, ¿no? No es un producto vacío y por
23:30lo tanto, entonces yo puedo cancelar
23:34este n de aquí con el primer n
23:37factorial, quedando aquí abajo un n - 1
23:40factorial.
23:42¿Okay?
23:45Y ahora que
23:51ahora yo puedo pasar el
23:55aquí en la sumatoria puedo pasar el uno
23:57a la izquierda restando n - 1 mayor o
23:59igual que 0.
24:00Y aquí cuando dice a su n, puedo decir
24:03que eso es lo mismo quiere decir a su n
24:05- 1 + 1. Y acá tengo z la n - 1 y acá
24:10tengo n - 1 factorial y y y estoy, a
24:13ver,
24:16y estoy escribiendo todo esto para que
24:18quede en evidencia que todo esto está
24:20expresado en términos de n - 1. Entonces
24:22ahora yo puedo hacer un pequeño cambio
24:23de variable y al n - 1 llamarlo n.
24:27Entonces, va a quedar así. sumatoria
24:28para n mayor o igual que 0 de a sub n +
24:311, ¿no es cierto? Por z a la n divido
24:35por n factorial, que es una perfecta
24:36función generatriz exponencial. Función
24:39generatriz exponencial de qué? Función
24:42generatriz exponencial de a sub n + 1.
24:44¿Ya? Por lo tanto,
24:48la de derivada
24:54de de una función generaría exponencial
24:56es la
25:00es
25:01la función generatriz exponencial de a
25:04sub n + 1,
25:09¿ya?
25:10O sea, el la traslación, ¿se acuerdan
25:13cómo hacíamos la traslación en eh con la
25:17función generatrices ordinaria? Ya la
25:19función generatriz,
25:21la función generatriz ordinaria de az n
25:23+ 1 era 1 parido por z por la función
25:29generatriz exponencial a de z - a sub0.
25:33Ya, pero era básicamente dividir por z.
25:37Acá en vez de dividir por Z lo que hay
25:40es derivar. O sea, cuando yo tengo una
25:42traslación en mi eh recurrencias, por
25:45ejemplo, eso me genera una derivada en
25:48el dominio de las funciones
25:50generatrices. Por lo tanto, mientras eh
25:53muchas veces en las funciones
25:55generatricas ordinarias yo obtengo
25:57ecuaciones algebraicas que tengo que
25:59resolver en en situaciones similares con
26:02las funciones generatrices
26:03exponenciales, eh probablemente yo voy a
26:05obtener funciones, perdón, ecuaciones
26:08diferenciales que voy a tener que
26:10resolver. ¿Ya? Ahora, a pesar de que ahí
26:12se ve como derivada parcial, en realidad
26:14si Z es la única variable, eso va a ser
26:15una derivada eh común y corriente, así
26:18que no va a ser una ecuación derivadas
26:20parciales, ¿ya?
26:22Eh, okay. Otra propiedad,
26:27la multiplicación por Z.
26:38Ya
26:40en las funciones matrizes ordinaria, la
26:42multiplicación por Z corresponde a la
26:45traslación para el otro lado, el a n -
26:471, ¿no es cierto? Vamos a ver qué
26:49significa multiplicar por z aquí.
26:53¿Qué pasa cuando yo hago z por acorro de
26:55z, ¿cierto?
26:59Eso es la sumatoria para n.
27:04Eh,
27:06ver
27:08esto, perdón.
27:11Ah, ya. Listo. Okay. Eh, sumatoria para
27:15n igual que er, ¿no es cierto? De eh a
27:19su n
27:22va a quedar por z a la n + 1, ¿cierto?
27:25Partido por n factorial.
27:31Okay. Eh,
27:34entonces ahora voy a hacer un cambio de
27:35variable
27:38y al n + 1 lo voy a llamar n. Okay.
27:43Entonces va a quedar
27:46eh
27:54n + 1 lo llamo n.
27:57El
28:02esto para que el a ver cómo me queda la
28:06el rango de la sumatoria. Ah, eh, va a
28:10partir de n un adelante. Claro, el con
28:12el nuevo n va a ser n 1 y esto va a
28:16quedar a sub n - 1
28:20y esto va a quedar z a la n y esto va a
28:24quedar n - 1 factorial.
28:28Ahí está. Hm.
28:34Y y y Ah, ya. Y
28:44ah, ya. Y ahora lo que yo necesito,
28:49ya tengo el z a la n.
28:51Lo lo que estoy tratando siempre de
28:53hacer para que ustedes sepan por qué
28:54estoy haciendo estos cambios de
28:55variable, lo que estoy tratando siempre
28:57de hacer es que esto quede como
28:58sumatoria de algo multiplicado por z la
29:00n, pero el exponente tiene que ser n.
29:04Ah. Eh, y para eso yo puedo tener que
29:06hacer estas traslaciones y cosas. Ah,
29:09eh, para que si el exponente era z a la
29:11n + un, eso no me sirve para
29:13identificarlo como función generalía
29:14exponencial. Necesito que sea z a la n y
29:17ahí yo veo qué es lo que quedo
29:18multiplicando z a la n para identificar
29:20la función que esto es la función
29:21general exponencial de qué. Ya.
29:24Entonces, aquí ya me estoy acercando,
29:25tengo z a la n, eh, pero en este caso
29:28recuerden que además tiene que estar
29:29dividido por n factorial para que todo
29:31calce. Entonces, ¿qué le falta al eh
29:34denominador para hacer un n factorial?
29:35Falta que lo multiplique por n.
29:37Entonces, puedo multiplicar por n abajo
29:38siempre que yo multiplique por n arriba
29:40para mantener todo. Entonces, me va a
29:42quedar así. Sumatoria
29:45de n * a sub n - 1
29:49z a la n parido por n factorial.
29:52Estamos super cerca.
29:56Hay solo una cosa que va faltando. El
29:58rango de suma tiene que ser de cero en
30:00adelante. Ya si parto de uno en adelante
30:04está incompleta la serie o yo le agrego
30:07y le quito ya para compensar. Pero en
30:10este caso la verdad es que no tengo que
30:12agregar nada, o sea, tengo que agregar
30:15el término n = 0. Ya, pero si agrego el
30:17término n = 0, eh, ese el término n = 0
30:22es 0 porque el término que tengo que
30:25agregar es de la forma n por su n - 1,
30:27¿no es cierto? Entonces, si n vale 0,
30:29eso va a ser cer. Así que no no cuesta
30:31nada decir que esta sumatoria en
30:33realidad puede partir de cero en
30:34adelante, ya porque lo que estoy
30:37agregando es un cero. Y ahí sí ya está
30:40identificado
30:42esto.
30:44Perdón, pong otro color.
30:47Esto es lo que multiplica al z la n
30:50partido por n factorial. Por lo tanto,
30:54eh la función generatriz exponencial de
30:59n por a sub n - 1
31:03es z por aro de z.
31:09Okay.
31:11Y si ahora yo junto las propiedades dos
31:14y tres,
31:17¿ya?
31:20Entonces, la propiedad tres es
31:21multiplicar por Z. Y eh, ah, pero
31:26primero la propiedad dos. La propiedad
31:27dos es derivar y luego multiplico por Z.
31:31Entonces, la pregunta es, ¿qué pasa si
31:32yo hago Z por D Z? Ya, si esto se lo
31:38aplico al agorro de Z.
31:42Okay. Entonces, eh, ¿qué va a pasar al
31:46al multiplicar por Z? Voy a tener la
31:49exponencial Z de A sub n + 1, ¿cierto?
31:53Eh, pero ahora cuando al ese era al
31:57derivar, pero ahora cuando
32:03multiplico por z,
32:05entonces me va a quedar n multiplicado
32:08por a sub n - 1, pero a sub n ya era su
32:10n + 1. Ah, entonces eso compensa. Uno lo
32:15traslada para adelante, el otro lo
32:16traslada para atrás y al final lo que
32:18queda es que esto es la función
32:20generatriz exponencial en Z. de n por a
32:23sub n.
32:26Ya.
32:28Así que ahí lo tenemos. H
32:32ya. La siguiente propiedad
32:36es la convolución.
32:50A ver, eh,
32:55¿cómo es la convolución aquí? Un poquito
32:56más complicada que la convolución en
33:00eh que la convolución de las funciones
33:03geratrices ordinaria. ¿Se acuerdan cuál
33:05era la A ver, recordémoslo mejor
33:10recordemos
33:14que para las funciones generatrices
33:18ordinarias,
33:20ya
33:22A de Z por BDZ
33:26era la generatriz en Z de una
33:30convolución de la sumatoria de A sub* B
33:32sub J.
33:34para todo y j mayor o igual que 0 tal
33:37que i + j = n.
33:40¿Ya? O la otra manera de escribirlo esto
33:43de manera asimétrica, es decir, la
33:44generatriz en Z de la sumatoria sobre K
33:49para 0 menor o igual que K menor o igual
33:51que n de n sobre K,
33:55A sub k b sub n - k.
33:59Ahí está escrito de manera asimétrica.
34:00Arriba está de manera simétrica.
34:03¿Qué pasa? Ya. Entonces, ahora
34:09para las funciones generatrices
34:13exponenciales, ¿qué es lo que pasa?
34:15Eh, que sería a gorro de Z
34:20por bro de Z, que sería el producto de
34:25dos funciones generatrices
34:26exponenciales.
34:28Bueno, el primero sería la sumatoria.
34:31Como tengo dos distintas, no voy a usar
34:34el níndice,
34:36porque quiero que sean su índices
34:37distintos. Entonces, al primero voy a
34:39hacer el su índice i. Entonces, va a ser
34:41sumatoria sobre i mayor o igual que 0 de
34:44a su i por z a la i parido por i
34:48factorial, ¿no es cierto? Ya, eso es.
34:52Y la otra sería sumatoria, digamos,
34:54sobre J mayor o igual que 0
34:57de B sub J z a la J parido por J
35:01factorial. Ya.
35:05Y ahora esto lo puedo transformar en una
35:10doble sumatoria.
35:12Sumatoria sobre todo y i y j mayor o
35:15igual que 0, ya de
35:19a su I.
35:22por B subj
35:24partido por Iorial J factorial, ¿no es
35:27cierto?
35:29Z a la I + J.
35:33Okay. Ya.
35:38Aquí lo que yo puedo hacer es
35:42multiplicar y dividir por i + j
35:45factorial. Entonces, pongamos aquí un i
35:49+ j factorial y acá dividimos por i + j
35:55factorial. Okay.
35:58Entonces, ¿cómo queda esto? Sumatoria
36:01sobre todo y j mayor o igual que 0, ¿no
36:04es cierto?
36:06Y
36:08y el i + j factorial.
36:12Eh, si yo tomo todo esto,
36:16tomo el i + j factorial y lo divido por
36:19esos dos factoriales,
36:21eso lo que me entrega aquí es un i com
36:25j, el coeficiente binomial simétrico,
36:28¿ya?
36:31Y eso queda
36:34eh multiplic por a sub por b sub j
36:40por z
36:42a la i + j
36:48partido por i + j factorial.
36:56Okay.
36:59Eh, y ahora eh
37:05esto,
37:07esta sobre sumatoria la voy a ir
37:10agrupando de acuerdo al valor de I + J.
37:14¿Ya? Entonces voy a separar según cuánto
37:17vale I + J.
37:19Eh, entonces voy a
37:22sumar
37:25sobre todo n mayor o igual que 0.
37:28No, voy a ir suponiendo que + j vale n.
37:31Okay. Entonces, para n = 0, n = 1, n =
37:332, todos los posibles valores que puede
37:34tomar y + j los voy viendo uno por uno.
37:37Entonces, voy a suponer que al interior,
37:40ahora al interior voy a restringir esta
37:42sumatoria
37:45que era sobre todo y j mayor o igual que
37:470. la voy a restringir al caso que i + j
37:51= n, ¿cierto? Porque yo voy por un y
37:55entonces, ¿qué me va a quedar? Me va a
37:56quedar eh i com j
38:01a sub i b sub j.
38:04Okay. Y acá va a quedar z a la n porque
38:07i + j vale n dividido por n factorial
38:09porque + j vale n. Y entonces ahora
38:16esta
38:17cosa que acabo de encerrar entre
38:19paréntesis naranja, ya
38:22eso es el
38:25eso es lo que multiplica al z la n
38:26parido por n factorial. Por lo tanto, eh
38:29el la función generatriz exponencial que
38:31está resultando aquí es la función
38:34generatriz exponencial aplicada a eso.
38:36Ya creámoslo.
38:39Por lo tanto,
38:42a gorro de Z por bro de Z
38:48es la generatriz exponencial en Z de
38:51esto de la sumatoria
38:54sobre todo y j mayor o igual que 0 tal
38:57que i + j = n
39:00de i j
39:02a su i p sub j.
39:05¿Ya? Y esto que está aquí adentro es
39:08como una convolución.
39:10Si esto hubiera sido sumatoria de a su I
39:11por b sub j con esos sub índices, eh
39:14sería una convolución tal como la
39:16conocemos, pero esta es una convolución
39:18en que está eh multiplicada por I+ J, el
39:23coeficiente I+ J.
39:25¿Qué qué significa eso? ¿Y por de dónde
39:28puede venir eso? Viene de esta
39:31interpretación que yo les decía, que
39:33aquí lo que estamos trabajando es con
39:35objetos rotulados. Ya luego vamos a
39:37formalizar eso. Entonces, eh si yo tengo
39:42eh un los objetos del primer tipo A
39:45rotulado de todas las maneras posibles y
39:47los de tipo B rotul de todas las maneras
39:49posibles, los objetos de tipo A van a
39:52estar tener como rótulos del uno al I,
39:55¿no es cierto? Porque es un objeto de
39:56tamaño I, del uno al I. Y estos otros
39:59que son los objetos de tipo B, son de
40:01tamaño J, que también están entonces
40:04rotulados por números del 1 al J.
40:06Y ahora yo los voy a a unir estos dos
40:08objetos en un en un nuevo objeto a
40:11través de un producto cartesiano,
40:12¿cierto? Eh, pero no puedo llegar a
40:15unirlo porque si llego de los unos va a
40:18haber rótulos duplicados, como aquí está
40:21numerado del uno al i y acá están
40:23numerados del uno al j, si los uno va a
40:25haber dos objetos rotulados uno, dos
40:27objetos rotulados dos y así. Ah, eso no
40:30puede ser. Entonces, lo que hay que
40:32hacer es rotular.
40:36Ahora, los rótulos que yo voy a asignar
40:38son los rótulos del 1 al i + j, ¿no es
40:41cierto? Ya. Eh, ¿y de qué manera? Eh, de
40:46esos rótulos yo voy a extraer y de ellos
40:50y y los voy a asignar a los objetos de
40:53tipo A y los J restantes a los objetos
40:56de tipo B. y dentro del del los objetos
41:00de tipo A hay solo una manera de
41:02asignarlos porque tienen que preservar
41:04el orden con el que ya venían y en el
41:06otro también solo una manera de
41:07asignarlos porque hay que preservar el
41:10orden que venían. Entonces, la única
41:11decisión que se toma es de los i más j
41:14objetos, cuáles i van para acá y cuáles
41:17j van para allá. Eso se hace de I + J
41:20sobre i maneras o de I + J sobre J
41:22maneras, que es exactamente el
41:24coeficiente bibendomial y + J. Ya, de
41:27ahí aparece ese factor. Adelante, lo
41:30vamos a poder expresar de de manera más
41:33más precisa, pero esa es la esa es la
41:37intuición. Ya. Y ahora para por
41:41completitud eh esto lo podemos escribir
41:43también de manera asimétrica.
41:47¿Cómo sería de manera asimétrica? Decir
41:49que esta es la sumatoria sobre todo K
41:51para 0 menor o igual que K menor o igual
41:53que n.
41:54Entonces, al al I + J lo estoy llamando
41:58N. Claro, porque I + J es n, ¿no es
42:01cierto? Y al i lo estoy llamando K y al
42:04J lo estoy llamando N - K. Entonces, si
42:08si + J es n, eh, el I+ J queda N sobre i
42:15o n sobre J. No, pero como cambié nombre
42:18y le llamo K, ahora va a ser N sobre K,
42:20coeficiente binomial común y corriente.
42:23Y el A subido ahora es A sub K. Y el B
42:26sub J es B sub N - K.
42:29Así que ahí tengo la versión asimétrica
42:32de esta propiedad
42:35en que eh antes con las funciones
42:38generatrices exponenciales, ya lo que yo
42:41tenía era la ups, perdón.
42:45Ahí sí. Antes con la función generatriz
42:48ordinaria lo que yo tenía era la
42:49sumatoria, ¿cierto?, de la subk por b
42:53sub - k, pero ahora aparece ese
42:55coeficiente multiplicando que acompaña a
42:58todas estas funciones generatrices eh
43:02exponenciales. ¿Okay?
43:05Muy bien.
43:07Entonces, eh esas son algunas de las
43:11propiedades que que vimos. Ah. Eh, vamos
43:14a ver ahora eh cómo se une esto con la
43:18numeración simbólica.
43:39versión simbólica y
43:42funciones generatrices exponenciales.
43:46Esto se refiere a cómo nosotros podemos
43:48ir de la estructura de los objetos
43:50directamente a las funciones
43:51generatrices sin pasar por los a sub n
43:55eh entre medio. ¿Ya? Entonces eh
44:01aquí vamos a empezar a formalizar un
44:02poquito esta intuición que yo les decía.
44:04Eh
44:06eh lo que vamos a hacer es considerar
44:14clases de objetos
44:20rotulados.
44:24Ya también a veces decimos etiquetados
44:31y en inglés se dice labeled.
44:38Y como les decía antes, sin perder
44:42generalidad,
44:48suponemos
44:55que los rótulos
45:00son los números
45:05del 1 al n.
45:09Okay. Si el objeto tiene tamaño N.
45:13Ejemplo,
45:18árboles generales
45:23rotulados.
45:32¿Qué cosa es un árbol general? Un árbol
45:34general consiste de una raíz
45:38y un conjunto de hijos
45:43de
45:47cero o más
45:49hijos.
45:53Ya
45:55puede tener cero hijos y en ese caso es
45:57ya es un no terminal dentro del árbol o
45:59puede tener varios hijos, puede tener un
46:01hijo, dos hijos, qué sé yo, la cantidad
46:03que quieran. Ya, así son los árboles
46:05generales. A diferencia de lo que
46:07ocurre, por ejemplo, en árboles eh
46:09binarios, ¿no es cierto? donde son dos
46:12hijos a lo más. Ya. Acá puede ser
46:14cualquier cantidad de cero en adelante
46:16sin límite. Ahí. La otra diferencia es
46:18que en un árbol binario yo distingo
46:20entre hijo izquierdo y hijo derecho, ¿no
46:22es cierto? Acá no, acá son simplemente
46:24los hijos, ¿ya? Eh, así es que, ¿cómo se
46:28vería esto? Tengo espacio, ¿no? Hagamos
46:30acá en la siguiente página. Eh, por
46:33ejemplo, vamos, comparemos estructuras
46:36no rotuladas con estructuras rotuladas.
46:39Entonces, por ejemplo, para n = 1. Ah,
46:42los árboles generales siempre tienen por
46:43lo menos un nodo.
46:47Entonces, cuando la estructura es no
46:49rotulada
46:54versus cuando es rotulada.
47:03Okay. Eh,
47:06un árbol de un nodo no rotulado es eso.
47:09Ahí está.
47:12Un árbol rotulado se ve igual. Ah, pero
47:18contiene un rótulo.
47:21Ahora, como es uno solo, hay solo una
47:22manera de rotularlo. Así es que eh y
47:25llamemos aquí el t sub n, el número de
47:29objetos rotulados es un
47:35caso de n = 2.
47:37En caso igual dos hay solo un árbol
47:39general no rotulado, que es ese.
47:42Un nodo con su hijo. No hay más.
47:45Ya,
47:47en el caso rotulado tengo dos, tengo el
47:51uno que tiene de hijo al dos y eso es
47:53distinto del dos cuando tiene de hijo al
47:56uno, así es que tengo dos ahí.
48:01¿Qué pasa con n = 3?
48:06Aquí tengo
48:08una posibilidad es S ese. Ese es un
48:09árbol general con tres nodos y este es
48:12el otro.
48:13Uno con dos hijos y no hay más. Ya
48:22no hay más. Entonces, eh si ahora yo
48:26rotulo, ¿cuántos voy a tener? Bueno, en
48:30en el que son tres en línea para abajo,
48:32yo voy a tener eh seis porque les puedo
48:35asignar rótulos de todas las maneras
48:36posible. Entonces, puede estar el uno de
48:39padre, padre el dos, el cual es padre el
48:42tres, ¿no es cierto? Pero eh podría ser
48:46el uno como padre del tres, que es padre
48:49del dos. Ese es otro árbol.
48:52Y no hay más posibilidades ahí, ¿no es
48:54cierto? Entonces ahora si el la rey
48:56fuera el dos, el hijo podría ser el uno
48:59y el tres. Pero la otra posibilidad
49:01cuando la raíz es el dos que el hijo sea
49:03el tres y acá está el uno. Y la última
49:07posibilidad es que en la raíz sea el
49:09tres. En este caso aquí estaría el uno y
49:12acá el dos. Pero también podría ser que
49:14siendo el tres la raíz que estuviera el
49:16dos y acá estuviera el uno. O sea, van
49:18seéis ahí.
49:20Pero ahora tengo que rotular eh ese
49:26arbolito en forma triángulo ahí.
49:28Entonces, pero ¿qué pasa? La raíz podría
49:31ser el uno y en ese caso los hijos
49:32tienen que ser el dos y el tres, ¿no es
49:34cierto?
49:36Eh, y uno diría, ya la otra posibilidad
49:38es que sea el la raíz del uno y que los
49:41hijos sean el tres y el dos, ¿no es
49:43cierto?
49:44Pero no, porque aquí el los hijos son un
49:48conjunto. Entonces el conjunto de hijos
49:512,3 es lo mismo que el conjunto de hijos
49:533,2. O sea, el orden no importa. ¿Ya?
49:57Entonces, o en otras palabras eh para no
50:00rotular más de una vez, yo puedo eh
50:02suponer que el conjunto de hijos está
50:03ordenado de izquierda a derecha, ¿ya? Y
50:06así me evito. Ese sería un orden
50:08canónico, ¿no es cierto? Entonces, el
50:103,2 no sería orden canónico, así que no
50:12lo cuento. El 2,3 sí lo cuento. Así que
50:15a partir de de de la estructura no
50:18rotulada se genera solo una estructura
50:20rotulada en ese caso, pero eh sí es
50:23distinto cuando la raíz es el dos,
50:25porque en ese caso los hijos serían el
50:27uno y el tres, ¿cierto? O cuando la raíz
50:30es el tres, porque en ese caso los hijos
50:33serían el uno y el dos.
50:36Si juntamos todo esto, el total es
50:40nueve. Hay nueve árboles generales
50:43rotulado. Ah,
50:48y por supuesto esto puede seguir ya,
50:52pero le vamos a poner continuará
50:55porque no lo vamos a resolver todavía.
50:57nos faltan herramientas matemáticas para
51:00poder saber, eh, porque ahí la pregunta
51:03sería, bueno, ¿y cuánto es para n, ¿no
51:05es cierto? ¿Cuántos árboles generales
51:08rotulados hay con n nodos? Ya todavía no
51:12sabemos, pero lo que sea, la fórmula que
51:16sea, va a tener que eh predecir
51:19correctamente que t de 1 es 1, que t de
51:222 es 2 y que t de 3 es 9 mínimo, ¿no es
51:26cierto? y de ahí para adelante. Ya.
51:29Entonces, ¿qué es lo que nos falta? Eh,
51:31saber más cosas sobre cómo construir
51:34objetos rotulados, cómo construir
51:36estructuras rotuladas a partir de átomos
51:38rotulados. Ah, entonces
51:41sí nos queda tiempo para eso. Ya. A ver.
51:45Sí, estamos bien. Ya.
51:49Entonces,
51:50eh
51:53ya si tenemos
51:59una
52:01clase
52:04A de objetos rotulados,
52:16se puede
52:18definir
52:21su función generatriz exponencial
52:25como la sumatoria
52:31sumatoria de a su n por z a la n parido
52:34por n factorial para n más igual que 0
52:38donde
52:41el a sub n
52:45se define como que a su n es el cardinal
52:47final de
52:50a cursiva sub n y a y a cursiva sub n el
52:55conjunto de todos los alfa en a
53:00tal que el tamaño de alfa n, ¿no es
53:01cierto? Es igual como lo hacíamos antes,
53:03¿ya? O bien derechamente yo puedo decir
53:06que esto es la sumatoria para todo alfa
53:09en a de z elevado al tamaño de alfa
53:15partido por el tamaño de alfa factorial,
53:18¿no es cierto? Esa es equivalente.
53:22Entonces, eh, ¿qué clases son
53:25importantes? Uno es la clase
53:29neutra, la que
53:32la clase asociada al neutro de la
53:35operación multiplicativa. Ah, esa clase
53:38eh la podemos llamar eh eh no no
53:43confundir con el operador subz, ya que
53:47contiene solamente
53:49eh
53:52la estructura de tamaño cero, ¿ya?
53:56y esa estructura y su función generatriz
54:00exponencial
54:02es 1, ¿cierto? Porque es eh 1 * z la 0
54:07parido por 0 factorial y es el único
54:09término de la sumatoria.
54:15Luego entonces es una clase neutra, la
54:18clase que contiene solo un objeto que es
54:19el objeto vacío, el objeto con cero, el
54:22objeto de tamaño cero, ¿ya?
54:24y está la clase atómica, que es el
54:26objeto de tamaño de uno.
54:32El caso atómica, llamémosla
54:35Z cursiva, contiene solo un objeto
54:40que está rotulado obviamente con el
54:41rótulo uno y eso conduce a que Z gorro
54:47de Z sea Z, ¿cierto?
54:50porque es 1 * z parido por 1 factorial.
54:58Otra es la clase
55:00de las permutaciones.
55:14Ya vemos la la clase P.
55:19Yo voy a tener todas las permutaciones
55:20de
55:22de átomos. Ah, entonces está de partida
55:28la
55:31permutación de cero elementos. Ya hay
55:34solo una manera es la permutación vacía.
55:37Acá está la permutación de un cuando es
55:39un solo elemento, esa es la única
55:41permutación que hay. Pero cuando son
55:42dos, ahí tengo la permutación 1 2 y la
55:47permutación 2 1, ¿no es cierto?
55:51Cuando son tres, ahí tengo la
55:55permutación 1 2 3
55:591 3 2
56:05hasta la 3 2 1.
56:093 2
56:111
56:13son seis, ¿no es cierto?
56:17Entonces,
56:19esta es uno, esa es un esa es, eso es 6,
56:26etcétera,
56:28que y este uno es 0 factorial, esto es 1
56:32factorial, 2 factorial, 3 factorial,
56:35etcétera.
56:37Por lo tanto, la función generatriz
56:40exponencial p r z que numera esta clase
56:43es la sumatoria
56:46de pechica sub n por z a la n parido por
56:48n factorial para n mayor igual que 0.
56:52Ya, pero
56:55pechica n, el número de permutaciones de
56:58de tamaño n es n factorial.
57:02¿Okay?
57:03Entonces, e este n factorial, los dos n
57:07factorial se cancelan y lo que queda es
57:09un sumatorio de z a la n partido por n
57:12factorial, que es 1/- z.
57:21Esa es la clase de las permutaciones.
57:22Esa es su función generatriz
57:24exponencial.
57:27La clase de las urnas.
57:36En combinatoria hablan de urnas eh como
57:39receptáculos donde uno puede depositar
57:42átomos a y dentro de de de la urna no
57:46hay ningún orden especial, digamos. O
57:47sea, es un conjunto. ¿Okay? Uno puede
57:50suponer que están en un orden canónico
57:52para no contarlo más de una vez. Eh,
57:55entonces, eh, la pregunta es, ¿cuál es
57:58la función generatria exponencial para
58:00la clase de las urnas?
58:06Si llamamos u cursiva a la clase de las
58:09urnas,
58:12eh, están las urnas de tamaño cero. Ahí
58:15es una urna donde no hay nada dentro.
58:18Está la urna de tamaño uno. Ahí está un
58:22objeto de tamaño uno. Adentro está la
58:25urna de tamaño dos, donde hay un objeto
58:27de tamaño uno y un objeto de tamaño dos,
58:30pero yo puedo suponer que están como
58:31flotando en el aire, ¿no es cierto? No
58:33están en ningún orden en particular.
58:36están la de tamaño tres, que estaría el
58:39objeto de tamaño uno, el objeto de
58:40tamaño dos, el objeto de tamaño tres,
58:42perdón, el objeto uno, el objeto dos,
58:44objeto tres, etcétera, y así
58:46sucesivamente.
58:49Entonces,
58:50hay exactamente una urna de tamaño cero,
58:54hay exactamente una urna de tamaño uno,
58:57una urna de tamaño dos, una urna de
59:00tamaño tres y así.
59:02Por lo tanto, la clase eh u gorro de
59:07zatoria
59:10para n mayor o igual que 0 de u sub n z
59:14a la n parido por n factorial,
59:19donde como acabamos de ver us n vale 1
59:21siempre.
59:24Eh, por lo tanto, esto es la sumatoria
59:26para n mayor o igual que 0 de z a la n
59:29parido por n factorial, ¿no es cierto?
59:32Y quién me puede decir cuánto vale esa
59:34sumatoria. Alguien que se acuerda de los
59:36cursos de cálculo.
59:43A ver,
59:45ver
59:48aquí abrí el chat para a ver si alguien
59:50me escribe que no se atreven a hablar o
59:54no quieren hablar.
59:56¿Cuánto va la sumatoria de n z la n
59:58parido por n factorial?
1:00:08Se ve familiar. Ah, sí, se ve super
1:00:10familiar.
1:00:12¿Alguien que haya puesto atención en
1:00:13clase de cálculo?
1:00:20¿Ustedes tienen Maple instalado en sus
1:00:21computadores?
1:00:24Alguien no abre Maple y dice zoom de Z
1:00:28elevado n partio por n factorial para n
1:00:29de hasta infinity
1:00:33y le va a decir exactamente qué es eso.
1:00:38Como torpeos. Ah,
1:00:43pero deían saber solo memoria. Sí,
1:00:48es solo
1:00:50una de las funciones más importante del
1:00:53universo.
1:01:02Nadie, nadie.
1:01:05M hría que usarlo los matemáticos.
1:01:09Ya, para que ustedes sepan, todos lo
1:01:14saben, pero pero se les olvidó, ah, para
1:01:17que ustedes recuerden, la sumatoria de z
1:01:19a la n partido por n factorial no es
1:01:20otra cosa que e a la z,
1:01:23función exponencial,
1:01:26ya,
1:01:27de hecho, que estemos hablando de
1:01:28funciones generaticas exponenciales,
1:01:30debería haberles
1:01:32eh soplado ahí que la cosa se vea por
1:01:35ahí, ¿no es cierto? E a la Z. Así que E
1:01:37a la Z. es la función generaliza
1:01:40exponencial de la clase de las urnas.
1:01:42Ya. Y por último, estos, por último creo
1:01:46sí, ¿no? Sí, estos objetos. Ya.
1:01:53Okay.
1:01:56Por último, eh la clase
1:02:01de las permutaciones cíclicas.
1:02:14¿Qué son las permutaciones cíclicas?
1:02:17Cursiva,
1:02:20una permutación cíclica eh es eh
1:02:25corresponde a es como una permutación,
1:02:28pero pero en un ciclo. Ah, entonces
1:02:30cualquier rotación del ciclo me sigue
1:02:31dando es la misma permutación cíclica.
1:02:34Ah, déjeme verlo otra vez de un ejemplo.
1:02:36E para que hay una permutación cíclica
1:02:38tiene que haber por lo menos un átomo.
1:02:40Entonces, la permutación cíclica más
1:02:42simple es la que dice uno y y ese es un
1:02:47ciclo, ¿ya? O sea, el uno va al uno,
1:02:54se queda ahí
1:02:56el
1:02:58la que tiene dos elementos. Bueno, el
1:03:01uno va al dos y el dos va al uno.
1:03:06Y esa es la única. Ah, porque uno podría
1:03:08decir la no. La otra es la que el dos va
1:03:10uno y el uno va al dos. Pero es la
1:03:11misma. Ah, o sea, yo la puedo yo la
1:03:14puedo empezar
1:03:17yo la puedo empezar leyendo aquí 1 do
1:03:21ya. o la puedo empezar aquí 2 1, pero es
1:03:23la misma permutación cíclica.
1:03:26Ah, o sea, el uno va el dos, el 2 va el
1:03:29uno.
1:03:31No importa como yo la comience leyendo,
1:03:32pero es lo mismo. El uno va el dos, el
1:03:34dos va un. Así que para que como se
1:03:37puede comenzar leyendo de cualquier
1:03:39parte, partiendo del uno al dos o el dos
1:03:43al uno, eh para evitar ambigüedades
1:03:47siempre voy a colocar como líder de la
1:03:50de la permutación cíclica al elemento
1:03:52menor de todo, o sea, al uno. ¿Ya?
1:03:54Entonces, si el si el si comienzo
1:03:57leyendo desde el dos, eso no es una
1:03:58permutación cíclica distinta, porque si
1:04:00yo la reescribo partiendo del uno, eh,
1:04:03va a ser el
1:04:06va a ser la misma que la otra. Okay, ya.
1:04:09Eh, ahora eh más interesante es cuando
1:04:11son tres, porque una posibilidad es que
1:04:13el uno vaya al dos,
1:04:17el dos vaya al tres y el tres vuelve al
1:04:20uno. Esa es una, ¿no es cierto?
1:04:23Y eso es lo mismo que si yo partiera del
1:04:252 al tres y del 3 al 1 o que partiera
1:04:27del 3 al 1 y el 1 al 2, sería todas la
1:04:29misma, pero esta otra es distinta, la
1:04:32que el uno va al tres, el tres va al dos
1:04:37y el dos va al uno.
1:04:41Ya, esa es distinta.
1:04:51Entonces, como decíamos, en este caso
1:04:55tenemos una, en este caso tenemos una,
1:04:59en este caso tenemos dos y así veremos.
1:05:02Okay.
1:05:14¿Cuánto es? Eh,
1:05:20entonces, ¿cuál sería? C, perdón.
1:05:23Cambiamos,
1:05:24cambiamos de color.
1:05:28Ya.
1:05:31¿Cuánto sería C gorro de Z?
1:05:36Ya sería la sumatoria de C sub n z a la
1:05:40n parido por n factorial, ¿no es cierto?
1:05:46Y la pregunta, ¿cuánto vale su n?
1:05:53Ya.
1:05:55¿Cuánto vale su?
1:05:57¿Cómo yo puedo construir todas las
1:05:59permutaciones cíclicas de tamaño N? Ya,
1:06:03bueno,
1:06:06el primer elemento del ciclo siempre va
1:06:08a ser el uno, ¿no es cierto? Por esta
1:06:11manera canónica de escribir la
1:06:12permutación. Ustedes ven que en los
1:06:15ejemplos que tenemos a la vista siempre
1:06:16parto del uno. La pregunta es, ¿qué
1:06:19viene después del uno? Ya. Eh, bueno,
1:06:22después del uno puede venir los
1:06:25restantes elementos permutados de
1:06:26cualquier manera,
1:06:28ya, por ejemplo, en el caso de
1:06:31permutación cíclica de tamaño tres, está
1:06:33al principio el uno y luego los que
1:06:35vienen son el dos y el tres y el tres y
1:06:36el dos. Son las dos permutaciones
1:06:39posibles de dos elementos. Ya, si esto
1:06:41fuera una permutación cíclica de tamaño
1:06:44cuatro, colocaríamos el uno al principio
1:06:47y luego vendrían las seis permutaciones
1:06:50posibles de tres elementos, ¿ya? O sea,
1:06:53ya que el uno está anclado al principio,
1:06:56aquí podría venir eh 2 3 4, ¿no es
1:06:59cierto? 2 43 eh etcétera, hasta el 4 32
1:07:066. O sea, en general c sub n
1:07:12es n - 1 factorial
1:07:18porque uno eh
1:07:22uno de los elementos queda fijo y los
1:07:25restantes se permutan.
1:07:27Ya, así es que eh esto va a ser
1:07:33ah y esto es la sumatoria para n mayor o
1:07:34igual que 1, ¿no es cierto? porque tiene
1:07:36que haber por lo menos un elemento para
1:07:38para que haya una un ciclo. Entonces
1:07:41esto va a ser la sumatoria
1:07:44para n mayor o igual que 1 de n - 1
1:07:49factorial
1:07:51dividido por n factorial por z a la n,
1:07:55o sea,
1:07:58sumatoria
1:08:00para n mayor o igual que 1
1:08:03de z la n parido por
1:08:17Ya. ¿Y cuál es la
1:08:24Y esa sumatoria cuánto da? Sumatoria z a
1:08:27la n parido por n. Solo podríamos
1:08:31probar. Bueno, tengo más de una manera
1:08:32de hacerlo. Esto, por supuesto, ¿eh?
1:08:40Probemos con maple primero. Ya se me ha
1:08:43que esperar un segundo porque se me
1:08:46pensé que no lo iba a necesitar, así que
1:08:47no lo había echado andar.
1:08:49que tiene que partir maple aquí.
1:09:07Ya. Entonces aquí ponemos
1:09:11share
1:09:14screens.
1:09:19Ya. Entonces, aquí vamos a poner la suma
1:09:24de z a la n
1:09:29divido por n
1:09:32para n de 1 hasta infinito.
1:09:41Mm. Ya. H la dejó formal porque eh creo
1:09:46que él espera que yo le diga el valor
1:09:49absoluto de Z es menor que uno porque se
1:09:52está preocupando de la convergencia. En
1:09:54realidad, como hemos dicho, la
1:09:55convergencia no nos no nos interesa,
1:09:57pero para dejar tranquilo MPS
1:10:01de Z, digámosle que es menor que uno.
1:10:06Sea que lo puedo hacer. Okay. Y ahora
1:10:08volvemos acá. Decimos ya ahora. Ahora,
1:10:11ahora sí hágalo.
1:10:13Miren, el el la tilde que aparece con el
1:10:15Z es el es el una indicación de que eso
1:10:20tiene una una suposición asociada. Ah,
1:10:23así que pueden ignorar la z menos
1:10:25logaritmo de 1 - z. Si el menos lo meto
1:10:30dentro del logaritmo va a quar el
1:10:31logaritmo de 1/ido por 1 - z. Logaritmo
1:10:34de 1/* 1 - z. Esa es la función
1:10:38generatriz.
1:10:40exponencial
1:10:42asociada a la clase de los eh de las
1:10:46permutaciones cíclicas. H Entonces,
1:10:48vamos a volver acá.
1:10:53Vamos a decir que queremos volver a a
1:10:58mi pizarra.
1:11:17Eso sería lo ups
1:11:23logaritmo de 1/o por 1 - z.
1:11:28Esa sería la función generatriz
1:11:30exponencial de las permutaciones
1:11:34cíclicas. Okay. Ahora, si yo no hubiera
1:11:37tenido Maple a la mano o por último, si
1:11:40no le creo a Maple y quiero asegurarme
1:11:42por mí mismo de que esa es efectivamente
1:11:45la
1:11:48función generatriz correcta, lo que yo
1:11:50podría observar es lo siguiente, que e
1:11:55a ver eh
1:12:00podría observar.
1:12:05Ah, claro, puedo tomar la derivada
1:12:08y aquí, miren, yo puedo decir derivado
1:12:11de esto.
1:12:13La derivada de esto sería la derivada de
1:12:15esto, ¿no es cierto? Que sería n * z^ la
1:12:17n - 1 parido por n. Entonces, los n se
1:12:20cancelan y queda z a la n - 1.
1:12:23Pero eh
1:12:26como n es mayor o igual que 1, yo puedo
1:12:28trasladar esto y me va a quedar la
1:12:29sumatoria z a la n/ido por n, que es
1:12:311/ido por 1 - z. Ah, hagamos eso ya.
1:12:36Eh,
1:12:39¿cómo podemos demostrarlo?
1:12:42Pues la demostración de que Maple lo
1:12:43dijo no no es una demostración
1:12:45realmente.
1:12:47E yo puedo decir ya voy a derivar de A
1:12:50de Z de Corro de Z
1:12:55es la sumatoria para n mayor o igual que
1:12:571 de n * z a la n - 1/ n. Entonces estos
1:13:05se cancelan
1:13:09y esta es lo mismo que la sumatoria para
1:13:11n mayor o igual que 0 de z a la n. Eso,
1:13:16o sea, 1/ido por 1 - z.
1:13:21Entonces, si la derivada de gorro de
1:13:24zido por 1 - z, corro de z para
1:13:27obtenerlo tengo que integrar.
1:13:29Ah, y eso implica que entonces despejo
1:13:32el segorro Z integrando y me queda la
1:13:34integral de 1/o por 1- Z es logaritmo de
1:13:381/o por 1- Z.
1:13:41¿Listo? Bien, así se demostrado.
1:13:44Así que ahí yo tengo un pequeño
1:13:46repertorio de funciones generatrices
1:13:49exponenciales conocidas.
1:13:51Y ahora lo que me queda de esto, puedo
1:13:55eh
1:13:59puedo introducir eh
1:14:07a ver cómo está muy bien.
1:14:12Questo espacio. Ya. Entonces,
1:14:16maneras
1:14:18de combinar estructuras rotuladas.
1:14:38Uno es la unión disjunta.
1:14:45No,
1:14:47la unión disjunta eh
1:14:52en que yo formo una clase A con B + C,
1:14:56¿no es cierto? Donde
1:14:59B y C no tienen intersección en común.
1:15:02Otra forma de combinar es lo que se
1:15:04llama el producto rotulado,
1:15:10que se escribe a = b
1:15:15estrella
1:15:17C. ¿Ya? Eh, ¿y cómo se hace eso?
1:15:22eh
1:15:25es eh
1:15:30al concatenar
1:15:35beta en B con gama
1:15:40en C, ¿no es cierto?
1:15:43Eh, hay que
1:15:47rerrotular
1:15:52el objeto resultante
1:16:01con los rótulos
1:16:06del uno al tamaño de beta más tamaño de
1:16:11gama.
1:16:12cierto, lo que yo les había dicho antes,
1:16:15de todas las maneras posibles.
1:16:31Esto genera
1:16:36el coeficiente bien simétrico beta, com
1:16:40gama.
1:16:43Esto genera
1:16:45esa cantidad de objetos
1:16:48rotulados resultantes.
1:16:59Otra manera es la secuencia rotulada.
1:17:07La vamos a llamar
1:17:12un objeto lo construyo este por eso que
1:17:15muy raro.
1:17:17Eh, lo construyo
1:17:20eso. Eso me parece una cualquier cosa.
1:17:23Estoy tratando de hacer una S cursiva.
1:17:26Eso parece una S cursiva aplicado a un
1:17:30objeto P.
1:17:31Eso es
1:17:34el objeto vacío. Está ahí. Y también
1:17:37están todos los de la clase B.
1:17:40Y están todos los de la clase B,
1:17:43estrella B
1:17:46y todos los de la clase B, estrella B,
1:17:52estrella B, que sería como un B cub, ¿no
1:17:54es cierto?
1:17:56Así, al infinitum.
1:17:58Esa es una secuencia rotulada.
1:18:01Ya
1:18:04yo formo secuencias de objetos de de
1:18:08tipo de tipo B.
1:18:13Okay. Eh, también puedo formar los
1:18:16conjuntos
1:18:19de objetos de tipo B.
1:18:32No,
1:18:35una P cursiva
1:18:37B, todos los conjuntos que yo puedo
1:18:40formar de de objeto de tipo B. Y por
1:18:43último, los ciclos.
1:18:46Ya. A va a ser el conjunto de todos los
1:18:49ciclos de objetos de clase B.
1:18:58Y la relación que hay con la función
1:19:01generativa exponencial
1:19:05es la siguiente.
1:19:14Cuando una clase A
1:19:18cuando una clase A
1:19:21es la
1:19:23suma de dos clases,
1:19:26la función generatriz exponencial
1:19:29es la suma de las respectivas funciones
1:19:31generatrices exponenciales.
1:19:36Cuando una clase A es el producto
1:19:41rotulado esta estrella
1:19:44entre B y C, la
1:19:48función generat resultante es el
1:19:50producto simple.
1:20:00Cuando una clase A se forma como una
1:20:04secuencia
1:20:05de objetos de tipo B,
1:20:08ya,
1:20:10entonces agorro Z
1:20:14es 1/ por 1 men gorro de Z.
1:20:28Ah, eh para formar secuencias se me
1:20:31olvidó decir que eh la suposición es que
1:20:36la palabra el objeto de tamaño cero
1:20:40no pertenece a la clase B igual que
1:20:42antes.
1:20:44Así es que eso
1:20:47ahí, eh, así es que
1:20:53no pertenece a la clase B. Bien. E y
1:21:00¿qué pasa con los conjuntos? Cuando A
1:21:05es un conjunto de objetos de la clase B,
1:21:11agorro.
1:21:17No quería
1:21:19no no necesito eso. Ya. Agorro de Z
1:21:26es eh e
1:21:30elevado a p.
1:21:35Y cuando una clase A se forma como una
1:21:40permutación cíclica de objetos de la
1:21:43clase B,
1:21:45ya
1:21:47su función generatriz exponencial
1:21:51es
1:21:53el el logaritmo
1:21:57de 1 parido por 1 menor
1:22:03z.
1:22:15Okay. Bueno, eso
1:22:19no es una Bueno, todo esto está por
1:22:22demostrarse. Ah, todo eso está por
1:22:24demostrarse. Pero déjenme antes de
1:22:28concluir la clase, porque la
1:22:30demostración va a quedar para la clase
1:22:31que viene, es que
1:22:35un ejemplo de esto
1:22:40es lo siguiente.
1:22:42Eh, tenemos una identidad que me dice
1:22:45que e elevado al logaritmo de 1/- z,
1:22:51¿no es cierto? Es igual a 1/- Z.
1:22:57Okay.
1:23:01Bueno, esto que tengo aquí
1:23:06es la función generatriz exponencial de
1:23:07las permutaciones, ¿no es cierto?
1:23:14H, ¿se acuerdan? Un poquito más atrás
1:23:16vemos que que para la clase de las
1:23:19permutaciones su función generatriz era
1:23:23no las permutaciones cíclicas, las
1:23:25permutaciones comunicorrientes. Acá era
1:23:281 par por 1 men z. ¿De acuerdo? Así que
1:23:30lo que tengo a la derecha es la clase de
1:23:32las permutaciones, la función
1:23:33generatonencial de la clase de las
1:23:35permutaciones. ¿Qué es lo que tengo aquí
1:23:37a la izquierda?
1:23:39Aquí tengo
1:23:41la función genera triponencial de los
1:23:43ciclos,
1:23:46¿ya?
1:23:49Pero toda
1:23:50permutación se puede escribir como un
1:23:52conjunto de ciclos. ¿Ustedes se acuerdan
1:23:54eso de de haber sido álgebra de primer
1:23:56año? Algo así. Ah, cualquier permutación
1:23:58la puedo escribir como un conjunto de
1:24:00ciclos, porque eh de toda permutación yo
1:24:04puedo encontrar que un cierto elemento
1:24:06se va a otra posición. El que estaba ahí
1:24:08se va a otra posición, el que estaba ahí
1:24:10se va a otra posición y al final alguno
1:24:11vuelve a la posición del primero y eso
1:24:13es un ciclo. Ahora, a lo mejor eso
1:24:15cubrió toda la permutación, pero si no,
1:24:17entonces hay otro ciclo que es junto con
1:24:19este en que otro objeto se mueve acá, el
1:24:22otro se mueve acá, se mueve acá y vuelve
1:24:24primaria. Ya. Y todo y y al final, una
1:24:27vez que yo tengo identificado todos los
1:24:28ciclos,
1:24:30entonces ese conjunto de ciclos es
1:24:32equivalente a la permutación. Y lo que
1:24:35esto me está diciendo que eh si yo tengo
1:24:38todos los ciclos ahí cuya función
1:24:41generatriz exponencial es el logaritmo
1:24:43de 1/ido por 1 - z, el e elevado a eso
1:24:47ya lo tenemos aquí, el e elevado a eso
1:24:49es el conjunto, son dos conjuntos.
1:24:51Entonces, esto que tengo a la izquierda
1:24:53son todos los conjuntos de ciclos,
1:25:02pero los conjuntos de ciclo son
1:25:03equivalentes a las permutaciones.
1:25:06Toda permutación se puede escribir de
1:25:08manera única como un conjunto de ciclos,
1:25:10¿ya? Y todo conjunto de ciclos determina
1:25:12una única permutación, así que son lo
1:25:15mismo. Entonces, aquí esta identidad
1:25:16matemática que tengo aquí o algebraica,
1:25:19es eh en realidad tiene esta
1:25:21interpretación combinatorial, ¿ya? Lo
1:25:23que esto me está diciendo es que toda
1:25:24mutación se puede escribir como un
1:25:26conjunto de ciclos, lo cual es cierto.
1:25:28Ya. Sí. Con eso cerramos la clase de hoy
1:25:31y en la clase que viene vamos a partir
1:25:32demostrando estas propiedades y haciendo
1:25:35una aplicación superbonita que es eh
1:25:39resolver el problema que dejamos
1:25:40pendiente, poder calcular cuántas
1:25:44cuántos árboles generales rotulados de
1:25:47tamaño N hay. Ya, así que con eso los
1:25:51dejo ahí en suspenso
1:25:54eh hasta la clase que viene. Eso sería
1:25:58todo por hoy. Muchas gracias.