Números combinatorios clásicos · Definición

Número de Stirling de segunda especie

combinatoria enumerativanúmeros combinatorios clásicos

Antes de empezar necesitas conocer

Al particionar un conjunto aparecen agrupaciones que no importan en qué orden se listan. Los números de Stirling de segunda especie miden exactamente cuántas de estas agrupaciones existen.

Definición

El número de Stirling de segunda especie S(n,k) cuenta las particiones de un conjunto de n elementos en k bloques no vacíos e indistinguibles.

\[S(n,k)=kS(n-1,k)+S(n-1,k-1)\]

Sus propiedades básicas son S(n,1)=1, S(n,n)=1 y S(n,k)=0 si k>n. Satisfacen la recurrencia S(n,k)=kS(n-1,k)+S(n-1,k-1), que se justifica separando según si el elemento n forma un bloque propio o se une a un bloque ya existente. Además, la suma sobre k de S(n,k) da el número de Bell.

Para n=4 y k=2, la recurrencia da S(4,2)=2S(3,2)+S(3,1)=2·3+1=7. Comprobándolo por enumeración, las particiones de {1,2,3,4} en dos bloques son 7, lo que confirma el valor.

Un error típico es confundir S(n,k) con los coeficientes binomiales, o contar particiones ordenadas como si el orden de los bloques importara. Recuerda que los bloques se consideran indistinguibles, así que S(n,k) no se multiplica por k! salvo que se quiera contar particiones ordenadas.

Para pensar

¿Por qué S(n,k) no se multiplica por k! si los bloques no tienen orden, y qué cambiaría si sí lo tuvieran?

Los bloques indistinguibles no tienen un orden propio, así que cada partición se cuenta una sola vez. Si los bloques estuvieran etiquetados u ordenados, cada partición se contaría k! veces, dando \(k!\,S(n,k)\).

Ejercicios 10

  1. ¿Cuántas particiones de un conjunto de 3 elementos en 2 bloques no vacíos existen?
  2. Indica el valor de S(n,n) para cualquier n≥1.
  3. Enuncia qué cuenta el número de Stirling S(n,k).
  4. ¿Cuál es el valor de \(S(n,1)\) para \(n\ge 1\)?
  5. ¿Cuánto vale S(n,k) cuando k>n?
  6. Usa la recurrencia para calcular S(4,2).
  7. Calcula S(4,3) usando S(n,k)=kS(n-1,k)+S(n-1,k-1) y S(3,3)=1.
  8. Suma los valores S(3,k) para k=1,2,3 y di a qué número de Bell corresponde.
  9. ¿Cuántas particiones ordenadas de 3 elementos en 2 bloques no vacíos existen?
  10. Demuestra que \(S(n,2)=2^{n-1}-1\) para \(n\ge 1\) y verifica con \(n=4\). Indica el valor de \(S(4,2)\).

Después de esto

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.