1.9: Números de Stirling
- Page ID
- 117126
En el Ejercicio 1.E.5.4 de la Sección 1.E, vimos los números de Stirling del segundo tipo. No es sorprendente que haya números de Stirling de primer tipo. Recordemos que los números de Stirling del segundo tipo se definen de la siguiente manera:
Definición \(\PageIndex{1}\): The Stirling Number of the Second Kind
El número Stirling del segundo tipo,\(S(n,k)\) o\(\left\{\begin{array}{c}n\\k\end{array}\right\}\), es el número de particiones de\([n]=\{1,2,\ldots,n\}\) en exactamente\(k\) partes,\(1\le k\le n\).
Antes de definir los números de Stirling del primer tipo, necesitamos revisar las permutaciones. Como mencionamos en la Sección 1.8, podemos pensar en una permutación\([n]\) ya sea como un reordenamiento de\([n]\) o como una biyección\(\sigma\colon [n]\to[n]\). Existen diferentes formas de escribir permutaciones cuando se consideran funciones. Dos formas típicas y útiles son como una tabla, y en forma de ciclo. Considera esta permutación\(\sigma\colon [5]\to[5]\):\(\sigma(1)=3\),\(\sigma(2)=4\),\(\sigma(3)=5\),\(\sigma(4)=2\),\(\sigma(5)=1\). En forma de tabla, escribimos esto como\(\left(1\; 2\; 3\; 4\; 5\atop 3\; 4\; 5\; 2\; 1\right)\), que es algo más compacto, ya que no escribimos ""\(\sigma\) "cinco veces. En forma de ciclo, escribimos esta misma permutación que\((1,3,5)(2,4)\). Aquí\((1,3,5)\) indica que\(\sigma(1)=3\),\(\sigma(3)=5\), y\(\sigma(5)=1\), mientras\((2,4)\) indica\(\sigma(2)=4\) y\(\sigma(4)=2\). Esta permutación tiene dos ciclos, uno de 3 ciclos y uno de 2 ciclos. Tenga en cuenta que\((1,3,5)\)\((3,5,1)\),, y\((5,1,3)\) todos significan lo mismo. Permitimos que los 1-ciclos cuenten como ciclos, aunque a veces no los escribimos explícitamente. En algunos casos, sin embargo, es valioso escribirlos para obligarnos a recordar que están ahí. Considera esta permutación:\(\left(1\; 2\; 3\; 4\; 5\; 6\atop 3\; 4\; 5\; 2\; 1\; 6\right)\). Si escribimos esto en forma de ciclo como\((1,3,5)(2,4)\), lo cual es correcto, no hay indicios de que el conjunto subyacente sea realmente\([6]\). La escritura\((1,3,5)(2,4)(6)\) lo deja claro. Decimos que esta permutación tiene 3 ciclos, a pesar de que uno de ellos es un trivial de 1 ciclo. Ahora estamos listos para la siguiente definición.
Definición\(\PageIndex{2}\): Stirling Number of the First Kind
El número de Stirling del primer tipo,\(s(n,k)\), es\((-1)^{n-k}\) multiplicado por el número de permutaciones de\([n]\) con exactamente\(k\) ciclos. El número de Stirling sin signo correspondiente del primer tipo, el número de permutaciones de\([n]\) con exactamente\(k\) ciclos, está\(|s(n,k)|\), a veces escrito\(\left[\begin{array}{c}n\\k\end{array}\right]\). Usando esta notación,\(s(n,k)=(-1)^{n-k}\left[\begin{array}{c}n\\k\end{array}\right]\).
Obsérvese que el uso de\(\left[\begin{array}{c}n\\k\end{array}\right]\) conflictos con el uso de la misma notación en la Sección 1.8; no debe haber confusión, ya que no estaremos discutiendo las dos ideas juntos.
Algunos valores de\(\left[\begin{array}{c}n\\k\end{array}\right]\) son fáciles de ver; si\(n\ge 1\), entonces
\[\begin{array}{ll}\left[\begin{array}{c}n\\n\end{array}\right]=1 &\left[\begin{array}{c}n\\k\end{array}\right]=0,\text{ if }k>n \\ \left[\begin{array}{c}n\\1\end{array}\right]=(n-1)!&\left[\begin{array}{c}n\\0\end{array}\right]=0\end{array}\nonumber\]
A veces es conveniente decir eso\(\left[\begin{array}{c}0\\0\end{array}\right]=1\). Estos números forman así un triángulo de la manera obvia, tal como lo hacen los números de Stirling del primer tipo. Aquí están las líneas 1—5 del triángulo:\[\matrix{ 1\cr 0&1\cr 0&1&1\cr 0&2&3&1\cr 0&6&11&6&1\cr 0&24&50&35&10&1\cr }\nonumber\] La primera columna no es particularmente interesante, por lo que a menudo se elimina.
En el Ejercicio 1.E.5.4 de la Sección 1.E, vimos que\[\label{eq:1}\left\{\begin{array}{c}n\\k\end{array}\right\}=\left\{\begin{array}{c}n-1 \\ k-1\end{array}\right\}+k\cdot\left\{\begin{array}{c}n-1\\k\end{array}\right\}.\]
Los números de Stirling sin signo del primer tipo satisfacen una recurrencia similar.
Teorema \(\PageIndex{1}\)
\(\left[\begin{array}{c}n\\k\end{array}\right]=\left[\begin{array}{c}n-1 \\ k-1\end{array}\right] + (n-1)\cdot\left[\begin{array}{c}n-1 \\ k\end{array}\right]\),\(k\ge 1\),\(n\ge1\).
- Prueba
-
La prueba es por inducción\(n\); la tabla anterior muestra que es cierto para las primeras líneas. Dividimos las permutaciones de\([n]\) con\(k\) ciclos en dos tipos: aquellos en los que\((n)\) es un ciclo 1, y el resto. Si\((n)\) es un ciclo 1, entonces los ciclos restantes forman una permutación de\([n-1]\) con\(k-1\) ciclos, por lo que hay\(\left[\begin{array}{c}n-1 \\k-1\end{array}\right]\) de estos. De lo contrario,\(n\) ocurre en un ciclo de longitud de al menos 2, y retirando\(n\) las hojas una permutación de\([n-1]\) con\(k\) ciclos. Dada una permutación\(\sigma\) de\([n-1]\) con\(k\) ciclos, se\(n\) puede agregar a cualquier ciclo en cualquier posición para formar una permutación de\([n]\) en la que no\((n)\) se encuentre un 1-ciclo. Supongamos que las longitudes de los ciclos en\(\sigma\) son\(l_1,l_2,\ldots,l_k\). En número de ciclo\(i\), se\(n\) puede agregar después de cualquiera de los\(l_i\) elementos en el ciclo. Así, el número total de lugares que se\(n\) pueden sumar es\(l_1+l_2+\cdots+l_k=n-1\), por lo que hay\((n-1)\cdot\left[\begin{array}{c}n-1 \\ k\end{array}\right]\) permutaciones de\([n]\) en las que no\((n)\) es un 1-ciclo. Ahora el número total de permutaciones de\([n]\) con\(k\) ciclos es\(\left[\begin{array}{c}n-1 \\ k-1\end{array}\right]+ (n-1)\cdot\left[\begin{array}{c}n-1 \\ k\end{array}\right]\), según se desee.
Corolario \(\PageIndex{1}\)
\(s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k)\).
Los números de Stirling satisfacen dos identidades notables. Primero una definición:
Definición\(\PageIndex{3}\): The Kronecker delta
El delta de Kronecker\(\delta_{n,k}\) es 1 si\(n=k\) y 0 en caso contrario.
Teorema \(\PageIndex{2}\)
Para\(n\ge 0\) y\(k\ge 0\),
\[\eqalign{ \sum_{j=0}^n s(n,j)S(j,k) &= \sum_{j=0}^n (-1)^{n-j}\left[\begin{array}{c}n\\j\end{array}\right]\left\{\begin{array}{c}j\\k\end{array}\right\} =\delta_{n,k}\cr \sum_{j=0}^n S(n,j)s(j,k) &= \sum_{j=0}^n (-1)^{j-k}\left\{\begin{array}{c}n\\j\end{array}\right\}\left[\begin{array}{c}j\\k\end{array}\right] = \delta_{n,k}\cr }\nonumber\]
- Prueba
-
Demostramos la primera versión, por inducción en\(n\). Los primeros valores de\(n\) se comprueban fácilmente; supongamos\(n>1\). Ahora tenga en cuenta eso\(\left[\begin{array}{c}n\\0\end{array}\right]=0\), por lo que podemos iniciar el índice de suma\(j\) en 1.
Cuando\(k>n\),\(\left\{\begin{array}{c}j\\k\end{array}\right\}=0\), para\(1\le j\le n\), y así la suma es 0. Cuando\(k=n\), el único término distinto de cero ocurre cuando\(j=n\), y es\((-1)^0\left[\begin{array}{c}n\\n\end{array}\right]\left\{\begin{array}{c}n\\n\end{array}\right\}=1\), por lo que la suma es 1. Ahora supongamos\(k< n\). Cuando\(k=0\),\(\left\{\begin{array}{c}j\\k\end{array}\right\}=0\) para\(j>0\), entonces la suma es 0, y suponemos ahora que\(k>0\).
Comenzamos aplicando las relaciones de recurrencia:\[\eqalign{ \sum_{j=1}^n &(-1)^{n-j}\left[\begin{array}{c}n\\j\end{array}\right] \left\{\begin{array}{c}j\\k\end{array}\right\}= \sum_{j=1}^n (-1)^{n-j}\left(\left[\begin{array}{c}n-1 \\ j-1\end{array}\right]+(n-1)\left[\begin{array}{c}n-1 \\ j\end{array}\right]\right) \left\{\begin{array}{c}j\\k\end{array}\right\}\cr &=\sum_{j=1}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right] \left\{\begin{array}{c}j\\k\end{array}\right\}+ \sum_{j=1}^n (-1)^{n-j}(n-1)\left[\begin{array}{c}n-1\\j\end{array}\right] \left\{\begin{array}{c}j\\k\end{array}\right\}\cr &=\sum_{j=1}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right] \left(\left\{\begin{array}{c}j-1\\k-1\end{array}\right\}+ k\left\{\begin{array}{c}j-1\\k\end{array}\right\}\right) + \sum_{j=1}^n (-1)^{n-j}(n-1)\left[\begin{array}{c}n-1\\j\end{array}\right] \left\{\begin{array}{c}j\\k\end{array}\right\}\cr &=\sum_{j=1}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right] \left\{\begin{array}{c}j-1\\k-1\end{array}\right\}+ \sum_{j=1}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right] k\left\{\begin{array}{c}j-1\\k\end{array}\right\}\cr &\qquad+ \sum_{j=1}^n (-1)^{n-j}(n-1)\left[\begin{array}{c}n-1\\j\end{array}\right] \left\{\begin{array}{c}j\\k\end{array}\right\}.\cr }\nonumber\]
Considera la primera suma en la última expresión:\[\eqalign{ \sum_{j=1}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right]\left\{\begin{array}{c}j-1\\k-1\end{array}\right\} &=\sum_{j=2}^n (-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right]\left\{\begin{array}{c}j-1\\k-1\end{array}\right\}\cr &=\sum_{j=1}^{n-1} (-1)^{n-j-1}\left[\begin{array}{c}n-1\\j\end{array}\right]\left\{\begin{array}{c}j\\k-1\end{array}\right\}\cr &=\delta_{n-1,k-1}=0, }\nonumber\] since\(k-1< n-1\) (o trivialmente, if\(k=1\)).
Así, nos quedan sólo dos sumas. \[\eqalign{ \sum_{j=1}^n &(-1)^{n-j}\left[\begin{array}{c}n-1\\j-1\end{array}\right]k\left\{\begin{array}{c}j-1\\k\end{array}\right\} +\sum_{j=1}^n (-1)^{n-j}(n-1)\left[\begin{array}{c}n-1\\j\end{array}\right]\left\{\begin{array}{c}j\\k\end{array}\right\}\cr &=k\sum_{j=1}^{n-1} (-1)^{n-j-1}\left[\begin{array}{c}n-1\\j\end{array}\right]\left\{\begin{array}{c}j\\k\end{array}\right\} -(n-1)\sum_{j=1}^{n-1} (-1)^{n-j-1}\left[\begin{array}{c}n-1\\j\end{array}\right]\left\{\begin{array}{c}j\\k\end{array}\right\}\cr &=k\delta_{n-1,k}-(n-1)\delta_{n-1,k}. }\nonumber\]
Ahora si\(k=n-1\), esto es\((n-1)\delta_{n-1,n-1}-(n-1)\delta_{n-1,n-1}=0\), mientras que si\(k< n-1\) lo es\(k\delta_{n-1,k}-(n-1)\delta_{n-1,k}=k\cdot 0-(n-1)\cdot 0=0\).
Si interpretamos los triángulos que contienen el\(s(n,k)\) y\(S(n,k)\) como matrices, ya sea\(m\times m\), tomando las primeras\(m\) filas y columnas, o incluso las matrices infinitas que contienen los triángulos enteros, las sumas del teorema corresponden a calcular el producto matricial en ambos órdenes. El teorema dice entonces que este producto consiste en unos en la diagonal y ceros en otra parte, por lo que estas matrices son inversas. Aquí hay un pequeño ejemplo:
\[ \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& -1& 1& 0& 0& 0\cr 0& 2& -3& 1& 0& 0\cr 0& -6& 11& -6& 1& 0\cr 0& 24& -50& 35& -10& 1\cr } \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& 1& 1& 0& 0& 0\cr 0& 1& 3& 1& 0& 0\cr 0& 1& 7& 6& 1& 0\cr 0& 1& 15& 25& 10& 1\cr } = \pmatrix{ 1& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0\cr 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 1& 0& 0\cr 0& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 1\cr }\nonumber \]