4.1: La idea de generar funciones
- Page ID
- 112561
4.1.1: Visualización de Conteo con Imágenes
Supongamos que vas a elegir tres trozos de fruta de entre manzanas, peras y plátanos para un refrigerio. Podemos representar simbólicamente todas sus elecciones como
Aquí estamos usando una imagen de un trozo de fruta para soportar tomar un trozo de esa fruta. Así
significa tomar una manzana,
por tomar una manzana y una pera, y
por tomar dos manzanas. Se puede pensar que el signo más representa el “exclusivo o”, es decir,
significaría “Tomo una manzana o un plátano pero no ambos”. Para decir “Tomo tanto una manzana como un plátano”, escribiríamos
Podemos extender la analogía a la notación matemática condensando nuestra afirmación de que tomamos tres trozos de fruta para
En esta notación
significa tomar un multiset de tres manzanas, mientras que
significa tomar un multiset de dos manzanas y un plátano, y así sucesivamente. Lo que realmente está haciendo nuestra notación es darnos una manera conveniente de enumerar los tres multiconjuntos de elementos elegidos del conjunto
. 1
Supongamos ahora que planeamos elegir entre una y tres manzanas, entre una y dos peras, y entre una y dos plátanos. De una manera algo torpe podríamos describir nuestras selecciones de frutas como
\((\text{Formula } 1)\)
\(\bullet\) Exercise \(178\)
Usando un\(A\) in place de la imagen de una manzana, un\(P\) in place de la imagen de una pera, y un\(B\) in place de la imagen de un plátano, escriba la fórmula similar a la Fórmula 4.1 sin ningún punto para términos omitidos. (Puedes usar imágenes en lugar de letras si lo prefieres, ¡pero se vuelve tedioso bastante rápido!) Ahora expande el producto\((A+A^{2}+A^{3})(P+P^{2})(B+B^{2})\) y compara el resultado con tu fórmula.
\(\bullet\) Exercise \(179\)
Sustituye\(x\) todas\(A, P\) y\(B\) (o por las imágenes correspondientes) en la fórmula que obtuviste en Problema 178 y amplía el resultado en potencias de\(x\). Dar una interpretación del coeficiente de\(x^{n}\).
Si tuviéramos que ampliar la fórmula
\((\text{Formula } 2)\)
obtendríamos la Fórmula 4.1. Así, la Fórmula 4.1 y la Fórmula 4.2 describen cada una el número de multiconjuntos que podemos elegir del conjunto en el que aparece entre una y tres veces, y
y
cada uno aparece una o dos veces. Interpretamos la Fórmula 4.1 como la descripción de cada multiconjunto individual que podemos elegir, e interpretamos la Fórmula 4.2 como diciendo que primero decidimos cuántas manzanas tomar, y luego decidir cuántas peras tomar, y luego decidir cuántos plátanos tomar. En esta etapa, puede parecer un poco mágico que hacer álgebra ordinaria con la segunda fórmula rinda la primera, pero de hecho, podríamos definir suma y multiplicación con estas imágenes de manera más formal para poder explicar en detalle por qué funcionan las cosas. Sin embargo, dado que las imágenes son para motivar, y en realidad son difíciles de escribir en papel, no tiene mucho sentido elaborar estos detalles. Veremos una explicación en otro contexto más adelante.
4.1.2: Funciones de imagen
Como has visto, en nuestras descripciones de formas de elegir frutas, hemos tratado las imágenes de la fruta como si fueran variables. También es probable que hayas notado que es mucho más fácil hacer manipulaciones algebraicas con letras en lugar de imágenes, simplemente porque lleva mucho tiempo dibujar el mismo cuadro una y otra vez, mientras estamos acostumbrados a escribir cartas rápidamente. En la teoría de generar funciones, asociamos variables o polinomios, o incluso series de potencia con miembros de un conjunto. No existe un lenguaje estándar que describa cómo asociamos variables con miembros de un conjunto, por lo que inventaremos 2 algunos. Por una imagen de un miembro de un conjunto nos referiremos a una variable, o tal vez un producto de potencias de variables (o incluso una suma de productos de potencias de variables). Una función que asigna una imagen\(P(s)\) a cada miembro s de un conjunto se\(S\) llamará función de imagen. El enumerador de imágenes para una función de imagen\(P\) definida en un conjunto\(S\) será la suma de las imágenes de los elementos en\(S\). En símbolos podemos escribir esto convenientemente como.
\[E_{p}(S) = \sum_{s:s ∈ S}P(s).\]
Elegimos este idioma porque el enumerador de imágenes enumera, o enumera, todos los elementos de\(S\) según sus imágenes. Así, la Fórmula 4.1 es el enumerador de imágenes del conjunto de todos los multiconjuntos de frutas con entre una y tres manzanas, una y dos peras, y uno y dos plátanos.
\(\circ\) Exercise \(180\)
¿Cómo escribirías un polinomio en la variable\(A\) que dice que debes tomar entre cero y tres manzanas?
\(\bullet\) Exercise \(181\)
¿Cómo escribirías un enumerador de imágenes que diga que tomamos entre cero y tres manzanas, entre cero y tres peras, y entre cero y tres plátanos?
\(\cdot\) Exercise \(182\)
(Utilizado en el Capítulo 6.) Observe que cuando\(A^{2}\) solíamos estar por tomar dos manzanas, y\(P^{3}\) para estar por tomar tres peras, entonces usamos el producto\(A^{2}P^{3}\) para soportar tomar dos manzanas y tres peras. Así hemos elegido la imagen del par ordenado (\(2\)manzanas,\(3\) peras) para que sea producto de las imágenes de un multiset de dos manzanas y un multiset de tres peras. Mostrar que si\(S_{1}\) y\(S_{2}\) son conjuntos con las funciones de imagen P1 y P2 definidas en ellas, y si definimos la imagen de un par ordenado\((x_{1}, x_{2}) \in S_{1} \times S_{2}\) para ser\(P((x_{1}, x_{2})) = P_{1}(x_{1})P_{2}(x_{2})\), entonces el enumerador de imágenes de P en el conjunto\(S_{1} \times S_{2}\) es\(E_{P_{1}}(S_{1})E_{P_{2}}(S_{2})\). A esto lo llamamos el principio del producto para los enumeradores de imágenes.
4.1.3: Generando Funciones
\(\bullet\) Exercise \(183\)
Supongamos que vas a elegir un refrigerio de entre cero y tres manzanas, entre cero y tres peras, y entre cero y tres plátanos. Anota un polinomio en una variable de\(x\) tal manera que el coeficiente de\(x^{n}\) sea el número de formas de elegir un bocadillo con\(n\) trozos de fruta. (Pista).
\(\circ\) Exercise \(184\)
Supongamos que una manzana cuesta\(20\) centavos, un plátano cuesta\(25\) centavos y una pera cuesta\(30\) centavos. ¿A qué se debe sustituir\(A, P\), y\(B\) en Problema 181 para obtener un polinomio en el que el coeficiente de\(x^{n}\) es el número de formas de elegir una selección de fruta que cuesta\(n\) centavos? (Pista).
\(\bullet\) Exercise \(185\)
Supongamos que una manzana tiene\(40\) calorías, una pera tiene\(60\) calorías y un plátano tiene\(80\) calorías. ¿Qué debes sustituir\(A, P\), y\(B\) en Problema 181 para obtener un polinomio en el que el coeficiente de\(x^{n}\) es el número de formas de elegir una selección de fruta con un total de\(n\) calorías?
\(\bullet\) Exercise \(186\)
Vamos a elegir un subconjunto del conjunto\([n] = \{1, 2, . . . , n\}\). Supongamos\(x_{1}\) que solíamos ser la imagen de\(1\) elegir estar en nuestro subconjunto. ¿Cuál es el enumerador de imágenes para elegir\(1\) o no elegir\(1\)? Supongamos que para cada uno\(i\) entre\(1\) y\(n\),\(x_{i}\) solemos ser la imagen de\(i\) elegir estar en nuestro subconjunto. ¿Cuál es el enumerador de imágenes para elegir\(i\) o no\(i\) elegir estar en nuestro subconjunto? ¿Cuál es el enumerador de imágenes para todas las opciones posibles de subconjuntos de\([n]\)? ¿Qué debemos sustituir para\(x^{i}\) obtener un polinomio de\(x\) tal manera que el coeficiente de\(x^{k}\) sea el número de formas de elegir un subconjunto\(k\) -elemento de\(n\)? ¿Qué teorema acabamos de reprender (un caso especial de)? (Pista).
En el Problema 186 vemos que podemos pensar en el proceso de expansión del polinomio\((1+x)^{n}\) como una forma de “generar” los coeficientes binomiales\(\binom{n}{k}\) como los coeficientes de\(x_k\) en la expansión de\((1+x)^{n}\). Por ello, decimos que\((1+x)^{n}\) es la “función generadora” para los coeficientes binomiales\(\binom{n}{k}\). De manera más general, la función generadora para una secuencia\(a_{i}\), definida para\(i\) con\(0 \leq i \leq n\) es la expresión\(\sum^{n}_{i=0}a_{i}x^{i}\), y la función generadora para la secuencia\(a_{i}\) con\(i \geq 0\) es la expresión\(\sum^{\inf}_{i=0}a_{i}x^{i}\). Esta última expresión es un ejemplo de una serie de poder. En el cálculo, es importante pensar si una serie de potencias converge para determinar si representa o no una función. En un bonito giro del lenguaje, aunque usamos la función de generación de frases como el nombre de una serie power en combinatoria, no requerimos que la serie power represente realmente una función en el sentido habitual, y así no tenemos que preocuparnos por la convergencia. 3 En cambio pensamos en una serie de poder como una manera conveniente de representar los términos de una secuencia de números de interés para nosotros. La única justificación para decir que tal representación es conveniente es por la forma en que las propiedades algebraicas de las series de poder capturan algunas de las propiedades importantes de algunas secuencias que son de importancia combinatoria. El resto de este capítulo está dedicado a dar ejemplos de cómo la serie álgebra de poder refleja ideas combinatorias.
Debido a que elegimos pensar en las series de poder como cadenas de símbolos que manipulamos usando las reglas ordinarias del álgebra y elegimos ignorar cuestiones de convergencia, tenemos que evitar manipular las series de poder de una manera que nos obligaría a sumar infinitamente muchos números reales. Por ejemplo, no podemos hacer la sustitución de\(y + 1\) for\(x\) en la serie power\(\sum^{\inf}_{i=0}x^{i}\), pues para poder interpretar\(\sum^{\inf}_{i=0}(y+1)^{i}\) como una serie power tendríamos que aplicar el teorema binomial a cada uno de los\((y+1)^{i}\) términos, y luego recolectar términos similares, dándonos infinitamente muchos añadidos juntos como el coeficiente de\(y^{0}\), y de hecho infinitamente muchos números sumados para el coeficiente de cualquiera\(y^{i}\). (Por otro lado, estaría bien\(y + y^{2}\) sustituir\(x\). ¿Puedes ver por qué?)
4.1.4: Serie Power
Por ahora, la mayoría de nuestros usos de las series de poder implicarán solo álgebra simple. Dado que usamos series de potencia de una manera diferente en combinatoria que en cálculo, deberíamos revisar un poco del álgebra de las series de poder.
\(\circ\) Exercise \(187\)
En el polinomio\((a_{0} + a_{1}x + a_{2}x_{2})(b_{0} + b_{1}x + b_{2}x_{2} + b_{3}x_{3})\), ¿cuál es el coeficiente de\(x^{2}\)? ¿Cuál es el coeficiente de\(x^{4}\)? \(\circ\)
\(\circ\) Exercise \(188\)
En Problema 187 ¿por qué hay una\(b_{0}\) y una\(b_{1}\) en tu expresión para el coeficiente de\(x^{2}\) pero no hay una\(b_{0}\) o una\(b_{1}\) en tu expresión para el coeficiente de\(x^{4}\)? Cuál es el coeficiente de\(x^{4}\) in
\[(a_{0} + a_{1}x + a_{2}x_{2} + a_{3}x_{3} + a_{4}x_{4})(b_{0} + b_{1}x + b_{2}x_{2} + b_{3}x_{3} + b_{4}x_{4})?\]
Expresar este coeficiente en la forma
\[\sum\limits^{4}_{i=0} \text{something},\]
donde el algo es una expresión que necesitas averiguar. Ahora supongamos que\(a_{3} = 0, a_{4} = 0,\) y\(b_{4} = 0\). ¿A cuál es tu expresión igual después de sustituir estos valores? En particular, ¿qué tiene que ver esto con el Problema 187? (Pista).
\(\circ\) Exercise \(189\)
El punto de los Problemas 187 y 188 es que siempre y cuando estemos dispuestos a asumir\(a_{i} = 0\) por\(i > n\) y\(b_{j} = 0\) para\(j > m\), entonces hay una fórmula muy bonita para el coeficiente de xk en el producto
\[\left(\sum\limits^{n}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{m}_{j=0}b_{j}x^{j}\right).\]
Anote esta fórmula explícitamente. (Pista).
\(\bullet\) Exercise \(190\)
Suponiendo que las reglas que usas para hacer aritmética con polinomios se aplican a series de potencia, anota una fórmula para el coeficiente de\(x^{k}\) en el producto
\[\left(\sum\limits^{\infty}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{\infty}_{j=0}b_{j}x^{j}\right).\]
Utilizamos la expresión que obtuvo en el Problema 190 para definir el producto de la serie power. Es decir, definimos el producto
\[\left(\sum\limits^{ \infty }_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{ \infty }_{j=0}b_{j}x^{j}\right)\]
para ser la serie power\(\sum^{inf}_{k=0}c_{k}x^{k}\), donde\(c_{k}\) esta la expresión que encontraste en Problema 190. Dado que derivó esta expresión utilizando las reglas habituales de álgebra para polinomios, no debería sorprender que el producto de la serie power satisfaga estas reglas.
4.1.5: Principio de Producto para Generar Funciones
Cada vez que convertimos una función de imagen en una función generadora sustituyendo\(x\) o alguna potencia de\(x\) para cada imagen, el coeficiente de\(x\) tenía un significado que era significativo para nosotros. Por ejemplo, con el enumerador de imágenes para seleccionar entre cero y tres cada una de manzanas, peras y plátanos, cuando sustituimos\(x\) por cada una de nuestras imágenes, el exponente\(i\) en la potencia\(x^{i}\) es el número de trozos de fruta en la selección de frutas que nos llevó a\(x^{i}\). Después de simplificar nuestro producto recolectando juntos todos como potencias de\(x\), el coeficiente de\(x^{i}\) es el número de selecciones de frutas que utilizan\(i\) trozos de fruta. De la misma manera, si sustituimos\(x^{c}\) por una imagen, dónde\(c\) está el número de calorías en ese tipo particular de fruta, entonces el\(i\) en un\(x^{i}\) término en nuestra función generadora representa el número de calorías en una selección de frutas que dio origen\(x^{i}\), y el coeficiente de\(x^{i}\) en nuestra función generadora es el número de selecciones de frutas con\(i\) calorías. El principio de producto de los enumeradores de imágenes se traduce directamente en un principio de producto para generar funciones. No obstante, es posible dar una prueba que no se base en el principio del producto para los enumeradores.
\(\bullet\) Exercise \(191\)
Supongamos que tenemos dos conjuntos\(S_{1}\) y\(S_{2}\). Let\(v_{1}\) (\(v\)significa valor) ser una función de\(S_{1}\) a los enteros no negativos y let\(v_{2}\) ser una función de\(S_{2}\) a los enteros no negativos. Definir una nueva función\(v\) en el conjunto\(S_{1} \times S_{2}\) por\(v(x_{1}, x_{2}) = v_{1}(x_{1})+v_{2}(x_{2})\). Supongamos además que\(\sum^{\infty}_{i=0}a_{i}x^{i}\) es la función generadora para el número\(x_{1}\) de elementos\(S_{1}\) de valor\(i\), es decir, con\(v_{1}(x_{1}) = i\). Supongamos también que\(\sum^{\infty}_{i=0}b_{i}x^{i}\) es la función generadora para el número\(x_{2}\) de elementos\(S_{2}\) de valor\(j\), es decir, con\(v_{2}(x_{2}) = j\). Demostrar que el coeficiente de\(x^{k}\) in
\[\left(\sum\limits^{\infty}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{\infty}_{j=0}b_{j}x^{j}\right)\]
es el número de pares ordenados\((x_{1}, x_{2})\) en\(S_{1} \times S_{2}\) con valor total\(k\), es decir, con\(v_{1}(x_{1})+v_{2}(x_{2}) = k\). Esto se llama el principio del producto para generar funciones. (Pista).
El problema 191 puede extenderse por inducción matemática para probar nuestro próximo teorema.
Teorema\(\PageIndex{1}\): Product Principle for Generating Functions
Si\(S_{1}, S_{2}, . . . , S_{n}\) son conjuntos con una función\(v_{i}\) de valor de\(S_{i}\) a los enteros no negativos para cada uno\(i\), y\(f_{i}(x)\) es la función generadora para el número de elementos\(S_{i}\) de cada valor posible, entonces la función generadora para el número de\(n\) -tuplas de cada posible valor total es\(\prod^{n}_{i=1}f_{i}(x)\).
4.1.6: El teorema del binomio extendido y los multiconjuntos
\(\bullet\) Exercise \(192\)
Supongamos una vez más que\(i\) es un número entero entre\(1\) y\(n\).
- ¿Cuál es la función generadora en la que el coeficiente de\(x^{k}\) es uno? Esta serie es un ejemplo de lo que se llama una serie geométrica infinita. En la siguiente parte de este problema será útil interpretar el coeficiente uno como el número de multiconjuntos de tamaño\(k\) elegidos del conjunto singleton\(\{i\}\). A saber, solo hay una manera de elegir un multiset de tamaño\(\{i\}\):\(k\) elegir\(i\) exactamente las\(k\) veces.
- Expresar la función generadora en la que el coeficiente de\(x^{k}\) es el número de multiconjuntos\(k\) -elementos elegidos\([n]\) como potencia de una serie de potencias. ¿Qué le dice el Problema 125 (en el que tu respuesta podría expresarse como un coeficiente binomial) sobre lo que equivale esta función generadora? (Pista).
\(\circ\) Exercise \(193\)
¿Cuál es el producto\((1-x)\sum^{n}_{k=0}x^{k}\)? Cuál es el producto
\[(1-x)\sum\limits^{\inf}_{k=0}x^{k}?\]
\(\rightarrow \; \bullet\) Exercise \(194\)
Expresar la función generadora para el número de multiconjuntos de tamaño\(k\) elegidos\([n]\) (donde\(n\) es fijo pero\(k\) puede ser cualquier entero no negativo) como un\(1\) sobre algo relativamente simple.
\(\bullet\) Exercise \(195\)
Encuentre una fórmula para\((1+x)−n\) como una serie de potencias cuyos coeficientes involucren coeficientes binomiales. ¿Qué te dice esta fórmula sobre cómo debemos definir\(\binom{-n}{k}\) cuándo\(n\) es positivo? (Pista).
\(\bullet\) Exercise \(196\)
Si define\(\binom{-n}{k}\) de la manera que describió en Problema 195, puede anotar una versión del teorema binomial para\((x + y)^{n}\) que sea
válida tanto para valores no negativos como negativos de\(n\). Hazlo. Esto se llama el teorema del binomio extendido. Anota un caso especial con\(n\) negativo, como\(n = -3\), para ver una sorpresa interesante que sugiere por qué no usamos esta fórmula más adelante.
\(\rightarrow \; \bullet\) Exercise \(197\)
Anote la función generadora para el número de formas de distribuir piezas idénticas de dulces a tres niños para que ningún niño obtenga más de 4 piezas. Escribe esta función generadora como cociente de polinomios. Utilizando tanto el teorema del binomio extendido como el teorema binomial original, averigüe de cuántas maneras podemos repartir exactamente diez piezas. (Pista).
\(\bullet\) Exercise \(198\)
¿Cuál es la función generadora para el número de multisets elegidos de un conjunto\(n\) -element para que cada elemento aparezca al menos\(j\) veces y menos que\(m\) veces? Escribe esta función generadora como cociente de polinomios, luego como producto de un polinomio y una serie de potencias. (Pista).
\(\rightarrow\) Exercise \(199\)
Recordemos que un árbol está determinado por su conjunto de bordes. Supongamos que tienes un árbol en\(n\) vértices, digamos con vértice establecido\([n]\). Podemos usar\(x_{i}\) como la imagen de vértice\(i\) y\(x_{i}x_{j}\) como la imagen del borde\(x_{i}x_{j}\). Entonces una posible imagen del árbol\(T\) es el producto\(P(T) = \prod_{(i,j):i}\) y\(j\) son adyacentes\(x_{i}x_{j}\).
- Explica por qué también lo es la imagen de un árbol\(\prod^{n}_{i=1}x_{i}^{\text{deg}(i)}\).
- Anote los enumeradores de imágenes para árboles en dos, tres y cuatro vértices. Factorizarlos lo más completamente posible.
- Explicar por qué\(x_{1}x_{2} · · · x_{n}\) es un factor de la imagen de un árbol en\(n\) vértices.
- Anote la imagen de un árbol en cinco vértices con un vértice de grado cuatro, digamos vértice\(i\). Si un árbol sobre cinco vértices tiene un vértice de grado tres, cuáles son los grados posibles de los otros vértices. ¿Qué se puede decir de la imagen de un árbol con un vértice de grado tres? Si un árbol en cinco vértices no tiene vértices de grado tres o cuatro, ¿cuántos vértices de grado dos tiene? ¿Qué puedes decir de su imagen? Anote el enumerador de imágenes para árboles en cinco vértices.
- Encontrar una expresión polinómica (relativamente) simple para el enumerador de imágenes\(\sum_{T:T}\) es un árbol en\({}_{[n]}P(T)\). Demostrar que es correcto. (Pista).
- El enumerador para árboles por secuencia de grados es la suma sobre todos los árboles de\(x^{d_{1}}_{1}x^{d_{2}}_{2} \dotsc x^{d_{n}}_{n}\), donde\(d_{i}\) está el grado de vértice\(i\). ¿Cuál es el enumerador por secuencia de grados para árboles en el conjunto de vértices\([n]\)?
- Encuentra el número de árboles en\(n\) vértices y demuestra que tu fórmula es correcta.