3.1: La idea de la distribución

Muchos de los problemas que resolvimos en el Capítulo 1 pueden pensarse como problemas de distribuir objetos (como trozos de fruta o pelotas de ping-pong) a los destinatarios (como los niños). Algunas de las formas de ver los problemas de conteo como problemas de distribución son algo indirectas. Por ejemplo, en el Problema 37 probablemente notaste que la cantidad de formas de repartir pelotas de\(k\) ping-pong a\(n\) los niños para que ningún niño obtenga más de una es la cantidad de formas en que podemos elegir un subconjunto\(k\) -element de un conjunto\(n\) -element. Pensamos en los niños como destinatarios y objetos que estamos distribuyendo como las mismas pelotas de ping-pong, distribuidas para que cada destinatario obtenga como máximo una pelota. Esos niños que reciben un objeto están en nuestro set. Es útil tener más de una forma de pensar en soluciones a problemas. En el caso de problemas de distribución, otro modelo popular para las distribuciones es pensar en poner bolas en cajas en lugar de distribuir objetos a los destinatarios. La repartición de objetos idénticos se modela poniendo bolas idénticas en cajas. La repartición de objetos distintos se modela poniendo bolas distintas en cajas.

3.1.1: El Camino Veinte

Cuando estamos distribuyendo objetos a destinatarios, podemos pensar que los objetos son idénticos o distintos. También podemos pensar que los destinatarios son idénticos (como en el caso de poner fruta en bolsas de plástico en la tienda de abarrotes) o distintos (como en el caso de repartir fruta a los niños). Podemos restringir las distribuciones a aquellas que dan al menos un objeto a cada destinatario, o aquellas que dan exactamente un objeto a cada destinatario, o aquellas que dan como máximo un objeto a cada destinatario, o puede que no tengamos Tabla 3.1.1: Una tabla incompleta del número de formas de distribuir\(k\) objetos a\(n\) los destinatarios, con restricciones sobre cómo se reciben los objetos tales restricciones. Si los objetos son distintos, puede ser que el orden en que se reciben los objetos sea relevante (piense en poner libros en los estantes de una estantería) o que el orden en que se reciben los objetos sea irrelevante (piense en dejar caer un puñado de dulces en la bolsa de truco o golosinas de un niño). Si ignoramos la posibilidad de que el orden en que se reciben los objetos sea importante, hemos creado problemas de\(2 \cdot 2 \cdot 4 = 16\) distribución. En los casos en que un destinatario puede recibir más de un objeto distinto, también tenemos cuatro problemas más cuando se reciben los objetos de orden importa. Así tenemos\(20\) posibles problemas de distribución.

Cuadro 3.1.1: La Vigésima Vía: Una Tabla de Problemas de Distribución
\(k\)objetos y condiciones sobre cómo se reciben	\(n\)destinatarios y modelo matemático para distribución
	Distinto	idéntico
1. Distinto sin condiciones	\(n^k\) funciones	? establecer particiones (\(≤ n\)partes)
2. Distinto Cada uno obtiene como máximo uno	\(n^{\underline{k}}\) \(k\)-elemento permutaciones	\(1\)si\(k ≤ n\); \(0\)de lo contrario
3. Distinto Cada uno obtiene al menos uno	? sobre funciones	? establecer particiones (\(n\)partes)
4. Distinto Cada uno obtiene exactamente uno	\(k! = n!\) permutaciones	\(1\)si\(k = n\); \(0\)de lo contrario
5. Distinto, asuntos de orden	? ?	? ?
6. Distinto, asuntos de orden Cada uno obtiene al menos uno	? ?	? ?
7. idéntico sin condiciones	? ?	? ?
8. idéntico Cada uno obtiene como máximo uno	\(\binom{n}{k}\) subconjuntos	\(1\)si\(k ≤ n\); \(0\)de lo contrario
9. idéntico Cada uno obtiene al menos uno	? ?	? ?
10. idéntico Cada uno obtiene exactamente uno	\(1\)si\(k = n\); \(0\)de lo contrario	\(1\)si\(k = n\); \(0\)de lo contrario

Describimos estos problemas en la Tabla 3.1.1. Dado que hay veinte posibles problemas de distribución, llamamos a la mesa la “Vigésima Vía”, adaptando la terminología sugerida por Joel Spencer para una clase más restringida de problemas de distribución. En la primera columna de la mesa, indicamos si los objetos son distintos (como personas) o idénticos (como pelotas de ping-pong) y luego damos alguna condición sobre cómo pueden recibirse los objetos. Las condiciones que consideramos son si cada destinatario obtiene como máximo un objeto, si cada destinatario obtiene al menos un objeto, si cada destinatario obtiene exactamente un objeto y si importa el orden en que se reciben los objetos. En la segunda columna, damos la solución al problema y el nombre del modelo matemático para este tipo de problema de distribución cuando los destinatarios son distintos, y en la tercera columna, damos la misma información cuando los destinatarios son idénticos. Utilizamos signos de interrogación como respuestas a problemas que aún no hemos resuelto y modelos que aún no hemos estudiado. Damos respuestas explícitas a problemas que resolvimos en el Capítulo 1 y problemas cuyas respuestas son inmediatas. El objetivo de este capítulo es desarrollar métodos que nos permitan rellenar la tabla con fórmulas o al menos cantidades que sepamos calcular, y daremos una tabla terminada al final del capítulo. Ahora justificaremos las respuestas que no son signos de interrogación y reemplazaremos algunos signos de interrogación por respuestas ya que cubrimos material relevante.

Si repartimos objetos\(k\) distintos (digamos trozos de fruta) a destinatarios\(n\) distintos (digamos hijos), estamos diciendo para cada objeto a qué destinatario va. Así, estamos definiendo una función desde el conjunto de objetos hasta los destinatarios. Vimos el siguiente teorema en Problema 13b.

Teorema\(\PageIndex{1}\)

Hay\(n^{k}\) funciones desde un conjunto\(k\) -element hasta un conjunto\(n\) -element.

Prueba

Lo probamos de una manera en el Problema 13b y de otra manera en el Problema 75. Si repartimos objetos\(k\) distintos (digamos trozos de fruta) a recipientes\(n\) indistinguibles (digamos bolsas de papel idénticas) entonces estamos dividiendo los objetos en conjuntos disjuntos; es decir, estamos formando una partición de los objetos en algún número, ciertamente no más que el número\(k\) de objetos, de partes. Posteriormente en este capítulo (y nuevamente en el siguiente capítulo) discutiremos cómo calcular el número de particiones de un\(k\) -elemento establecido en n partes. Esto explica las entradas en la fila uno de nuestra tabla.

Si repartimos objetos\(k\) distintos a\(n\) los destinatarios para que cada uno obtenga como máximo uno, aún determinamos una función, pero la función debe ser uno a uno. El número de funciones uno a uno de un conjunto\(k\) de elementos a un conjunto de\(n\) elementos es el mismo que el número de funciones uno a uno del conjunto\([k] = \{1, 2, . . . , k\}\) a un conjunto\(n\) de elementos.

En el Problema 20, probamos el siguiente teorema.

Teorema\(\PageIndex{2}\)

Si\(0 ≤ k ≤ n\), entonces el número de permutaciones\(k\) -elemento de un conjunto de\(n\) elementos es

\[n^{\underline{k}} = n(n - 1) \dotsc (n-k+1) = n!/(n-k)!.\]

Si no\(k > n\) hay funciones uno a uno de un conjunto de\(k\) elementos a un conjunto de\(n\) elementos, entonces\(n^{\underline{k}}\) definimos como cero en este caso. Observe que esto es lo que nos da el producto indicado en el mediano plazo de nuestra fórmula. Si se supone que debemos distribuir\(k\) distintos objetos a destinatarios\(n\) idénticos para que cada uno obtenga como máximo uno, no podemos hacerlo si\(k > n\), entonces hay\(0\) formas de hacerlo. Por otro lado, si\(k \leq n\), entonces no importa qué destinatario obtiene qué objeto, entonces sólo hay una manera de hacerlo. Esto explica las entradas en la fila dos de nuestra tabla.

Si distribuimos\(k\) distintos objetos a\(n\) distintos destinatarios para que cada destinatario obtenga al menos uno, entonces volvemos a contar funciones, pero esta vez funciona de un conjunto\(k\) -element a un conjunto\(n\) -element. En la actualidad no sabemos cómo calcular el número de tales funciones, pero discutiremos cómo hacerlo más adelante en este capítulo y en el siguiente capítulo. Si distribuimos objetos\(k\) idénticos a\(n\) destinatarios, nuevamente estamos simplemente particionando los objetos, pero la condición de que cada destinatario obtenga al menos uno significa que estamos particionando los objetos en\(n\) bloques exactamente. Nuevamente, discutiremos cómo calcular el número de formas de particionar un conjunto de\(k\) objetos en\(n\) bloques más adelante en este capítulo. Esto explica las entradas en la fila tres de nuestra tabla.

Si repartimos objetos\(k\) distintos a\(n\) los destinatarios para que cada uno obtenga exactamente uno, entonces\(k = n\) y la función que nos da nuestra distribución es una biyección. El número de bijecciones de un conjunto\(n\) -elemento a un conjunto\(n\) -elemento es\(n!\) por el Teorema 3.1.2. Si repartimos objetos\(k\) distintos a destinatarios\(n\) idénticos para que cada uno obtenga exactamente\(1\), entonces en este caso no importa qué destinatario obtenga qué objeto, por lo que el número de formas de hacerlo es\(1\) if\(k = n\). Si\(k \neq n\), entonces el número de tales distribuciones es cero. Esto explica las entradas en la fila cuatro de nuestra tabla.

Ahora saltamos a la fila ocho de nuestra mesa. Vimos en el Problema 37 que el número de formas de repartir pelotas de ping-pong\(k\) idénticas a\(n\) los niños es simplemente el número de subconjuntos\(k\) -elementos de un conjunto\(n\) -elemento. En Problema 39d probamos el siguiente teorema.

Teorema\(\PageIndex{3}\)

Si\(0 ≤ k ≤ n\), el número de subconjuntos\(k\) -element de un conjunto\(n\) -element viene dado por

\[\binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{n!}{k!(n-k)!}.\]

Definimos\(\binom{n}{k}\) ser\(0\) si\(k > n\), porque entonces no hay subconjuntos\(k\) -element de un conjunto\(n\) -element. Observe que esto es lo que nos da el término medio de la fórmula en el teorema. Esto explica las entradas de la fila 8 de nuestra tabla. Por ahora, saltamos por encima de la fila 9.

En la fila 10 de nuestra tabla, si estamos repartiendo objetos\(k\) idénticos a\(n\) destinatarios para que cada uno obtenga exactamente uno, no importa si los destinatarios son idénticos o no; solo hay una manera de repartir los objetos si\(k = n\) y de otra manera es imposible hacer la distribución, por lo que no hay formas de distribuir los objetos. Esto explica las entradas de la fila 10 de nuestra tabla. Varias otras filas de nuestra tabla se pueden calcular usando los métodos del Capítulo 1.

3.1.2: Funciones ordenadas

\(\righarrow \; \bullet\) Exercise \(122\)

Supongamos que deseamos colocar libros\(k\) distintos en las repisas de una estantería con\(n\) estantes. Por simplicidad, supongamos por ahora que todos los libros cabrían en cualquiera de las repisas. Además, imaginemos que una vez que terminemos de poner libros en las estanterías, los empujamos en una estantería lo más lejos posible a la izquierda, para que solo estemos pensando en cómo se sientan los libros uno relativo al otro, no en los lugares exactos donde colocamos los libros. Como los libros son distintos, podemos pensar en el primer libro, el segundo libro y así sucesivamente.

1. ¿Cuántos lugares hay donde podamos colocar el primer libro?
2. Cuando colocamos el segundo libro, si decidimos colocarlo en la estantería que ya tiene libro, ¿importa si lo colocamos a la izquierda o derecha del libro que ya está ahí?
3. ¿Cuántos lugares hay donde podamos colocar el segundo libro? (Pista).
4. Una vez que tenemos\(i − 1\) los libros colocados, si queremos colocar libro\(i\) en una estantería que ya tiene algunos libros, ¿lo está deslizando hacia la izquierda de todos los libros ya ahí diferente a colocarlo a la derecha de todos los libros ya ahí o entre dos libros ya ahí?
5. ¿De cuántas maneras podemos colocar el libro i-ésimo en la estantería? (Pista).
6. ¿De cuántas maneras podemos colocar todos los libros?

Ejercicio\(123\)

Supongamos que deseamos colocar los libros en el Problema 122e (satisfaciendo los supuestos que hicimos allí) para que cada estantería obtenga al menos un libro. Ahora bien, ¿de cuántas maneras podemos colocar los libros? (Pista).

La asignación de qué libros van a qué estantes de una estantería es simplemente una función desde los libros hasta los estantes. Pero una función no determina qué libro se encuentra a la izquierda de qué otros en la estantería, y esta información es parte de cómo se disponen los libros en las estanterías. Es decir, el orden en que los estantes reciben sus libros importa. Por lo tanto, nuestra función debe asignar una lista ordenada de libros a cada estante. Llamaremos a tal función una función ordenada. Más precisamente, una función ordenada de un conjunto\(S\) a un conjunto\(T\) es una función que asigna una lista (ordenada) de elementos de\(S\) a algunos, pero no necesariamente todos, elementos de\(T\) tal manera que cada elemento de\(S\) aparece en una y sólo una de las listas. ¹ (Observe que aunque no es la definición habitual de una función de\(S\) a\(T\), una función puede describirse como una asignación de subconjuntos de\(S\) a algunos, pero no necesariamente todos, elementos de\(T\) tal manera que cada elemento de\(S\) está en uno y sólo uno de estos subconjuntos.) Así, el número de formas de colocar los libros en la estantería es la entrada en la columna central de la fila 5 de nuestra tabla. Si además requerimos que cada estante obtenga al menos un libro, estamos discutiendo la entrada en la columna central de la fila 6 de nuestra mesa. Una función ordenada en es aquella que asigna una lista a cada elemento de\(T\).

En Problema 122e mostró que el número de funciones ordenadas de un conjunto de\(k\) elementos -a un conjunto de\(n\) elementos es\(\prod\limits^{k}_{i=1}(n+i-1)\). Este producto ocurre con la suficiente frecuencia que tiene un nombre; se llama el poder factorial\(k^{\text{th}}\) ascendente de\(n\) y se denota por\(n^{\bar{k}}\). Se lee como “\(n\)al\(k\) levantamiento”. (Esta notación se debe a Don Knuth, quien también sugirió la notación para la caída de poderes factoriales). Podemos resumir con un teorema que agrega dos fórmulas más para el número de funciones ordenadas.

Teorema\(\PageIndex{3}\)

El número de funciones ordenadas de un conjunto\(k\) -element a un conjunto\(n\) -element es

\[n^{\bar{k}} = \prod\limits^{k}_{i=1}(n+i-1) = \frac{(n+k-1)!}{(n-1)!} = (n+k-1)^{\underline{k}}\].

Las funciones ordenadas explican las entradas en la columna media de las filas 5 y 6 de nuestra tabla de problemas de distribución.

3.1.3: Multisets

En la columna central de la fila 7 de nuestra mesa, estamos pidiendo el número de formas de distribuir objetos\(k\) idénticos (digamos pelotas de ping-pong) a\(n\) distintos destinatarios (digamos niños).

\(\bullet\) Exercise \(124\)

¿De cuántas maneras podemos distribuir libros\(k\) idénticos en las repisas de una estantería con\(n\) estantes, suponiendo que cualquier estantería pueda contener todos los libros? (Pista).

\(\bullet\) Exercise \(125\)

Un multiconjunto elegido de un conjunto\(S\) puede considerarse como un subconjunto con elementos repetidos permitidos. Para determinar un multiset debemos decir cuántas veces (incluyendo, quizás, cero) cada miembro de\(S\) aparece en el multiset. El número de veces que aparece un elemento se llama su multiplicidad. Por ejemplo, si elegimos tres canicas rojas idénticas, seis canicas azules idénticas y cuatro canicas verdes idénticas, de una bolsa de canicas rojas, azules, verdes, blancas y amarillas entonces la multiplicidad de una canica roja en nuestro multiset es de tres, mientras que la multiplicidad de una canica amarilla es cero. El tamaño de un multiconjunto es la suma de las multiplicidades de sus elementos. Por ejemplo, si elegimos tres canicas rojas idénticas, seis canicas azules idénticas y cuatro canicas verdes idénticas, entonces el tamaño de nuestro multijuego de canicas es\(13\). ¿Cuál es el número de multiconjuntos de tamaño
\(k\) que se pueden elegir de un conjunto\(n\) -element? (Pista).

\(\rightarrow\) Exercise \(126\)

Tu respuesta en el problema anterior debería ser expresable como un coeficiente binomial. Dado que un coeficiente binomial cuenta subconjuntos, encuentra una biyección entre subconjuntos de algo y multiconjuntos elegidos de un conjunto\(S\). (Pista).

Ejercicio\(127\)

¿Cuántas soluciones hay en enteros no negativos a la ecuación\(x_{1} + x_{2} + · · · + x_{m} = r\), dónde\(m\) y\(r\) son constantes? (Pista).

Ejercicio\(128\)

¿De cuántas maneras podemos distribuir objetos\(k\) idénticos a\(n\) distintos destinatarios para que cada destinatario obtenga al menos\(m\)? (Pista).

Multisets explican la entrada en la columna central de la fila 7 de nuestra tabla de problemas de distribución.

3.1.4: Composiciones de números enteros

\(\cdot\) Exercise \(129\)

¿De cuántas maneras podemos poner libros\(k\) idénticos en\(n\) estantes si cada estante debe obtener al menos un libro? (Pista).

\(\cdot\) Exercise \(130\)

Una composición del entero\(k\) en\(n\) partes es una lista de enteros\(n\) positivos que se suman a\(k\). ¿Cuántas composiciones hay de un entero\(k\) en\(n\) partes? (Pista).

\(\rightarrow\) Exercise \(131\)

Tu respuesta en el Problema 130 se puede expresar como un coeficiente binomial. Esto significa que debería ser posible interpretar una composición como un subconjunto de algún conjunto. Encuentra una biyección entre composiciones de\(k\) en\(n\) partes y ciertos subconjuntos de algún conjunto. Explicar explícitamente cómo obtener la composición del subconjunto y el subconjunto de la composición. (Pista).

\(\cdot\) Exercise \(132\)

Explicar la conexión entre las composiciones de\(k\) en\(n\) partes y el problema de distribuir k objetos idénticos a\(n\) los destinatarios para que cada destinatario obtenga al menos uno.

La secuencia de problemas que acabas de completar debería explicar la entrada en la columna media de la fila 9 de nuestra tabla de problemas de distribución.

3.1.5: Permutaciones rotas y números de Lah

\(\rightarrow \; \cdot\) Exercise \(133\)

¿De cuántas maneras podemos apilar libros\(k\) distintos en cajas\(n\) idénticas para que haya una pila en cada caja? (Pista).

Podemos pensar en apilar libros en cajas idénticas como particionar los libros y luego ordenar los bloques de la partición. Esto resulta no ser una forma computacional útil de visualizar el problema porque el número de formas de ordenar los libros en las distintas pilas depende de los tamaños de las pilas y no solo del número de pilas. Sin embargo, en lugar de dividir una instalación en partes no superpuestas, podemos pensar en dividir una permutación (pensada como una lista) de nuestros\(k\) objetos en bloques\(n\) ordenados. Diremos que un conjunto de listas ordenadas de elementos de un conjunto\(S\) es una permutación rota de\(S\) si cada elemento de\(S\) está en una y sólo una de estas listas. El número de permutaciones rotas de un conjunto\(k\) -elemento con n bloques se denota por\(L(k, n)\). El número\(L(k, n)\) se llama Número Lah (esto es estándar) y, desde nuestra solución hasta el Problema 133, es igual a\(k!\binom{k-1}{n-1}n!\).

Los números de Lah son la solución a la pregunta “¿De cuántas maneras podemos distribuir\(k\) distintos objetos a destinatarios\(n\) idénticos si el orden importa y cada destinatario debe obtener al menos uno?” Así dan la entrada en la fila 6 y columna 3 de nuestra tabla. La entrada en la fila 5 y columna 3 de nuestra tabla será el número de permutaciones rotas con\(n\) partes menores o iguales. Por lo tanto, es una suma de números de Lah.

Hemos visto que las funciones ordenadas y las permutaciones rotas explican las entradas en las filas 5 y 6 de nuestra tabla.

En las dos secciones siguientes, daremos formas de computar las entradas restantes.

Notas

1. La función ordenada por frase no es estándar, porque todavía no hay un nombre estándar para el resultado de un problema de distribución ordenada.