3.3: Particiones de números enteros

Ahora hemos completado todos nuestros problemas de distribución excepto aquellos en los que tanto los objetos como los destinatarios son idénticos. Por ejemplo, podríamos estar poniendo manzanas idénticas en bolsas de papel idénticas. En este caso, lo único que importa es cuántas bolsas obtienen una manzana (cuántos destinatarios obtienen un objeto), cuántos obtienen dos, cuántas obtienen tres, y así sucesivamente. Así, para cada bolsa, tenemos un número, y el multiconjunto de números de manzanas en las diversas bolsas es lo que determina nuestra distribución de manzanas en bolsas idénticas. Un multiconjunto de enteros positivos que se suman a\(n\) se llama partición de\(n\). Así las particiones de\(3\) son\(1+1+1\),\(1+2\) (que es lo mismo que\(2+1\)) y\(3\). El número de particiones de\(k\) se denota por\(P(k)\); en la computación de las particiones de\(3\) lo demostramos\(P(3) = 3\). Es tradicional usar letras griegas como\(\lambda\) (la letra griega\(\lambda\) se pronuncia LAMB duh) para representar particiones; podríamos escribir\(\lambda = 1, 1, 1\),\(\rho = 2, 1\) y\(\tau = 3\) para representar las tres particiones de tres. También escribimos\(\lambda = 1^{3}\) como una taquigrafía para\(\lambda = 1, 1, 1\), y escribimos\(3\) como una taquigrafía para “\(\lambda\)es una partición de tres”.

\(\circ\) Exercise \(157\)

Encuentre todas las particiones de\(4\) y encuentre todas las particiones de\(5\), con lo tanto informática\(P(4)\) y\(P(5)\).

3.3.1: El número de particiones de\(k\) en\(n\) partes

Una partición del entero\(k\) en\(n\) partes es un multiconjunto de enteros\(n\) positivos que se suman a\(k\). Utilizamos\(P(k, n)\) para denotar el número de particiones de\(k\) en\(n\) partes. Así\(P(k, n)\) es el número de formas de distribuir objetos\(k\) idénticos a destinatarios\(n\) idénticos para que cada uno obtenga al menos uno.

\(\circ\) Exercise \(158\)

Encuentra\(P(6, 3)\) encontrando todas las particiones de\(6\) en\(3\) partes. ¿Qué dice esto sobre la cantidad de formas de poner seis manzanas idénticas en tres bolsas idénticas para que cada bolsa tenga al menos una manzana?

3.3.2: Representaciones de Particiones

\(\circ\) Exercise \(159\)

¿Cuántas soluciones hay en los enteros positivos a la ecuación\(x_{1} + x_{2} + x_{3} = 7\) con\(x_{1} \geq x_{2} \geq x_{3}\)?

Ejercicio\(160\)

Explicar la relación entre particiones de\(k\) en\(n\) partes y listas\(x_{1}, x_{2},. . . , x_{n}\) de enteros positivos que se suman a\(k\) con\(x_{1} \geq x_{2} \geq . . . \geq x_{n}\). Tal representación de una partición se denomina representación de lista decreciente de la partición.

\(\circ\) Exercise \(161\)

Describir la relación entre particiones de k y listas o vectores\((x_{1}, x_{2}, . . . , x_{n})\) tales que\(x_{1}+2x_{2}+. . . kx_{k} = k\). Tal representación de una partición se denomina representación vectorial de tipo de una partición, y es típico dejar los ceros finales fuera de dicha representación; por ejemplo\((2, 1)\) representa la misma partición que\((2, 1, 0, 0)\). ¿Cuál es la representación de lista decreciente para esta partición y qué número particiona?

Ejercicio\(162\)

¿Cómo se\(k\) relaciona el número de particiones de con el número de particiones de\(k + 1\) cuya parte más pequeña es una? (Pista).

Cuando escribimos una partición como\(\lambda = \lambda_{1}, \lambda_{2}, . . . , \lambda_{n}\), es costumbre escribir la lista de\(\lambda_{i}s\) como una lista decreciente. Cuando tenemos un vector tipo\((t_{1}, t_{2}, . . . , t_{m})\) para una partición, escribimos cualquiera\(\lambda = 1^{t_{1}}2^{t_{2}} · · ·m^{t_{m}}\) o\(\lambda = m^{t_{m}}(m−1)t^{m−1} · · · 2^{t_{2}}1^{t_{1}}\). En adelante usaremos el segundo de estos. Cuando escribamos\(\lambda = \lambda^{i1}_{1}\lambda^{i2}_{2} · · · \lambda^{in}_{n}\), vamos a asumir eso\(\lambda_{i} > \lambda_{i+1}\).

3.3.3: Ferrers y diagramas jóvenes y la conjugación de una partición

La representación decreciente de la lista de particiones nos lleva a una manera práctica de visualizar particiones. Dada una lista decreciente\((\lambda_{1}, \lambda_{2}, . . . \lambda_{n})\), dibujamos una figura compuesta por filas de puntos que tiene puntos\(\lambda_{1}\) igualmente espaciados en la primera fila, puntos\(\lambda_{2}\) igualmente espaciados en la segunda fila, comenzando justo debajo del comienzo de la primera fila y así sucesivamente. Equivalentemente, en lugar de puntos, podemos usar cuadrados idénticos, dibujados de manera que un cuadrado toque cada uno a su derecha inmediata o inmediatamente debajo de él a lo largo de un borde. Ver Figura 3.3.1 para ejemplos. A la figura que dibujamos con puntos se le llama diagrama de Ferrers de la partición; a veces la figura con cuadrados también se llama diagrama de Ferrers; a veces se le llama diagrama Young. En esta etapa es irrelevante qué nombre elegimos y qué tipo de figura dibujamos; en un trabajo más avanzado los cuadrados son útiles porque podemos poner cosas como números o variables en ellos. A partir de ahora usaremos cuadrados y llamaremos a los diagramas Diagramas jóvenes.

Figura\(\PageIndex{1}\): Los diagramas de Ferrers y Young de la partición\((5,3,3,2)\). (Copyright; autor vía fuente)

\(\bullet\) Exercise \(163\)

Dibuja el diagrama Young de la partición\((4,4,3,1,1)\). Describir la relación geométrica entre el diagrama Young\((5,3,3,2)\) y el diagrama Young de\((4,4,3,1,1)\). (Pista).

\(\bullet\) Exercise \(164\)

A la partición\((\lambda_{1}, \lambda_{2}, . . . , \lambda_{n})\) se le llama el conjugado de la partición\((\rho_{1}, \rho_{2}, . . . , \rho_{m})\) si obtenemos el diagrama Young de uno del diagrama Young del otro volteando uno alrededor de la línea con pendiente\(-1\) que extiende la diagonal del cuadrado superior izquierdo. Véase la Figura 3.3.2 para un ejemplo.

Figura\(\PageIndex{2}\): Los Ferrers esquematizan la partición\((5,3,3,2)\) y su conjugado. (Copyright; autor vía fuente)

¿De qué es el conjugado\((4,4,3,1,1)\)? ¿Cómo se relaciona la mayor parte de una partición con el número de partes de su conjugado? ¿Qué le dice esto sobre el número de particiones de un entero positivo\(k\) con mayor parte\(m\)? (Pista).

\(\rightarrow\) Exercise \(165\)

Una partición se llama autoconjugada si es igual a su conjugado. Encuentre una relación entre el número de particiones autoconjugadas\(k\) y el número de particiones de\(k\) en distintas partes impares. (Pista).

Ejercicio\(166\)

Explicar la relación entre el número de particiones de\(k\) en partes pares y el número de particiones de\(k\) en partes de multiplicidad par, es decir, partes que se utilizan cada una un número par de veces como en\((3,3,3,3,2,2,1,1)\). (Pista).

\(\rightarrow\) Exercise \(167\)

Demuestre que el número de particiones de\(k\) en cuatro partes es igual al número de particiones de\(3k\) en cuatro partes de tamaño como máximo\(k − 1\) (o\(3k − 4\) en cuatro partes de tamaño como máximo\(k − 2\) o\(3k + 4\) en cuatro partes de tamaño como máximo\(k\)). (Pista).

Ejercicio\(168\)

La idea de conjugación de una partición podría definirse sin la interpretación geométrica de un diagrama de Young, pero parecería mucho menos natural sin la interpretación geométrica. Otra idea que parece mucho más natural en un contexto geométrico es ésta. Supongamos que tenemos una partición de\(k\) en\(n\) partes con mayor parte\(m\). Entonces el diagrama Young de la partición puede caber en un rectángulo que es\(m\) o más unidades de ancho (horizontalmente) y\(n\) o más unidades de profundidad. Supongamos que colocamos el diagrama Young de nuestra partición en la esquina superior izquierda de una\(m`\) unidad de ancho y\(n`\) unidad de rectángulo profundo con\(m` \geq m\) y\(n` \geq n\), como en la Figura 3.3.3.

Figura\(\PageIndex{3}\): Para complementar la partición\((5,3,3,2)\) en un\(6\) por\(5\) rectángulo: encerrarla en el rectángulo, rotar y cortar el diagrama original de Young. (Copyright; autor vía fuente)

1. ¿Por qué podemos interpretar la parte del rectángulo que no ocupa nuestro diagrama Young, girada en el plano, como el diagrama Young de otra partición? A esto se le llama el complemento de nuestra partición en el rectángulo.
2. ¿Qué entero está siendo particionado por el complemento?
3. ¿Qué condiciones\(m'\) y\(n'\) garantizan que el complemento tenga el mismo número de piezas que el original? (Pista).
4. ¿Qué condiciones\(m'\) y\(n'\) garantizan que el complemento tenga la misma mayor parte que el original? (Pista).
5. ¿Es posible que el complemento tenga tanto el mismo número de piezas como la misma mayor parte que la original?
6. Si complementamos una partición en un\(m'\) by\(n'\) box y luego complementamos esa partición en una\(m'\) por\(n'\) box nuevamente, ¿obtenemos la misma partición con la que empezamos?

\(\rightarrow\) Exercise \(169\)

Supongamos que tomamos una partición de\(k\) en\(n\) partes con mayor parte\(m\), la complementamos en el rectángulo más pequeño en el que encajará, complementamos el resultado en el rectángulo más pequeño en el que encajará, y continuamos el proceso hasta obtener la partición\(1\) de una en una parte. ¿Qué puedes decir de la partición con la que empezamos? (Pista).

Ejercicio\(170\)

Demostrar que\(P(k, n)\) es por lo menos\(\frac{1}{n!}\binom{k-1}{n-1}\). (Pista).

Con los coeficientes binomiales, con números de Stirling del segundo tipo, y con los números de Lah, pudimos encontrar una recurrencia preguntando números si eliminamos el elemento más grande de\(S\). Por lo tanto, es natural buscar una recurrencia para contar el número de particiones de\(k\) en\(n\) partes haciendo algo similar. Desafortunadamente, ya que estamos contando distribuciones en las que todos los objetos son idénticos, no hay forma de que identifiquemos un elemento más grande. Sin embargo, si pensamos geométricamente, podemos preguntar qué podríamos eliminar de un diagrama de Young para obtener un diagrama de Young. Dos formas naturales de obtener una partición de un entero menor de una partición de\(n\) serían eliminar la fila superior del diagrama Young de la partición y eliminar la columna izquierda del diagrama Young de la partición. Estas dos operaciones corresponden a eliminar la parte más grande de la partición y restar\(1\) de cada parte de la partición respectivamente. A pesar de que son simétricos con respecto a la conjugación, no son simétricos con respecto al número de partes. Así, uno podría ser mucho más útil que el otro para encontrar una recurrencia para el número de particiones de\(k\) en\(n\) partes.

\(\rightarrow \; \cdot\) Exercise \(171\)

En este problema, estudiaremos las dos operaciones y veremos cuál parece más útil para conseguir una recurrencia para\(P(k, n)\). Parte de la razón

1. ¿Cuántas partes tiene la partición restante cuando eliminamos la parte más grande (más precisamente, reducimos su multiplicidad en una) de una partición de\(k\) a\(n\) partes? (Una forma geométrica de describir esto es que eliminamos la primera fila del diagrama Young de la partición). ¿Qué puedes decir del número de partes de la partición restante si eliminamos una de cada parte? (Pista).
2. Si eliminamos la parte más grande de una partición, ¿qué podemos decir del entero que está siendo particionado por las partes restantes de la partición? Si eliminamos uno de cada parte de una partición de\(k\) en\(n\) partes, ¿qué entero está siendo particionado por las partes restantes? (Otra forma de describirlo es que eliminemos la primera columna del diagrama Young de la partición). (Pista).
3. Las dos últimas preguntas están diseñadas para hacerte pensar en cómo podemos obtener una biyección entre el conjunto de particiones de\(k\) en\(n\) partes y algún otro conjunto de particiones que son particiones de un número menor. Estas preguntas describen dos estrategias diferentes para obtener ese conjunto de particiones de un número menor o de números menores. Cada estrategia conduce a una biyección entre particiones de\(k\) en\(n\) partes y un conjunto de particiones de un número o números menores. Para cada estrategia, use las respuestas a las dos últimas preguntas para encontrar y describir este conjunto de particiones en un número menor y una biyección entre particiones de\(k\) en\(n\) partes y particiones del entero o enteros más pequeños en números apropiados de partes. (En un caso el conjunto de particiones y biyección son relativamente sencillos de describir y en el otro caso no tan fáciles). (Pista).
4. Encuentre una recurrencia (que no necesita tener solo dos términos en el lado derecho) que describa cómo calcular\(P(k, n)\) en términos del número de particiones de números enteros más pequeños en un número menor de partes. (Pista).
5. ¿Qué es\(P(k, 1)\) para un entero positivo\(k\)?
6. ¿Qué es\(P(k, k)\) para un entero positivo\(k\)?
7. Usa tu recurrencia para calcular una tabla con los valores de P (k, n) para valores de\(k\) entre\(1\) y\(7\).
8. ¿Qué te gustaría rellenar en fila\(0\) y columna\(0\) de tu tabla para que sea consistente con tu recurrencia? ¿Qué dice esto que\(P(0, 0)\) debería ser? Normalmente definimos una suma sin términos en ella como cero. ¿Eso es consistente con la forma en que la recurrencia dice que debemos definir\(P(0, 0)\)? (Pista).

Es notable que no haya una fórmula conocida para\(P(k, n)\), ni la haya para\(P(k)\). Esta sección está dedicada a desarrollar métodos para computar valores\(P(n, k)\) y encontrar propiedades de las\(P(n, k)\) que podamos probar incluso sin conocer una fórmula. Algunas secciones futuras intentarán desarrollar otros métodos.

Hemos visto que el número de particiones de\(k\) en\(n\) partes es igual al número de formas de distribuir objetos\(k\) idénticos a\(n\) los destinatarios para que cada uno reciba al menos uno. Si relajamos la condición de que cada destinatario reciba al menos uno, entonces vemos que el número de distribuciones de objetos\(k\) idénticos a\(n\) los destinatarios es\(\sum^{n}_{i=1}P(k,i)\) porque si algunos destinatarios no reciben nada, no importa qué destinatarios sean estos. Esto completa filas\(7\) y\(8\) de nuestra tabla de problemas de distribución. La tabla terminada se muestra en la Tabla 3.3.1. Cada entrada en esa tabla nos dice cómo contar algo. Hay bastantes teoremas que has probado que se resumen en la Tabla 3.3.1. ¡Merecería la pena intentar anotarlos todos! Los métodos que utilizamos para completar la Figura 3.3.1 son extensiones de los principios básicos de conteo que aprendimos en el Capítulo 1. Los capítulos restantes de este libro desarrollan tipos de herramientas más sofisticadas que nos permiten resolver tipos más sofisticados de problemas de conteo.

Cuadro 3.3.1: El número de formas de distribuir\(k\) objetos a\(n\) los destinatarios, con restricciones sobre cómo se reciben los objetos.
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos”. > La Vigésimo Vía: Una Tabla de Problemas de Distribución
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” rowspan="2">\(k\) objetos y condiciones sobre cómo se reciben	\(n\)destinatarios y modelo matemático para distribución
Distinto	idéntico
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 1. Distinto sin condiciones	\(n^k\) funciones	\(\sum_{i=1}^{k} S(n,i)\) establecer particiones (\(≤ n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 2. Distinto Cada uno obtiene como máximo uno	\(n^{\underline{k}}\) \(k\)-permutaciones de elementos	\(1\)si\(k ≤ n\); \(0\)de lo contrario
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 3. Distinto Cada uno obtiene al menos uno	\(S(k, n)n!\) sobre funciones	\(S(k, n)\) establecer particiones (\(n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 4. Distinto Cada uno obtiene exactamente uno	\(k! = n!\) permutaciones	\(1\)si\(k = n\); \(0\)de lo contrario
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 5. Distinto, asuntos de orden	\((k + n − 1)^{\underline{k}}\) funciones ordenadas	\(\sum_{i=1}^{n} L(k,i)\) permutaciones rotas (\(≤ n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 6. Distinto, asuntos de orden Cada uno obtiene al menos uno	\((k)^{\underline{n}}(k − 1)^{\underline{k−n}}\) ordenó sobre funciones	\(L(k, n) = \binom{k}{n} (k − 1)^{\underline{k−n}}\) permutaciones rotas (\(n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 7. idéntico sin condiciones	\( \binom{n+k−1}{k} \) multiconjuntos	\(\sum_{i=1}^{n} P(k, i)\) particiones numéricas (\(≤ n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 8. idéntico Cada uno obtiene como máximo uno	\( \binom{n}{k} \) subconjuntos	\(1\)si\(k ≤ n\); \(0\)de lo contrario
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 9. idéntico Cada uno obtiene al menos uno	\( \binom{k−1}{n−1} \) composiciones (\(n\)partes)	\(P(k, n)\) particiones numéricas (\(n\)partes)
\ (k\) objetos a\(n\) destinatarios, con restricciones sobre cómo se reciben los objetos.” class="lt-math-6107"> 10. idéntico Cada uno obtiene exactamente uno	\(1\)si\(k = n\); \(0\)de lo contrario	\(1\)si\(k = n\); \(0\)de lo contrario

3.3.4: Particiones en distintas partes

A menudo\(Q(k, n)\) se usa para denotar el número de particiones de\(k\) en partes distintas, es decir, partes que son diferentes entre sí.

Ejercicio\(172\)

Demostrar eso\(Q(k,n) \leq \frac{1}{n!}\binom{k-1}{n-1}\). (Pista).

\(\rightarrow\) Exercise \(173\)

Mostrar que el número de particiones de siete en tres partes es igual al número de particiones de\(10\) en tres partes distintas. (Pista).

\(\rightarrow \; \cdot\) Exercise \(174\)

Existe una relación entre\(P(k, n)\) y\(Q(m, n)\) para algún otro número\(m\). Encuentra el número\(m\) que te dé la mejor relación posible. (Pista).

\(\cdot\) Exercise \(175\)

Encontrar una recurrencia que\(Q(k, n)\) exprese como una suma de\(Q(k − n,m)\) para los valores apropiados de\(m\). (Pista).

\(\rightarrow *\) Exercise \(176\)

Mostrar que el número de particiones de\(k\) en partes distintas es igual al número de particiones de\(k\) en partes impares. (Pista).

\(\rightarrow *\) Exercise \(177\)

Euler demostró que si\(k \neq \frac{3j^{2}+j}{2}\), entonces el número de particiones de\(k\) en un número par de partes distintas es el mismo que el número de particiones de\(k\) en un número impar de partes distintas. Demuéstralo, y en el caso excepcional entérate de cómo se relacionan los dos números entre sí. (Pista).