Apéndice C: Funciones de generación exponencial
- Page ID
- 112640
C.1: Funciones de los indicadores
Cuando introdujimos la idea de una función generadora, dijimos que la suma formal
\(\sum_{i=0}^{n} a_ix^i\)
puede pensarse como una forma conveniente de realizar un seguimiento de la secuencia\(a_i\). Luego hicimos bastantes ejemplos que mostraron cómo las propiedades combinatorias de los arreglos contados por los coeficientes en una función generadora podrían reflejarse por las propiedades algebraicas de las propias funciones generadoras. Los monomios\(x^i\) se denominan polinomios indicadores. (Indican la posición del coeficiente\(a_i\).) Un ejemplo de una función generadora viene dado por
\((1 + x)^n = \sum_{i=0}^{\infty} \binom{n}{i} x^i \).
Así decimos que\((1+ x)^n\) es la función generadora para los coeficientes binomiales\( \binom{n}{i} \). La notación nos dice que estamos asumiendo que solo\(i\) varía en la suma de la derecha, pero que la ecuación se mantiene para cada entero fijo\(n\). Esto es implícito cuando decimos que\((1+ x)^n\) es la función generadora para\( \binom{n}{i} \), porque no hemos escrito i en ninguna parte\((1+ x)^n\), por lo que es libre de variar.
Otro ejemplo de una función generadora viene dado por
\(x^{\underline{n}} = \sum_{i=0}^{\infty} s(n, i)x^i\).
Así decimos que\(x^n\) es la función generadora para los números de Stirling del primer tipo,\(s(n, i)\). Hay una ecuación similar para los números de Stirling del segundo tipo, a saber
\(x^n = \sum_{i=0}^{\infty} S(n, i)x^{\underline{i}}\)
Sin embargo, con nuestra definición previa de funciones generadoras, esta ecuación no daría una función generadora para los números de Stirling del segundo tipo, porque no\(S(n, i)\) es el coeficiente de\(x^i\). Si estuviéramos dispuestos a considerar los poderes factoriales decrecientes\(x^i\) como polinomios indicadores, entonces podríamos decir que\(x^n\) es la función generadora para los números\(S(n, i)\) relativos a estos polinomios indicadores. Esto sugiere que tal vez diferentes tipos de polinomios indicadores van naturalmente con diferentes secuencias de números.
El teorema binomial nos da otro ejemplo más.
\(\circ\) Exercise \(371\)
Escribir\((1+x)^n\) como una suma de múltiplos de\(\dfrac{x^i}{i!}\) en lugar de como una suma de múltiplos de\(x^i\).
Este ejemplo sugiere que podríamos decir que\((1+x)^n\) es la función generadora para los poderes factoriales decrecientes\(n^{\underline{i}}\) relativos a los polinomios indicadores\(\dfrac{x^i}{i!}\). En general, una secuencia de polinomios se denomina familia de polinomios indicadores si hay un polinomio de cada grado entero no negativo en la secuencia. Aquellos familiarizados con el álgebra lineal reconocerán que esto dice que una familia de polinomios indicadores forman una base para el espacio vectorial de los polinomios. Esto significa que cada vía polinómica se puede expresar como una suma de múltiplos numéricos de polinomios indicadores de una y sólo una manera. Se podría usar el lenguaje del álgebra lineal para definir polinomios indicadores de una manera aún más general, pero una definición en tal generalidad no nos sería útil en este punto.
C.2: Funciones de Generación Exponencial
Decimos que la expresión\( \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\) es la función generadora exponencial para la secuencia\(a_i\). Es estándar usar EGF como una taquigrafía para la función de generación exponencial. En este contexto, llamamos a la función generadora\( \sum_{i=0}^{n} a_i x^i\) que originalmente estudiamos la función generadora ordinaria para la secuencia\(a_i\). Puedes ver por qué usamos el término función generadora exponencial pensando en la función generadora exponencial (EGF) para la secuencia all ones,
\[ \sum_{i=0}^{\infty} 1 \dfrac{x^i}{i!} = \sum_{i=0}^{\infty} \dfrac{x^i}{i!} = e^x,\]
que también denotamos por\(\exp(x)\). Recordemos del cálculo que la definición habitual de\(e^x\) o\(\exp(x)\) implica límites al menos implícitamente. Trabajamos en torno a eso definiendo como\(e^x\) la serie power\(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\).
\(\circ\) Exercise \(372\)
Encuentra el EGF (función generadora exponencial) para la secuencia\(a_n = 2^n\). ¿Qué dice esto sobre el EGF para el número de subconjuntos de un conjunto\(n\) -element?
\(\circ\) Exercise \(373\)
Encuentre el EGF (función de generación exponencial) para la cantidad de formas de pintar los postes de\(n\) farola que corren a lo largo del lado norte de Main Street en Anytown, EE. UU.
Ejercicio\(374\)
¿Para qué secuencia es\(\dfrac{e^x−e^{−x}}{2} = \cosh x\) el EGF (función generadora exponencial)?
\(\bullet\) Exercise \(375\)
¿Para qué secuencia es\(\ln \left( \dfrac{1}{1−x} \right)\) el EGF? (\(\ln(y)\)significa el logaritmo natural de\(y\). La gente suele escribir\(\log(y)\) en su lugar.) Pista: Piense en la definición del logaritmo como una integral, y no se preocupe en esta etapa si se aplican o no las leyes habituales del cálculo, ¡solo úselas como si lo hicieran! Luego definiremos como\(\ln(1 − x)\) la serie de poder que obtengas. a
\(\bullet\) Exercise \(376\)
¿Cuál es el EGF para el número de permutaciones de un conjunto\(n\) -element?
\(\rightarrow \; \bullet\) Exercise \(377\)
¿Cuál es el EGF para la cantidad de formas de organizar a\(n\) las personas alrededor de una mesa redonda? Trate de encontrar una función reconocible representada por el EGF. Observe que podemos pensar en esto como el EGF para el número de permutaciones en\(n\) elementos que son ciclos. (Pista).
\(\rightarrow \; \bullet\) Exercise \(378\)
¿Cuál es el EGF\(\sum_{n=0}^{\infty} p_{2n} \dfrac{x^{2n}}{(2n)!}\) para la cantidad de formas\(p_{2n}\) de emparejar a\(2n\) personas para jugar un total de partidos de\(n\) tenis (como en Problemas 12 y 44)? (Pista).
\(\circ\) Exercise \(379\)
¿Cuál es el EGF para la secuencia\(0, 1, 2, 3,...\)? Puede pensar en esto como el EFG para el número de formas de seleccionar un elemento de un conjunto de\(n\) elementos. ¿Cuál es el EGF para el número de formas de seleccionar dos elementos de un conjunto\(n\) -element?
\(\bullet\) Exercise \(380\)
¿Cuál es el EGF para la secuencia\(1, 1,..., 1,...\)? Observe que podemos pensar en esto como el EGF para el número de permutaciones de identidad en un conjunto\(n\) -elemento, que es lo mismo que el número de permutaciones de\(n\) elementos que son productos de\(1\) -ciclos, o como el EGF para el número de formas de seleccionar un conjunto\(n\) -elemento (o, si usted prefer, un conjunto vacío) de un conjunto\(n\) -element. Como habrás adivinado, hay muchas otras interpretaciones combinatorias que podríamos darle a este EGF.
\(\circ\) Exercise \(381\)
¿Cuál es el EGF para el número de formas de seleccionar\(n\) distintos elementos de un conjunto de un elemento? ¿Cuál es el EGF para el número de formas de seleccionar un número positivo\(n\) de elementos de un conjunto de elementos? Pista: Cuando obtengas la respuesta dirás “por supuesto” o “este es un problema tonto”. (Pista).
\(\bullet\) Exercise \(382\)
¿Cuál es el EGF para el número de particiones de un\(k\) -elemento establecido en exactamente un bloque? (Pista: ¿hay una partición del conjunto vacío en exactamente un bloque?)
\(\bullet\) Exercise \(383\)
¿Cuál es el EGF para la cantidad de formas de organizar\(k\) libros en una repisa (suponiendo que todos encajen)? ¿Cuál es el EGF para la cantidad de formas de organizar\(k\) libros en un número fijo\(n\) de estantes, asumiendo que todos los libros caben en cualquier estante? (Recuerde Problema 122.)
C.3: Aplicaciones a Recurrencias.
Vimos que las funciones generadoras ordinarias a menudo juegan un papel en la resolución de relaciones de recurrencia. Los encontramos más útiles en el caso del coeficiente constante. Las funciones generadoras exponenciales son útiles para resolver relaciones de recurrencia donde los coeficientes involucran funciones simples de\(n\), porque el\(n!\) en el denominador puede cancelar factores de\(n\) en el numerador.
\(\circ\) Exercise \(384\)
Considera la recurrencia\(a_n = na_{n−1}+n(n−1)\). Multiplica ambos lados por\(\dfrac{x^n}{n!}\), y suma de\(n = 2\) a\(∞\). (¿Por qué sumamos desde\(n = 2\) el infinito en lugar de\(n = 1\) o\(n = 0\)?) Dejando\(y = \sum_{i=0}^{\infty} a_ix^i\), mostrar que el lado izquierdo de la ecuación es\(y − a_0 − a_1x\). Exprese el lado derecho en términos de\(y\),\(x\), y\(e^x\). Resuelve la ecuación resultante para\(y\) y usa el resultado para obtener una ecuación para\(a_n\). (Una suma finita es aceptable en su respuesta para\(a_n\).)
\(\rightarrow \; \bullet\) Exercise \(385\)
La compañía telefónica en una ciudad tiene\(n\) suscriptores. Supongamos que una llamada telefónica involucra exactamente a dos suscriptores (es decir, no hay llamadas a fuera de la red y no hay llamadas de conferencia), y que la configuración de la red telefónica está determinada por qué pares de suscriptores están hablando. Observe que podemos pensar en una configuración de la red telefónica como una permutación cuya descomposición de ciclo consiste enteramente en un ciclo y dos ciclos, es decir, podemos pensar en una configuración como una involución en el grupo simétrico\(S_n\).
a. dar una recurrencia para el número\(c_n\) de configuraciones de la red. (Pista:\(n\) La persona está al teléfono o no.)
b. ¿Qué son\(c_0\) y\(c_1\)?
c. ¿Qué son\(c_2\) a través\(c_6\)?
\(\rightarrow \; \bullet\) Exercise \(386\)
Recordemos que un desajuste de\([n]\) es una permutación de\([n]\) que no tiene puntos fijos, o equivalentemente es una manera de repartir\(n\) sombreros a sus\(n\) diferentes dueños para que nadie obtenga el sombrero correcto. Se usa\(d_n\) para representar el número de descarrilamientos de\([n]\). Podemos pensar en el desajuste de\([n]\) como una lista de\(1\) a través\(n\) para que no\(i\) esté en el\(i^{\text{th}}\) lugar para ninguno\(n\). Así, en un desajuste, algún número\(k\) diferente de\(n\) está en posición\(n\). Considera dos casos: o\(n\) está en posición\(k\) o no lo está. Observe que en el segundo caso, si borramos posición\(n\) y reemplazamos\(n\) por\(k\), obtenemos un desajuste de\([n − 1]\). Con base en estos dos casos, encontrar una recurrencia para\(d_n\). ¿Qué es\(d_1\)? ¿Qué es\(d_2\)? ¿Qué es\(d_0\)? ¿Qué son\(d_3\) a través\(d_6\)?
C.3.1: Uso de Cálculo con Funciones Generadoras Exponenciales
\(\rightarrow \; \bullet\) Exercise \(387\)
Tu recurrencia en el Problema 385 debe ser una recurrencia de segundo orden.
a. suponiendo que el lado izquierdo es\(c_n\) y el lado derecho implica\(c_{n−1}\) y\(c_{n−2}\), decidir sobre un poder apropiado de\(x\) dividido por un factorial apropiado por el cual multiplicar ambos lados de la recurrencia. Utilizando el hecho de que la derivada de\(\dfrac{x^n}{n!}\) es\(\dfrac{x^{n−1}}{(n−1)!}\), anotar una ecuación diferencial para el EGF\(T(x) = \sum_{i=0}^{\infty} c_i \dfrac{x^i}{i!}\). Tenga en cuenta que tiene sentido\(0\) sustituir\(x\) en\(T(x)\). ¿Qué es\(T(0)\)? Resuelve tu ecuación diferencial para encontrar una ecuación para\(T(x)\).
b. Utilice su EGF para calcular una fórmula para\(c_n\). (Pista).
\(\rightarrow \; \bullet\) Exercise \(388\)
Tu recurrencia en el Problema 386 debe ser una recurrencia de segundo orden.
a. suponiendo que el lado izquierdo es dn y el lado derecho implica\(d_{n−1}\) y\(d_{n−2}\), decidir sobre un poder apropiado de\(x\) dividido por un factorial apropiado por el cual multiplicar ambos lados de la recurrencia. Utilizando el hecho de que la derivada de\(\dfrac{x^n}{n!}\) es\(\dfrac{x^{n−1}}{(n−1)!}\), anotar una ecuación diferencial para el EGF\(D(x) = \sum_{i=0}^{\infty} d_i \dfrac{x^i}{i!}\). ¿Qué es\(D(0)\)? Resuelve tu ecuación diferencial para encontrar una ecuación para\(D(x)\).
b. Usa la ecuación para la que encontraste\(D(x)\) para encontrar una ecuación\(d_n\). Compara este resultado con el que computaste por inclusión y exclusión.
C.4: El principio del producto para los EGF
Una de nuestras principales herramientas para las funciones generadoras ordinarias fue el principio del producto. Por lo tanto, es natural preguntarse si existe un principio de producto para las funciones generadoras exponenciales. En el Problema 383 probablemente encontraste que el EGF para el número de formas de organizar\(\) n libros en una estantería era exactamente el mismo que el EGF para el número de permutaciones de\([n]\), es decir,\(\dfrac{1}{1−x}\) o\((1 − x)^{−1}\). Entonces usando nuestra fórmula del Problema 122 y la función generadora para multisets, probablemente encontraste que el EGF para número de formas de organizar\(n\) libros en algún número fijo\(m\) de estanterías era\((1 − x)^{−m}\). Así, el EGF para\(m\) repisas es un producto de\(m\) copias del EGF para una repisa.
\(\circ\) Exercise \(389\)
En el Problema 373 ¿cuál hubiera sido la función generadora exponencial si hubiéramos pedido la cantidad de formas de pintar los postes con un solo color de pintura? ¿Con dos colores de pintura? ¿Cuál es la relación entre el EGF para pintar los\(n\) postes con un color de pintura y el EGF para pintar los\(n\) postes con cuatro colores de pintura? ¿Cuál es la relación entre el EGF para pintar los\(n\) postes con dos colores de pintura y el EGF para pintar los postes con cuatro colores de pintura?
En el Problema 385 probablemente encontraste que el EGF para el número de configuraciones de red con\(n\) los clientes era\(e^{\frac{x+x^2}{2}} = e^x · e^{\frac{x^2}{2}}\). En Problema 380 viste que la función generadora para el número de permutaciones en\(n\) elementos que son productos de un ciclo era\(e^x\), y en Problema 378 probablemente encontraste que el EGF para el número de parejas de tenis de\(2n\) personas, o equivalentemente, el número de permutaciones de \(2n\)objetos que son productos de\(n\) dos ciclos es\(e^{\frac{x^2}{2}}\).
\(\bullet\) Exercise \(390\)
¿Qué se puede decir de la relación entre el EGF para el número de permutaciones que son productos de dos ciclos disjuntos y de un ciclo, es decir, son involuciones, la función generadora exponencial para el número de permutaciones que son producto de dos ciclos disjuntos solamente y la función generadora para el número de permutaciones que son producto de un solo ciclo disjuntos (estas son permutaciones de identidad en su dominio)?
En el Problema 388 probablemente encontraste que el EGF para el número de permutaciones de\([n]\) que son desórdenes es\(e^{\frac{−x}{1−x}}\). Pero cada permutación es producto de desórdenes y un ciclo, porque la permutación que envía\(i\) a\(i\) es un ciclo, de manera que cuando factorizas una permutación como producto de ciclos disjuntos, los ciclos de tamaño mayor que uno se multiplican para dar un desajuste, y los elementos no movidos por la permutación son de un ciclo.
\(\bullet\) Exercise \(391\)
Si multiplicamos el EGF por desajustes por el EGF por el número de permutaciones cuyas descomposiciones cíclicas consisten únicamente en un ciclo, ¿qué EGF obtenemos? ¿para qué conjunto de objetos hemos encontrado el EGF? (Pista).
Ahora tenemos cuatro ejemplos en los que el EGF para una secuencia o un par de objetos es el producto de los EGF para los objetos individuales que componen la secuencia o par.
\(\bullet\) Exercise \(392\)
¿Cuál es el coeficiente de\(\dfrac{x^n}{n!}\) en el producto de dos EGF\( \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\) y\( \sum_{j=0}^{\infty} b_j \dfrac{x^j}{j!}\)? (Un signo de suma es apropiado en su respuesta.) (Pista).
En el caso de pintar postes de alumbrado público en el Problema 389, examinemos la relación entre el EGF para pintar postes con dos colores, el EGF para pintar los postes con tres colores, y el EGF para pintar postes con cinco colores,\(e^{5x}\). Para ser específicos, el EGF para pintar postes rojo y blanco es\(e^{2x}\) y el EGF para pintar postes azul, verde y amarillo es\(e^{3x}\). Para decidir cómo pintar postes con rojo, blanco, azul, verde y amarillo, podemos decidir qué juego de postes se va a pintar con rojo y blanco, y qué juego de postes se va a pintar con azul, verde y amarillo. Observe que el número de formas de pintar un conjunto de postes con rojo y blanco depende solo del tamaño de ese conjunto, y el número de formas de pintar un juego de postes con azul, verde y amarillo depende solo del tamaño de ese conjunto.
\(\bullet\) Exercise \(393\)
Supongamos que esa\(a_i\) es la cantidad de formas de pintar un conjunto de\(i\) postes con rojo y blanco, y\(b_j\) es el número de formas de pintar un conjunto de\(j\) postes con azul, verde y amarillo. De cuántas maneras podemos tomar un conjunto\(N\) de\(n\) postes, dividirlo en dos juegos\(I\) y\(J\) (usando\(i\) para representar el tamaño de\(I\) y\(j\) para representar el tamaño del conjunto\(J\), y permitiendo\(i\) y\(j\) variar) y pintar el polos en\(I\) rojo y blanco y los polos en\(J\) azul, verde y amarillo? (Da tu respuesta en términos de\(a_i\) y\(b_j\). No descubras fórmulas para\(a_i\) y\(b_j\) para usar en tu respuesta; ¡eso hará que sea más difícil entender el punto del problema!) ¿Cómo se relaciona esto con el Problema 392?
El problema 393 muestra que la fórmula que obtuviste para el coeficiente de\(\dfrac{x^n}{n!}\) en el producto de dos EGF es la fórmula que obtenemos dividiendo un conjunto\(N\) de postes en dos partes y pintando los polos en la primera parte con rojo y blanco y los polos en la segunda parte con azul, verde y amarillo. De manera más general, podrías interpretar tu resultado en el Problema 392 para decir que el coeficiente de\(\dfrac{x^n}{n!}\) en el producto\(\sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!} \sum_{j=0}^{\infty} b_j \dfrac{x^j}{j!}\) de dos EGF es la suma, sobre todas las formas de dividir un conjunto\(N\) de tamaño\(n\) en un par ordenado de conjuntos\(I\) disjuntos y\(J\), del producto \(a_{|I|} b_{|J|}\).
Parece haber dos características esenciales que se relacionan con el producto de funciones generadoras exponenciales. Primero, estamos considerando estructuras que consisten en un conjunto y alguna construcción matemática adicional o relación entre los elementos de ese conjunto. Por ejemplo, nuestro conjunto podría ser un conjunto de polos de luz y la construcción adicional podría ser una función de coloración definida en ese conjunto. Otros ejemplos de construcciones o relaciones matemáticas adicionales en un conjunto podrían incluir una permutación de ese conjunto; en particular, una involución o un desajuste, una partición de ese conjunto, una gráfica en ese conjunto, una gráfica conectada en ese conjunto, una disposición de los elementos de ese conjunto alrededor de un círculo, o un disposición de los elementos de ese conjunto en las repisas de una estantería. De hecho, un conjunto sin construcción o disposición adicional en él también es un ejemplo de una estructura. ¡Su construcción adicional es el conjunto vacío! Cuando una estructura consiste en el conjunto\(S\) más la construcción adicional, decimos que la estructura usa\(S\). Lo que todos los ejemplos que hemos mencionado en nuestra discusión anterior sobre las funciones generadoras exponenciales tienen en común es que el número de estructuras que utilizan un conjunto dado está determinado por el tamaño de ese conjunto. Llamaremos a una familia\(\mathcal{F}\) de estructuras una especie de estructuras en subconjuntos de un conjunto\(X\) si las estructuras se definen en subconjuntos finitos de\(X\) y si el número de estructuras en la familia que usa un conjunto finito\(S\) es finito y está determinado por el tamaño de\(S\) (es decir, si hay es una beccion entre subconjuntos\(S\) y\(T\) de\(X\), el numero de estructuras en la familia que utilizan\(S\) es igual al numero de estructuras en la familia que utilizan\(T\)). Decimos que una estructura es una\(\mathcal{F}\) -estructura si es un miembro de la familia\(\mathcal{F}\).
\(\bullet\) Exercise \(394\)
En el Problema 383, ¿por qué la familia de arreglos de juego de libros en una sola repisa (asumiendo que todos caben) es una especie?
\(\bullet\) Exercise \(395\)
En el Problema 385, ¿por qué la familia de personas realmente está haciendo llamadas telefónicas (asumiendo que nadie está llamando fuera de la red telefónica) en un momento dado, con la relación añadida de quién está llamando a quién, una especie? ¿Por qué la familia de conjuntos de personas que no están usando sus teléfonos es una especie (sin necesidad de construcción adicional)?
La segunda característica esencial de nuestros ejemplos de productos de EGF es que los productos de EGF parecen contar estructuras en pares ordenados de dos conjuntos disjuntos (o más generalmente en\(k\) -tuplas de conjuntos mutuamente disjuntos). Por ejemplo, podemos determinar un cinco colores de un conjunto\(S\) particionándolo de todas las formas posibles en dos conjuntos y coloreando el primer conjunto del par con nuestros dos primeros colores y nuestro segundo par con los tres últimos colores. O podemos dividir nuestro conjunto de todas las formas posibles en cinco partes y colorear la parte i con nuestro i-ésimo color. No tenemos que hacer lo mismo a cada parte de nuestra partición; por ejemplo, podríamos definir un desajuste por una parte y una permutación de identidad por la otra; esto define una permutación en el set que estamos particionando, y ya hemos notado que cada permutación surge de esta manera.
Nuestra interpretación combinatoria de EGF implicará asumir que el coeficiente de\(\dfrac{x^i}{i!}\) cuenta el número de estructuras en un conjunto particular de tamaño\(i\) en una especie de estructuras en subconjuntos de un conjunto\(X\). Así, para dar una interpretación del producto de dos EGF necesitamos ser capaces de pensar en pares ordenados de estructuras en conjuntos disjuntos o\(k\) -tuplas de estructuras en conjuntos disjuntos como estructuras mismas. Así, dada una estructura en un conjunto\(S\) y otra estructura en un conjunto disjunta\(T\), definimos el par ordenado de estructuras (¡que es una construcción matemática!) para ser una estructura en el set\(S ∪ T\). A esto lo llamamos una estructura de par en\(S ∪ T\). Podemos obtener muchas estructuras en un set\(S ∪ T\) de esta manera, porque se\(S ∪ T\) pueden dividir en muchos otros pares de conjuntos disjuntos. En particular, el conjunto de estructuras de par cuya primera estructura proviene\(\mathcal{F}\) y de cuyo segundo elemento proviene\(\mathcal{G}\) se denota por\(\mathcal{F} · \mathcal{G}\).
Ejercicio\(396\)
Mostrar que si\(\mathcal{F}\) y\(\mathcal{G}\) son especies de estructuras en subconjuntos de un conjunto\(X\), entonces el par de estructuras de\(\mathcal{F} \cdot \mathcal{G}\) para una especie de estructuras.
Dada una especie\(\mathcal{F}\) de estructuras, el número de estructuras que utilizan cualquier conjunto particular de tamaños\(i\) es el mismo que el número de estructuras en la familia que usa cualquier otro conjunto de tamaños\(i\). Podemos definir así la función generadora exponencial (EGF) para la familia como la serie de potencias\(\sum_{i=1}^{\infty} a_i \dfrac{x^i}{i!}\), donde\(a_i\) está el número de estructuras de las\(\mathcal{F}\) que utilizan un conjunto particular de tamaños\(i\). En Problemas 372, 373, 376, 377, 378, 380, 382, 383, 387 y 388, estábamos calculando EGF para especies de subconjuntos de algún conjunto.
Ejercicio\(397\)
Si\(\mathcal{F}\) y\(\mathcal{G}\) son especies de subconjuntos de\(X\), ¿cómo se\(\mathcal{F} · \mathcal{G}\) relaciona el EGF con los EGF para\(\mathcal{F}\) y\(\mathcal{G}\)? Demuestra que tienes razón. (Pista).
Ejercicio\(398\)
Sin dar la prueba, ¿cómo se puede calcular el EGF\(f(x)\) para el número de estructuras usando un conjunto de tamaño\(n\) en las especies\(\mathcal{F}_1 · \mathcal{F}_2 ···· · \mathcal{F}_k\) de estructuras en\(k\) -tuplas de subconjuntos\(X\) de los EGF\(f_i(x)\)\(\mathcal{F}_i\) para cada uno\(i\) de\(1\) a\(k\)? (Aquí estamos usando la extensión natural de la idea del par de estructuras a la idea de una estructura\(k\) -tupla.)
Teorema\(C.4.1\)
Si\(\mathcal{F}_1, \mathcal{F}_2,..., \mathcal{F}_n\) son especies de subconjuntos del conjunto\(X\) y\(F_i\) tiene EGF\(f_i(x)\), entonces la familia de estructuras\(k\) -tuplas\(\mathcal{F}_1 · \mathcal{F}_2 ···· · \mathcal{F}_n\) tiene EGF\(\prod_{i=1}^{n} f_i(x)\).
Llamamos al Teorema C.4.1 el principio de producto para funciones generadoras exponenciales. Damos dos corolarios; la prueba del segundo no es inmediata aunque no particularmente difícil.
Corolario\(C.4.1\)
Si\(\mathcal{F}\) es una especie de estructuras en subconjuntos de\(X\) y\(f(x0)\) es el EGF para\(\mathcal{F}\), entonces\(f(x)^k\) es el EGF para la estructura\(k\) -tuplas en\(k\) -tuplas de\(\mathcal{F}\) -estructuras usando subconjuntos disjuntos de\(X\).
Nuestro siguiente corolario utiliza la idea de una estructura\(k\) -set. Supongamos que tenemos una especie\(\mathcal{F}\) de estructuras en subconjuntos no vacíos de\(X\), es decir, una especie de estructuras que no asigna estructuras al conjunto vacío. Entonces podemos definir una nueva especie\(\mathcal{F}^{(k)}\) de estructuras, llamadas “\(k\)-establecer estructuras”, usando subconjuntos no vacíos de\(X\). Dado un entero positivo fijo\(k\), una estructura\(k\) - set en un subconjunto\(Y\) de\(X\) consiste en un conjunto\(k\) -elemento de subconjuntos disjuntos no vacíos de\(X\) cuya unión es\(Y\) y una asignación de una\(\mathcal{F}\) -estructura a cada uno de los disjuntos subconjuntos. Se trata de una especie en el conjunto de subconjuntos de\(X\); el subconjunto utilizado por una estructura\(k\) -set es la unión de los conjuntos de la estructura. Para recapitular, el conjunto de estructuras\(k\) -set en un subconjunto\(Y\) de\(X\) es el conjunto de todas las asignaciones posibles de\(\mathcal{F}\) -estructuras a conjuntos disjuntos\(k\) no vacíos cuya unión es\(Y\). (También puede pensar en las estructuras\(k\) -set como una familia de estructuras definidas en bloques de particiones de subconjuntos de\(X\) en\(k\) bloques.)
Corolario\(C.4.2\)
Si\(\mathcal{F}\) es una especie de estructuras en subconjuntos no vacíos de\(X\) y\(f(x)\) es el EGF para\(\mathcal{F}\), entonces para cada entero positivo\(k\),\(\dfrac{f(x)^k}{k!}\) es el EGF para la familia\(\mathcal{F}^{(k)}\) de estructuras\(k\) -conjunto en subconjuntos de\(X\).
Ejercicio\(399\)
Demostrar Corolario C.4.2. (Pista).
\(\bullet\) Exercise \(400\)
Utilice el principio del producto para EGF para explicar los resultados de Problemas 390 y Problema 391.
\(\bullet\) Exercise \(401\)
Utilice el principio general del producto para EGF o uno de sus corolarios para explicar la relación entre el EGF para pintar postes de farola en un solo color y el EGF para pintar postes de farola en\(4\) colores en Problemas 373 y Problema 389. Cuál es el EGF por el número\(p_n\) de formas de pintar postes de\(n\) farola con algún número fijo\(k\) de colores de pintura.
\(\bullet\) Exercise \(402\)
Utilice el principio general del producto para los EGF o uno de sus corolarios para explicar la relación entre el EGF para organizar libros en una repisa y el EGF para organizar libros en n estantes en el Problema 383.
\(\rightarrow\) Exercise \(403\)
(Opcional) Nuestro primer ejemplo de funciones de generación exponencial utilizó el teorema binomial para mostrar que el EGF para permutaciones\(k\) -elemento de un conjunto de\(n\) elementos es\((1 + x)^n\). Utilice el EGF para permutaciones\(k\) -elemento de un conjunto de un elemento y el principio del producto para probar lo mismo. Pista: Revisar la definición alternativa de una función en la Sección 3.1.2. (Pista).
Ejercicio\(404\)
¿Cuál es el EGF para el número de formas de pintar postes de\(n\) farola rojo, blanco azul, verde y amarillo, asumiendo que un número par de postes deben pintarse de verde y un número par de postes deben pintarse de amarillo? Dar una fórmula para la cantidad de formas de pintar\(n\) postes. (¡No olvides el factorial!) (Pista).
\(\rightarrow \; \bullet\) Exercise \(405\)
¿Cuál es el EGF para el número de funciones de un conjunto\(n\) -elemento a un conjunto de un elemento? (¿Puede haber alguna función del conjunto vacío a un conjunto de un elemento?) ¿Cuál es el EGF para el número\(c_n\) de funciones de un conjunto\(n\) -elemento a un conjunto de\(k\) elementos (donde\(k\) es fijo)? Usa este EGF para encontrar una expresión explícita para el número de funciones de un conjunto\(k\) -element a un conjunto\(n\) -element y compara el resultado con lo que obtuviste por inclusión y exclusión.
\(\rightarrow \; \bullet\) Exercise \(406\)
En Problema 142 Usted demostró que los Números de Campana\(B_n\) satisfacen la ecuación\(B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_{n−k}\) (o una ecuación similar para\(B_n\).) Multiplica ambos lados de esta ecuación por\(\dfrac{x^n}{n!}\) y suma desde\(n = 0\) hasta el infinito. En el lado izquierdo, tienes una derivada de un determinado EGF que podríamos llamar\(B(x)\). En el lado derecho, tienes un producto de dos EGF, uno de los cuales es\(B(x)\). ¿Cuál es el otro? ¿Qué ecuación diferencial\(B(x)\) implica esto te da? Resolver la ecuación diferencial para\(B(x)\). ¡Este es el EGF para los números de Bell!.
\(\rightarrow\) Exercise \(407\)
Demostrarlo\(n2^{n−1} = \sum_{k=1}^{n} \binom{n}{k} k\) mediante el uso de EGF. (Pista).
\(\bullet\) Exercise \(408\)
A la luz del Problema 382, ¿por qué no es el EGF para los números\(S(n, k)\) de Stirling de segundo tipo\((e^x − 1)^n\)? ¿A qué es igual en cambio?
C.5: La Fórmula Exponencial
Las funciones generadoras exponenciales resultan ser bastante útiles en el trabajo avanzado en combinatoria. Una razón es que a menudo es posible dar una interpretación combinatoria a la composición de dos funciones generadoras exponenciales. En particular, si\(f(x) = \sum_{i=0}^{n} a_i \dfrac{x^i}{i!}\) y\(g(x) = \sum_{j=1}^{\infty} b_j \dfrac{x^j}{j!}\), tiene sentido formar la composición\(f(g(x))\) porque al hacerlo necesitamos sumar solo finitamente muchos términos para encontrar el coeficiente de\(\dfrac{x^n}{n!}\) in\(f(g(x))\) ya que en el EGF\(g(x)\) la variable ficticio\(j\) comienza en\(1\). Dado que nuestro estudio de las estructuras combinatorias no ha sido lo suficientemente avanzado como para darnos aplicaciones de una fórmula general para la composición del EGF, no daremos aquí la interpretación combinatoria de esta composición. Sin embargo, hemos visto algunos ejemplos en los que se puede aplicar una composición particular. Es decir, si\(f(x) = e^x = \exp(x)\), entonces\(f(g(x)) = \exp(g(x))\) está bien definido cuándo\(b_0 = 0\). Hemos visto tres ejemplos en los que un EGF es\(e^{f (x)}\) donde\(f(x)\) está otro EGF. Hay un cuarto ejemplo en el que la función exponencial está ligeramente oculta.
\(\bullet\) Exercise \(409\)
Si\(f(x)\) es el EGF para el número de particiones de un\(n\) -set en un bloque, y\(g(x)\) es el EGF para el número total de particiones de un conjunto\(n\) -elemento, es decir, para los números Bell\(B_n\), ¿cómo se relacionan las dos funciones generadoras?
\(\bullet\) Exercise \(410\)
Dejar\(f(x)\) ser el EGF para el número de permutaciones de un conjunto\(n\) -elemento con un ciclo de tamaño uno o dos. ¿Qué es\(f(x)\)? ¿Cuál es el EGF\(g(x)\) para el número de permutaciones de un conjunto\(n\) -elemento todos cuyos ciclos tienen tamaño uno o dos, es decir, el número de involuciones en\(S_n\)? ¿Cómo se relacionan estas dos funciones generadoras exponenciales?
\(\rightarrow \; \bullet\) Exercise \(411\)
\(f(x)\)Sea el EGF para el número de permutaciones de un conjunto de\(n\) elementos -que tienen exactamente un ciclo de dos ciclos y ningún otro ciclo. \(g(x)\)Sea el EGF por el número de permutaciones que son productos de dos ciclos solamente, es decir, para emparejamientos de tenis. (Es decir, no son producto de dos ciclos y un número distinto de cero de un ciclo). ¿Qué es\(f(x)\)? ¿Qué es\(g(x)\)? ¿Cómo se relacionan éstas con las funciones de generación exponencial?
\(\bullet\) Exercise \(412\)
\(f(x)\)Sea el EGF para el número de permutaciones de un conjunto de\(n\) elementos -que tienen exactamente un ciclo. (Esto es lo mismo que el EGF por el número de formas de organizar a\(n\) las personas alrededor de una mesa redonda). \(g(x)\)Sea el EGF para el número total de permutaciones de un conjunto\(n\) -elemento. ¿Qué es\(f(x)\)? ¿Qué es\(g(x)\)? ¿Cómo están\(f(x)\) y\(g(x)\) relacionados?
Había un elemento que nuestros últimos cuatro problemas tenían en común. En cada caso, nuestro EGF\(f(x)\) implicaba el número de estructuras de cierto tipo (particiones, redes telefónicas, emparejamientos de tenis, permutaciones) que utilizaban solo un conjunto de un tipo apropiado. (Es decir, teníamos una partición con una parte, una red telefónica compuesta por una persona o dos personas conectadas entre sí, un emparejamiento de tenis de un conjunto de dos personas, o una permutación con un ciclo). Nuestro EGF\(g(x)\) era el número de estructuras del mismo “tipo” (aquí ponemos tipo entre comillas porque no planeamos definirlo formalmente) que podrían consistir en cualquier número de conjuntos del tipo apropiado. Observe que el orden de estos conjuntos era irrelevante. Por ejemplo, no ordenamos los bloques de una partición y un producto de ciclos disjuntos es el mismo sin importar el orden que usemos para anotar el producto. Así estábamos relacionando el EGF para estructuras que de alguna manera eran “bloques de construcción” con el EGF para estructuras que eran conjuntos de bloques de construcción. Por una razón que verá más adelante, es común llamar a los bloques de construcción estructuras conectadas. Observe que nuestras estructuras conectadas estaban todas basadas en conjuntos no vacíos, por lo que no teníamos estructuras conectadas cuyo valor era el conjunto vacío. Así en cada caso, si\(f(x) = \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\), tendríamos\(a_0 = 0\). La relación entre los EGF fue siempre\(g(x) = e^{f(x)}\). Ahora damos una explicación combinatoria para esta relación.
\(\bullet\) Exercise \(413\)
Supongamos que\(\mathcal{F}\) es una especie de estructuras de un conjunto\(X\) sin estructuras en el conjunto vacío. Que\(f(x)\) sea el EGF para\(\mathcal{F}\).
a.- En la serie de poder\(e^{f(x)} =1+ f(x) + \dfrac{f(x)^2}{2!} + ··· + \dfrac{f(x)^k}{k!} + ··· = \sum_{k=0}^{\infty} \dfrac{f(x)^k}{k!}\), ¿qué nos dice el Corolario C.4.2 sobre el coeficiente de\(\dfrac{x^n}{n!}\) in\(\dfrac{f (x)^k}{k!}\)?
b. ¿Cuál es el coeficiente de\(\dfrac{x^n}{n!}\) en\(e^{f (x)}\) cuenta?
En el Problema 413, probamos el siguiente teorema, que se llama la fórmula exponencial.
Teorema\(C.5.1\)
Supongamos que\(\mathcal{F}\) es una especie de estructuras en subconjuntos de un conjunto\(X\) sin estructuras en el conjunto vacío. Que\(f(x)\) sea el EGF para\(\mathcal{F}\). Entonces el coeficiente de\(\dfrac{x^n}{n!}\) in\(e^{f(x)}\) es el número de conjuntos de estructuras en conjuntos disjuntos cuya unión es un conjunto particular de tamaño\(n\).
Veamos cómo se aplica la fórmula exponencial a los ejemplos en Problemas 409, 410, 411 y 412. En el Problema 382 nuestra familia\(\mathcal{F}\) debe consistir en particiones de un bloque de subconjuntos finitos de un conjunto, digamos el conjunto de números naturales. Dado que una partición de un conjunto es un conjunto de bloques cuya unión es\(S\), una partición de un bloque cuyo bloque es\(B\) es el conjunto\(\{B\}\). Entonces, cualquier subconjunto finito no vacío de los enteros positivos es el valor de exactamente una estructura en\(\mathcal{F}\). (No hay una partición de un bloque del conjunto vacío, así que no tenemos estructuras usando el conjunto vacío.) Como mostraste en Problema 382 la función generadora para particiones con solo un bloque es\(e^{x} − 1\). Así, por la fórmula exponencial,\(\exp(e^x−1)\) es el EGF para conjuntos de subconjuntos de los enteros positivos cuyos valores son conjuntos disjuntos cuya unión es cualquier conjunto particular\(N\) de tamaño\(n\). Este conjunto de conjuntos disjuntos divide el conjunto\(N\). Así\(\exp(e^x − 1)\) es el EGF para particiones de conjuntos de tamaño\(n\). (Como escribimos nuestra descripción, es el EGF para particiones de subconjuntos\(n\) -element de los enteros positivos, pero cualquiera de dos conjuntos de\(n\) elementos tiene el mismo número de particiones.) En otras palabras,\(\exp(e^x − 1)\) es la función generadora exponencial para los números de Bell\(B_n\).
\(\bullet\) Exercise \(414\)
Explique cómo la fórmula exponencial prueba la relación que vimos en el Problema 412.
\(\bullet\) Exercise \(415\)
Explique cómo la fórmula exponencial prueba la relación que vimos en el Problema 411.
\(\bullet\) Exercise \(416\)
Explique cómo la fórmula exponencial prueba la relación que vimos en el Problema 410.
\(\bullet\) Exercise \(417\)
En Problema 373 vimos que la función generadora para el número de formas de utilizar cinco colores de pintura para pintar postes de\(n\) luz a lo largo del lado norte de Main Street en Anytown era\(e^{4x}\). Debemos esperar una explicación de este EGF usando la fórmula exponencial. \(\mathcal{F}\)Sea la familia de todos los conjuntos de polos de luz de un elemento con la construcción adicional de un par ordenado que consiste en un poste de luz y un color. Así, un polo de luz dado ocurre en cinco pares ordenados. No pongas estructuras en ningún otro conjunto finito. Demostrar que se trata de una especie de estructuras en los subconjuntos finitos de los enteros positivos. ¿Para qué sirve la función generadora\(f(x)\) exponencial\(\mathcal{F}\)? Suponiendo que no hay límite superior en el número de polos de luz, ¿qué subconjuntos de\(S\) nos dice la fórmula exponencial se cuentan por el coeficiente de\(x^n\) in\(e^{f (x)}\)? ¿Cómo se relacionan los conjuntos que se están contando con las formas de pintar postes de luz?
Una de las aplicaciones más espectaculares de la fórmula exponencial es también la razón por la que, cuando consideramos una estructura combinatoria como un conjunto de estructuras de bloques de construcción, llamamos a las estructuras de bloques de construcción conectadas. En el capítulo 2, presentamos la idea de una gráfica conectada y en Problema 104 vimos ejemplos de gráficas que estaban conectadas y no conectadas. Un subconjunto C del conjunto de vértices de una gráfica se denomina componente conectado de la gráfica si
- cada vértice en\(C\) está conectado a cada otro vértice en ese conjunto por un paseo cuyos vértices se encuentran en\(C\), y
- ningún otro vértice en la gráfica está conectado por un paseo a ningún vértice en\(C\).
En el Problema 241, mostramos que cada componente conectado de una gráfica consiste en un vértice y todos los vértices conectados a él por paseos en la gráfica.
\(\bullet\) Exercise \(418\)
Demuestre que cada vértice de una gráfica se encuentra en uno y solo un componente conectado de una gráfica. (Observe que esto muestra que los componentes conectados de una gráfica forman una partición del conjunto de vértices de la gráfica).
\(\bullet\) Exercise \(419\)
Explique por qué ningún borde de la gráfica conecta dos vértices en diferentes componentes conectados.
\(\bullet\) Exercise \(420\)
Explique por qué es que si\(C\) es un componente conectado de una gráfica y\(E′\) es el conjunto de todos los bordes de la gráfica que conectan vértices en\(C\), entonces la gráfica con conjunto de vértices\(C\) y conjunto de bordes\(E′\) es una gráfica conectada. Llamamos a esta gráfica una gráfica de componentes conectada de la gráfica original.
La última secuencia de problemas muestra que podemos pensar en cualquier gráfica como el conjunto de sus gráficas de componentes conectados. (Una vez que los conocemos, conocemos todos los vértices y todos los bordes de la gráfica). Observe que un gráfico está conectado si y solo si tiene exactamente un componente conectado. Dado que los componentes conectados forman una partición del conjunto de vértices de una gráfica, la fórmula exponencial relacionará el EGF para el número de gráficas conectadas en\(n\) vértices con el EGF para el número de gráficas (conectadas o no) en\(n\) vértices. Sin embargo debido a que podemos dibujar tantos bordes como queramos entre dos vértices de una gráfica, hay infinitamente muchas gráficas en\(n\) vértices, y así el problema de contarlos no es interesante. Podemos hacerlo interesante considerando gráficas simples, es decir, gráficas en las que cada borde tiene dos extremos distintos y no hay dos aristas que conecten los mismos dos vértices. Es porque las gráficas conectadas forman los bloques de construcción para ver todas las gráficas como conjuntos de componentes conectados que nos referimos a los bloques de construcción para estructuras contadas por el EGF en la fórmula exponencial como estructuras conectadas.
\(\rightarrow \; \bullet\) Exercise \(421\)
Supongamos que\(f(x) = \sum_{n=0}^{\infty} c_n \dfrac{x^n}{n!}\) es la función generadora exponencial para el número de gráficas simples conectadas en\(n\) vértices y\(g(x) = \sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}\) es la función generadora exponencial para el número de gráficas simples en\(i\) vértices. A partir de este punto, cualquier uso de la palabra grafo significa gráfica simple.
a. ¿Es\(f(x) = e^{g(x)}\), es\(f(x) = e^{g(x)−1}\), es\(g(x) = e^{f(x)−1}\) o es\(g(x) = e^{f(x)}\)? (Pista).
b. Uno de\(a_i\) y se\(c_n\) puede calcular reconociendo que un gráfico simple en un conjunto de vértices\(V\) está completamente determinado por su conjunto de bordes y su conjunto de bordes es un subconjunto del conjunto de dos subconjuntos de elementos de\(V\). Averiguar cuál es y cómplalo. (Pista).
c. Escribir\(g(x)\) en términos del logaritmo natural de\(f(x)\) o\(f(x)\) en términos del logaritmo natural de g (x).
d. escribir\(\log(1 + y)\) como una serie de potencia en\(y\). (Pista).
e. ¿Por qué el coeficiente de\(\dfrac{x^0}{0!}\) en\(g(x)\) igual a uno? Escribe\(f(x)\) como una serie de poder en\(g(x) − 1\).
f. Ahora puede usar las partes anteriores del problema para encontrar una fórmula\(c_n\) que implique sumar todas las particiones del entero\(n\). (No es la fórmula más simple del mundo, y no es la fórmula más fácil del mundo de entender, pero no obstante es una fórmula con la que uno podría hacer cálculos!) Encuentra tal fórmula. (Pista).
El punto al último problema es que podemos usar la fórmula exponencial a la inversa para decir que si\(g(x)\) es la función generadora para el número de estructuras conectadas (no vacías) de tamaño\(n\) en una familia dada de estructuras combinatorias y\(f(x)\) es la función generadora para todas las estructuras de tamaño\(n\) en esa familia, entonces no sólo lo es\(f(x) = e^{g(x)}\), sino\(g(x) = \ln(f(x))\) también. Además, si por casualidad tenemos una fórmula para los coeficientes de\(f(x)\) o los coeficientes de\(g(x)\), ¡podemos obtener una fórmula para los coeficientes del otro!
C.6: Problemas suplementarios
1. Utilice principio de producto para EGF y la idea de colorear un conjunto en dos colores para probar la fórmula\(e^x · e^x = e^{2x}\).
2. Encuentre el EGF para el número de funciones ordenadas de un conjunto de\(k\) elementos -a un conjunto de\(n\) elementos.
3. Encuentra el EGF para conocer el número de formas de enhebrar cuentas\(n\) distintas en un collar.
4. Encuentre la función de generación exponencial para el número de permutaciones rotas de un\(k\) elemento -conjunto en\(n\) partes.
5. Encuentre el EGF para el número total de permutaciones rotas de un conjunto\(k\) de elementos.
6. Encuentra el EGF para el número de gráficas sobre\(n\) vértices en los que cada vértice tiene grado\(2\).
7. Recordemos que un ciclo de una permutación no puede estar vacío.
a. ¿Cuál es la función generadora para el número de ciclos en un número par de elementos (es decir, permutaciones de un número par\(n\) de elementos que forman un n-ciclo)? Tu respuesta no debe tener un signo de suma en ella. Pista: Si\(y = \sum_{i=0}^{\infty} \dfrac{x^{2i}}{2i}\), ¿cuál es la derivada\(y\)?
b. ¿Cuál es la función generadora del número de permutaciones en\(n\) elementos que son producto de ciclos pares?
c. ¿Cuál es la función generadora para el número de ciclos en un número impar de elementos?
d. ¿Cuál es la función generadora para el número de permutaciones en\(n\) elementos que son producto de ciclos impares?
e. ¿Cómo se relacionan las funciones generadoras en las partes b y d de este problema con la función generadora para todas las permutaciones en\(n\) los elementos?