4.2: Generación de funciones para particiones enteras

\(\bullet\) Exercise \(200\)

Si tenemos cinco centavos idénticos, cinco nickels idénticos, cinco centavos idénticos, y cinco cuartos idénticos, dar el enumerador de imágenes para las combinaciones de monedas que podemos formar y convertirlo en una función generadora para el número de formas de hacer\(k\) centavos con las monedas que tenemos. Haz lo mismo asumiendo que tenemos un suministro ilimitado de centavos, cinco centavos, diez centavos y cuartos. (Pista).

\(\bullet\) Exercise \(201\)

Recordemos que una partición de un entero\(k\) es un multiconjunto de números que se suma a\(k\). En Problema 200 encontramos la función generadora para el número de particiones de un entero en partes de tamaño\(1\),\(5\),\(10\), y\(25\). Cuando se trabaja con funciones de generación para particiones, se está convirtiendo en estándar para usar en\(q\) lugar de\(x\) como la variable en la función generadora. A partir de ahora, escriba sus respuestas a problemas que impliquen generar funciones para particiones de un entero en esta notación ¹.

1. Dar la función generadora para el número de particiones de un entero en partes de tamaño uno a diez. (Pista).
2. Dar la función generadora para el número de particiones de un entero\(k\) en partes de tamaño como máximo\(m\), donde\(m\) es fijo pero\(k\) puede variar. Observe que esta es la función generadora para particiones cuyo diagrama Young encaja en el espacio entre la línea\(x = 0\) y la línea\(x = m\) en un plano de coordenadas. (Asumimos que las casillas en el diagrama Young son una unidad por una unidad.) (Pista).

\(\bullet\) Exercise \(202\)

En Problema 201b diste la función generadora para el número de particiones de un entero en partes de tamaño como máximo\(m\). Explique por qué esta es también la función generadora para particiones de un entero en como máximo\(m\) partes. Observe que esta es la función generadora para el número de particiones cuyo diagrama Young encaja en el espacio entre la línea\(y = 0\) y la línea\(y = m\). (Pista).

\(\bullet\) Exercise \(203\)

Al estudiar particiones de enteros, es inconveniente restringirnos a particiones con como máximo\(m\) partes o particiones con tamaño máximo de pieza\(m\).

1. Dar la función generadora para el número de particiones de un entero en partes de cualquier tamaño. No olvides usar\(q\) en lugar de\(x\) como tu variable. (Pista).
2. Encuentra el coeficiente de\(q^{4}\) en esta función generadora. (Pista).
3. Encuentra el coeficiente de\(q^{5}\) en esta función generadora.
4. Esta función generadora involucra un producto infinito. Describa el proceso que usaría para expandir este producto en tantos términos de una serie de potencia como elija. (Pista).
5. Reescribe cualquier serie de potencia que aparezca en tu producto como cocientes de polinomios o como enteros divididos por polinomios.

\(\rightarrow\) Exercise \(204\)

En Problema 203b, multiplicamos infinitamente muchas series de potencia. Aquí hay dos anotaciones para productos infinitos que se ven bastante similares:

\[\prod\limits^{\infty}_{i=1}1+x+x^{2}+\dotsc+x^{i} \text{ and } \prod\limits^{\infty}_{i=1}1+x^{i}+x^{2i}+\dotsc+x^{i^{2}}.\]

Sin embargo, uno tiene sentido y otro no. Descubre cuál tiene sentido y explica por qué tiene sentido y el otro no. Si queremos darle sentido a un producto de la forma

\[\prod\limits^{\infty}_{i=1}1+p_{i}(x),\]

donde cada uno\(p_{i}(x)\) es un polinomio distinto de cero en\(x\), describir una suposición relativamente simple sobre los polinomios\(p_{i}(x)\) que harán que el producto tenga sentido. Si asumimos que los términos\(p_{i}(x)\) eran series de potencia distintas de cero, ¿hay una suposición relativamente simple que podríamos hacer sobre ellos para que el producto tenga sentido? (Describa tal condición o explique por qué cree que no podría haber una). (Pista).

\(\bullet\) Exercise \(205\)

¿Cuál es la función generadora (usando\(q\) para la variable) para el número de particiones de un entero en el que cada parte es par? (Pista).

\(\bullet\) Exercise \(206\)

¿Cuál es la función generadora (usando\(q\) como variable) para el número de particiones de un entero en partes distintas, es decir, en las que cada parte se usa como máximo una vez? (Pista).

\(\bullet\) Exercise \(207\)

Usa funciones generadoras para explicar por qué el número de particiones de un entero en el que se usa cada parte un número par de veces es igual a la función generadora para el número de particiones de un entero en el que cada parte es par. ¿Cómo se compara esto con el Problema 166? (Pista).

\(\rightarrow \; \bullet\) Exercise \(208\)

Usa el hecho de que

\[\frac{1-q^{2i}}{1-q^{i}} = 1+q^{i}\]

y la función de generación para el número de particiones de un entero en partes distintas para mostrar cómo el número de particiones de un entero\(k\) en partes distintas se relaciona con el número de particiones de un entero\(k\) en partes impares. (Pista).

Ejercicio\(209\)

Anote la función generadora para el número de formas de particionar un entero en partes de tamaño no más que\(m\), cada una usó un número impar de veces. Anote la función generadora para el número de particiones de un entero en partes de tamaño no más que\(m\), cada una usó un número par de veces. Utilice estas dos funciones generadoras para obtener una relación entre las dos secuencias para las que anotó las funciones generadoras. (Pista).

\(\rightarrow\) Exercise \(210\)

En Problema 201b y Problema 202 diste las funciones generadoras para, respectivamente, el número de particiones de\(k\) en partes la mayor de las cuales es como máximo\(m\) y para el número de particiones de\(k\) en la mayoría de\(m\) las partes. En este problema, daremos la función generadora para el número de particiones de\(k\) en la mayoría de las\(n\) partes, la mayor de las cuales es a lo sumo\(m\). Es decir, analizaremos\(\sum^{\infty}_{i=0}a_{k}q^{k}\) dónde\(a_{k}\) está el número de particiones de\(k\) en la mayoría de las\(n\) partes, la mayor de las cuales es a lo sumo\(m\). Geométricamente, es la función generadora para particiones cuyo diagrama Young encaja en un\(m\) por\(n\) rectángulo, como en Problema 168. Esta función generadora tiene análogos significativos al coeficiente binomial\(\binom{m+n}{n}\), y así se denota por\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\). Se llama a\(q\) - coeficiente binomial.

1. \(\begin{bmatrix} 4 \\ 2 \end{bmatrix}_{q} = \begin{bmatrix} 2+2 \\ 2 \end{bmatrix}_{q}\)Cómpiate. (Pista).
2. Encuentra fórmulas explícitas para\(\begin{bmatrix} n \\ 1 \end{bmatrix}_{q}\) y\(\begin{bmatrix} n \\ n-1 \end{bmatrix}_{q}\). (Pista).
3. ¿Cómo están\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\) y\(\begin{bmatrix} m+n \\ m \end{bmatrix}_{q}\) relacionados? Demuéstralo. (Tenga en cuenta que esto es lo mismo que preguntar cómo\(\begin{bmatrix} r \\ s \end{bmatrix}_{q}\) y\(\begin{bmatrix} r \\ r-s \end{bmatrix}_{q}\) están relacionados.) (Pista).
4. ¡Hasta ahora la analogía a\(\binom{m+n}{n}\) es bastante delgada! Si tuviéramos una recurrencia como la recurrencia Pascal, eso demostraría una verdadera analogía. ¿Es\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q} = \begin{bmatrix} m+n-1 \\ n-1 \end{bmatrix}_{q} + \begin{bmatrix} m+n-1 \\ n \end{bmatrix}_{q}\)?
5. Recordemos las dos operaciones que estudiamos en Problema 171
   1. La mayor parte de una partición contada por\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\) es\(m\) o es menor o igual a\(m − 1\). En el segundo caso, la partición encaja en un rectángulo que es como máximo las\(m − 1\) unidades de ancho y como máximo las\(n\) unidades de profundidad. ¿Cuál es la función generadora para particiones de este tipo? En el primer caso, ¿en qué tipo de rectángulo se asienta la partición que obtenemos al quitar la parte más grande? ¿Cuál es la función generadora de particiones que se asientan en este tipo de rectángulo? ¿Cuál es la función generadora para particiones que se asientan en este tipo de rectángulo después de eliminar una mayor parte de tamaño\(m\)? ¿Qué relación de recurrencia te da esto?
   2. ¿Qué recurrencia obtiene de la otra operación que estudiamos en Problema 171?
   3. Es muy probable que las dos recurrencias que obtuviste sean diferentes. Uno esperaría que pudieran dar diferentes valores para\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\). ¿Se puede resolver este conflicto potencial? (Pista).
6. \([n]_{q}\)Definir ser\(1+q+\dotsc +q^{n-1}\) para\(n > 0\) y\([0]_{q} = 1\). Leemos esto simplemente como\(n\) -sub-\(q\). \([n]!_{q}\)Definir ser\([n]_{q}[n-1]_{q} \dotsc [3]_{q}[2]_{q}[1]_{q}\). Demostrar eso\[\begin{bmatrix} m+n \\ n \end{bmatrix}_{q} = \frac{[m+n]!_{q}}{[m]!_{q}[n]!_{q}}.\] (Pista).
7. Ahora pensemos\(q\) como una variable que vamos a dejar acercarse a 1. Encuentra una fórmula explícita para
   1. \(\displaystyle{\lim_{q \to 1}[n]_{q}}\).
   2. \(\displaystyle{\lim_{q \to 1}[n]!_{q}}\).
   3. \(\displaystyle{\lim_{q \to 1}[n]_{q}} \begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\).
      ¿Por qué el límite en la Parte iii es igual al número de particiones (de cualquier número) con como máximo\(n\) partes todas de tamaño más\(m\)? ¿Puedes explicar bijectivamente por qué esta cantidad equivale a la fórmula que obtuviste? (Pista).
8. * ¿Qué pasa\(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\) si dejamos\(q\) acercarnos\(-1\)? (Pista).

Notas

1. La razón de este cambio en la notación se relaciona con el tema de los campos finitos en álgebra abstracta, donde\(q\) está la notación estándar para el tamaño de un campo finito. Si bien no haremos uso de esta conexión, te será más fácil leer trabajos más avanzados si te acostumbras a la notación diferente.