Números combinatorios clásicos · Definición

Número de Stirling de primera especie

combinatoria enumerativanúmeros combinatorios clásicos

Antes de empezar necesitas conocer

Aparecen al expandir productos de factores lineales y al contar ciclos en permutaciones. Conectan el álgebra de polinomios con la combinatoria de conteo.

Definición

El número de Stirling de primera especie \(c(n,k)\) cuenta las permutaciones de \(n\) elementos que tienen exactamente \(k\) ciclos.

\[x(x+1)\cdots(x+n-1)=\sum_{k=0}^{n} c(n,k)\,x^{k}\]

Cumplen \(c(n,n)=1\), \(c(n,0)=0\) para \(n\ge 1\) y \(c(n,1)=(n-1)!\), y los valores de cada fila suman \(n!\). Satisfacen la recurrencia \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\) con \(c(0,0)=1\).

Para \(n=3\), las permutaciones con un único ciclo son los dos 3-ciclos, así que \(c(3,1)=2\). Con dos ciclos hay tres, una transposición más un punto fijo, luego \(c(3,2)=3\); y la identidad da \(c(3,3)=1\).

Un error frecuente es confundirlos con los números de Stirling de segunda especie, que cuentan particiones en bloques no vacíos. Ambas familias pueden coincidir en valores pequeños, pero no en general, así que conviene verificar siempre la definición.

Para pensar

¿Por qué \(c(n,k)=0\) cuando \(k>n\)?

Cada ciclo contiene al menos un elemento y los ciclos son disjuntos, así que no puede haber más ciclos que elementos.

Ejercicios 10

  1. ¿Qué cuenta el número \(c(n,k)\)?
  2. Las permutaciones de \(\{1,2,3\}\) con un único ciclo son los 3-ciclos. ¿Cuánto vale \(c(3,1)\)?
  3. ¿Cuánto vale \(c(n,n)\) para todo \(n\ge 1\)?
  4. ¿Cuánto vale \(c(n,0)\) para \(n\ge 1\)?
  5. ¿Cuánto vale \(c(n,1)\)?
  6. Usa \(c(4,1)=6\), \(c(4,2)=11\), \(c(4,3)=6\) y \(c(4,4)=1\). ¿Cuánto suma la fila \(n=4\)?
  7. Con \(c(4,2)=11\) y \(c(4,1)=6\), usa \(c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)\) para hallar \(c(5,2)\).
  8. Desarrolla \(x(x+1)(x+2)=\sum_k c(3,k)\,x^k\). ¿Cuánto vale \(c(3,2)\)?
  9. Con la fila \(n=4\), donde \(c(4,1)=6\), \(c(4,2)=11\), \(c(4,3)=6\) y \(c(4,4)=1\), calcula \(\sum_{k=1}^{4} k\,c(4,k)\).
  10. Una afirmación dice que \(c(n,k)=c(n-1,k-1)+c(n-1,k)\) siempre. ¿En cuál par \((n,k)\) la igualdad sí se cumple?

Referencias

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