3.2: Particiones y números de Stirling

Hemos visto como el número de particiones de un conjunto de\(k\) objetos en\(n\) bloques corresponde a la distribución de objetos\(k\) distintos a destinatarios\(n\) idénticos. Si bien existe una fórmula que eventualmente aprenderemos para este número, requiere más maquinaria de la que ahora tenemos disponible. Sin embargo, existe un buen método para calcular este número que es similar a la ecuación de Pascal. Ahora que hemos estudiado las recurrencias en una variable, señalaremos que la ecuación de Pascal es de hecho una recurrencia en dos variables; es decir, nos permite calcular\(\binom{n}{k}\) en términos de valores de\(\binom{m}{i}\) en los cuales una\(m < n\)\(i < k\) o ambas. Fue el hecho de que tuvimos tal recurrencia y conocimos\(\binom{n}{0}\) y\(\binom{n}{n}\) eso nos permitió crear el triángulo de Pascal.

3.2.1: Números de Stirling del Segundo Tipo

Usamos la notación\(S(k, n)\) para representar el número de particiones de un conjunto de\(k\) elementos con\(n\) bloques. Por razones históricas,\(S(k, n)\) se llama un Número Stirling del segundo tipo.

\(\rightarrow \; \bullet\) Exercise \(134\)

En una partición del conjunto [\(k\)], el número\(k\) está o bien en un bloque por sí mismo, o no lo está. ¿Cómo se compara el número de particiones de [\(k\)] con\(n\) partes en las que\(k\) se encuentra en un bloque con otros elementos de [\(k\)] con el número de particiones de [\(k − 1\)] en\(n\) bloques? Encuentra una recurrencia de dos variables para\(S(k, n)\), válida para\(k\) y\(n\) mayor de una. (Pista).

Ejercicio\(135\)

¿Qué es\(S(k, 1)\)? ¿Qué es\(S(k, k)\)? Crear una tabla de valores de\(S(k, n)\) para\(k\) entre\(1\) y\(5\) y\(n\) entre\(1\) y\(k\). Esta tabla a veces se llama Triángulo de Stirling (del segundo tipo). ¿Cómo definirías\(S(k, 0)\) y\(S(0, n)\)? (Tenga en cuenta que la pregunta anterior incluye\(S(0, 0)\).) ¿Cómo definirías\(S(k, n)\) para\(n > k\)? Ahora bien, ¿para qué valores de\(k\) y\(n\) es válida tu recurrencia de dos variables?

Ejercicio\(136\)

Extiende el triángulo de Stirling lo suficiente como para permitirte responder a la siguiente pregunta y responderla. (No llene las filas hasta el final; el trabajo se vuelve bastante tedioso si lo haces. Solo rellena lo que necesites para responder a esta pregunta.) Un servicio de catering prepara tres almuerzos de bolsa para excursionistas. El servicio de catering tiene nueve sándwiches diferentes. ¿De cuántas maneras se pueden distribuir estos nueve sándwiches en tres bolsas de almuerzo idénticas para que cada bolsa obtenga al menos una?

Ejercicio\(137\)

La pregunta del Problema 136 sugiere naturalmente una pregunta más realista; ¿de cuántas maneras puede el proveedor distribuir los nueve sándwiches en tres bolsas idénticas para que cada bolsa obtenga exactamente tres? Responde a esta pregunta. (Pista).

\(\cdot\) Exercise \(138\)

¿Qué es\(S(k, k − 1)\)? (Pista).

\(\bullet\) Exercise \(139\)

¿De cuántas maneras podemos particionar elementos\(k\) (distintos) en\(n\) bloques para que tengamos\(k_i\) bloques de tamaño\(i\) para cada uno\(i\)? (Observe que\(\sum^{k}_{i-1}k_{i} = n\) y\(\sum^{k}_{i-1}ik_{i} = k\).) La secuencia\(k_{1}, k_{2}, . . . , k_{n}\) se denomina vector tipo de la partición. (Pista).

\(+\) Exercise \(140\)

Describe cómo calcular\(S(n, k)\) en términos de cantidades dadas por la fórmula que encontraste en Problema 139.

\(\rightarrow\) Exercise \(141\)

Encuentra una recurrencia para los números de Lah\(L(k, n)\) similar a la del Problema 134. (Pista).

\(\cdot\) Exercise \(142\)

(Relevante en el Apéndice C.) El número total de particiones de un conjunto\(k\) -element se denota por\(B(k)\) y se llama el número\(k\) -ésimo Bell. Así\(B(1) = 1\) y\(B(2) = 2\).

1. Mostrar, al exhibir explícitamente las particiones, eso\(B(3) = 5\).
2. Encuentra una recurrencia que se exprese\(B(k)\) en términos de\(B(n)\) for\(n < k\) y demuestre que tu fórmula es correcta de tantas maneras como puedas. (Pista).
3. Encuentra\(B(k)\) para\(k = 4, 5, 6\).

3.2.2: Números de Stirling y funciones de encendido

\(\circ\) Exercise \(143\)

Dada una función\(f\) de un conjunto\(k\) -element\(K\) a un conjunto\(n\) -element, podemos definir una partición de\(K\) poniendo\(x\) y\(y\) en el mismo bloque de la partición si y solo si\(f(x) = f(y)\). ¿Cuántos bloques tiene la partición si\(f\) está en? ¿Cómo se relaciona el número de funciones de un conjunto\(k\) -element a un conjunto\(n\) -element con un número de Stirling? Sea lo más preciso posible en su respuesta. (Pista).

\(\rightarrow\) Exercise \(144\)

¿Cuántos árboles etiquetados en\(n\) vértices tienen exactamente\(3\) vértices de grado uno? Obsérvese que este problema ha aparecido antes en el Capítulo 2. (Pista).

\(\bullet\) Exercise \(145\)

Cada función de un conjunto de\(k\) elementos\(K\) -a un conjunto de\(n\) elementos\(N\) -es una función de\(K\) a algún subconjunto de\(N\). Si\(J\) es un subconjunto\(N\) de tamaño\(j\), sabes cómo calcular el número de funciones a las que se mapea\(J\) en términos de números de Stirling. Supongamos que agrega el número de funciones que se\(J\) mapean sobre todos los subconjuntos posibles\(J\) de\(N\). ¿Qué valor simple debe igualar esta suma? Escribe la ecuación que esto te da. (Pista).

\(\circ\) Exercise \(146\)

¿De cuántas maneras se pueden colocar los sándwiches del Problema 136 en tres bolsas distintas para que cada bolsa obtenga al menos una?

\(\circ\) Exercise \(147\)

¿De cuántas maneras se pueden colocar los sándwiches del Problema 137 en bolsas distintas para que cada bolsa obtenga exactamente tres?

\(\bullet\) Exercise \(148\)

etiquetas distintas (numeradas\(1\) a través de\(n\)) para que la etiqueta\(i\) se use\(j_i\) veces? (Si pensamos en las etiquetas como\(y_{1}, y_{2}, . . . , y_{n}\), entonces podemos reformular esta pregunta de la siguiente manera. ¿Cuántas funciones hay de un conjunto\(k\) -elemento\(K\) a un conjunto para\(N = \{y_{1}, y_{2}, . . . ,y_{n}\}\) que cada una\(y_{i}\) sea la imagen de\(j_{i}\) elementos de\(K\)?) Este número se denomina coeficiente multinomial y se denota por\(\binom{k}{j_{1},j_{2}, . . . ,j_{n}}\). (Pista).

Ejercicio\(149\)

Explicar cómo calcular el número de funciones de un conjunto\(k\) -elemento\(K\) a un conjunto de\(n\) elementos\(N\) mediante el uso de coeficientes multinomiales. (Pista).

Ejercicio\(150\)

Explicar cómo calcular el número de funciones de un conjunto\(k\) -elemento\(K\) a un conjunto de\(n\) elementos\(N\) mediante el uso de coeficientes multinomiales. (Pista).

\(\bullet\) Exercise \(151\)

¿Qué tienen que ver los coeficientes multinomiales con la expansión del\(k^{\text{th}}\) poder de una multinomial\(x_{1} + x_{2} + · · · + x_{n}\)? A este resultado se le llama teorema multinomial. (Pista).

3.2.3: Números y bases de Stirling para polinomios

\(\cdot\) Exercise \(152\)

1. Encontrar una manera de expresarse\(n^{k}\) en términos de\(k^{\underline{j}}\) para valores apropiados\(j\). Puedes usar números de Stirling si te ayudan. (Pista).
2. Observe que tiene\(x^{\underline{j}}\) sentido para una variable numérica\(x\) (que podría oscilar sobre los números racionales, los números reales, o incluso los números complejos en lugar de solo los enteros no negativos, como estamos suponiendo implícitamente que\(n\) lo hace), al igual que\(x^{j}\) lo hace. Encuentra una manera de expresar el poder\(x^{k}\) en términos de los polinomios\(x^{\underline{j}}\) para valores apropiados de\(j\) y explica por qué tu fórmula es correcta. (Pista).

Mostraste en Problema 152b cómo obtener cada poder de\(x\) en términos de la caída de los poderes factoriales\(x^{\underline{j}}\). Por lo tanto, cada polinomio en\(x\) es expresable en términos de una suma de múltiplos numéricos de potencias factoriales decrecientes. Usando el lenguaje del álgebra lineal, decimos que los poderes ordinarios de\(x\) y los poderes factoriales que caen de\(x\) cada uno forman una base para el “espacio” de polinomios, y que los números\(S(k, n)\) son “cambio de coeficientes de base”. Si no está familiarizado con el álgebra lineal, una base para el espacio de polinomios es un conjunto de polinomios tal que cada polinomio, ya sea en ese conjunto o no, se pueda expresar de una y sólo una manera como una suma de múltiplos numéricos de polinomios en el conjunto.

\(\circ\) Exercise \(153\)

Demostrar que cada poder de\(x + 1\) es expresable como una suma de múltiplos numéricos de poderes de\(x\). Ahora demuestra que cada poder de\(x\) (y así cada polinomio en\(x\)) es una suma de múltiplos numéricos (algunos de los cuales podrían ser negativos) de poderes de\(x + 1\). Esto significa que los poderes de\(x + 1\) son una base para el espacio de polinomios también. Describir el cambio de coeficientes de base que utilizamos para expresar\(x^{j}\) explícitamente los poderes binomiales\((x+1)^n\) en términos de lo ordinario. Encontrar el cambio de coeficientes de base que utilizamos para expresar los poderes ordinarios\(x^n\) en términos de los poderes binomiales\((x + 1)^k\). (Pista).

\(\rightarrow \; \cdot\) Exercise \(154\)

Por multiplicación, podemos ver que cada polinomio factorial descendente puede expresarse como una suma de múltiplos numéricos de poderes de\(x\). En símbolos, esto significa que hay números\(s(k, n)\) (fíjese que esta s es minúscula, no mayúscula) tal que podamos escribir\(x^{\underline{k}} = \sum^{k}_{n=0}s(k,n)x^{n}\). Estos números\(s(k, n)\) se llaman Números Stirling del primer tipo. Al pensar algebraicamente sobre lo que la fórmula

\[x^{\underline{k}} = x^{\underline{k-1}}(x-k+1) \label{3.2.1}\]

significa, podemos encontrar una recurrencia para los números de Stirling del primer tipo que nos da otra matriz triangular de números llamada triángulo de Stirling del primer tipo. Explique por qué Ecuación\(\ref{3.2.1}\) es verdadera y utilícela para derivar una recurrencia\(s(k, n)\) en términos de\(s(k−1, n−1)\) y\(s(k−1, n)\). (Pista).

Ejercicio\(155\)

Anota las filas del triángulo de Stirling de primer tipo para\(k = 0\) a\(6\).

Por definición, los números de Stirling del primer tipo también son coeficientes de cambio de base. Los números Stirling del primer y segundo tipo son cambio de coeficientes básicos de los poderes factoriales decrecientes\(x\) a los poderes factoriales ordinarios, y viceversa.

\(\rightarrow\) Exercise \(156\)

Explicar por qué cada polinomio factorial ascendente\(x^{\bar{k}}\) puede expresarse como una suma de múltiplos de los polinomios factoriales descendentes\(x^{\underline{n}}\). Dejemos de\(b(k, n)\) pie el cambio de coeficientes de base que nos permitan expresar\(x^{\bar{k}}\) en términos de los polinomios factoriales descendentes\(x^{\underline{n}}\); es decir, definir\(b(k, n)\) por las ecuaciones

\[x^{\bar{k}} = \sum^{k}_{n=0}b(k,n)x^{\underline{n}}\].

1. Encuentra una recurrencia para\(b(k, n)\). (Pista).
2. Encuentra una fórmula para\(b(k, n)\) y prueba la exactitud de lo que dices de tantas maneras como puedas. (Pista).
3. ¿Es\(b(k, n)\) lo mismo que alguna de las otras familias de números (coeficientes binomiales, números de Bell, números de Stirling, números de Lah, etc.) que hemos estudiado?
4. Di todo lo que puedas (pero dilo precisamente) sobre el cambio de coeficientes de base para expresar\(x^{\underline{k}}\) en términos de\(x^{\bar{n}}\). (Pista).