Números de Stirling

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas, los Números de Stirling resuelven algunos problemas del área de combinatoria. Su nombre se debe a James Stirling, quien los popularizó en el siglo XVIII. Existen dos diferentes conjuntos de números con este nombre: números de Stirling de primera especie y números de Stirling de segunda especie.

Notación[editar]

Existen diversas formas de denotar los números de Stirling. Los números de Stirling del primera especie se escriben con una s pequeña y los de segunda especie con una S grande (Abramowitz and Stegun usa una mayúscula o una S gótica). Las notaciones más comunes son:

  • Los números de Stirling de primera clase ordinarios (signados) se denotan como:

 s(n,k)\text{ (con signo)}\,

  • Los números de Stirling de primera clase signados se denotan como:

 \left[{n \atop k}\right]=c(n,k)=|s(n,k)|\text{ (sin signo)}\,

Los números de Stirling de segunda clase se denotan como:

 \left\{\begin{matrix} n \\ k \end{matrix}\right\}=S(n,k)= S_n^{(k)} 
.\,

La notación usando llaves y corchetes, en analogía a los coeficientes binomiales, fue introducida en 1935 por Jovan Karamata y promocionada por Donald Knuth; referida a veces como la notación de Karamata.

Números de Stirling de primera clase[editar]

Los números de Stirling de primera clase son los coeficientes s(n,k) de la expansión:

(x)_{n} = \sum_{k=0}^n s(n,k) x^k\,

donde (x)_{n} (símbolo de Pochhammer) denota el factorial descendente,

(x)_{n}=x(x-1)(x-2)\cdots(x-n+1)\,

Nótese que (x)0 = 1 porque es un producto vacío. En combinatoria también se usa la notación x^{\underline{n\!}} para el factorial descedente, y x^{\overline{n\!}} para el factorial ascendente.[1]

Los números de Stirling de primera clase no signados:

c(n,k)=\left[{n \atop k}\right]=|s(n,k)|=(-1)^{n-k} s(n,k)

(con una "s" minúscula), cuenta el número de permutaciones de n elementos con k cicloss disjuntos. Las siguiente tabla muestra algunos pocos números de Stirling de primera clase:

\begin{array}{ccccccccccc}
&&&&&~~1~~&&&&&\\
&&&&-1&&~~1~~&&&&\\
&&&2&&-3&&~~1~~&&&\\
&&-6&&11&&-6&&~~1~~&&\\
&24&&-50&&35&&-10&&~~1~~&\\
-120&&274&&-225&&85&&-15&&~~1~~\\
\end{array}

donde

s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)

Números de Stirling de segunda clase[editar]

El número de Stirling de segunda especie S(n,k) de formas de dividir un un conjunto de n elementos en k partes:

S(n,k) = \text{card}\left(\{B|\ \text{card}(B)= k \land B \subset \mathbb{N}_n \} \right)

donde el conjunto \mathbb{N}_n = [1,n] \cap \mathbb{N} es el conjunto de los primeros n enteros. Otra notación para los números de Stirling de segunda especie son:

\left\{\begin{matrix} n \\ k \end{matrix}\right\} := S(n,k)

A continuación se muestra una tabla de valores para los números de Stirling de segunda especie:

n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1

donde:

S(n,k) = S(n-1,k-1) + k S(n-1,k)\,

Fórmulas simétricas[editar]

Abramowitz y Stegun presentan las siguientes fórmulas simétricas que relacionan los número de Stirling de primera especie con los de segunda especie:

\left[{n\atop k}\right] = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left\{{n-k+j\atop j}\right\}

Y

\left\{{n\atop k}\right\} = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left[{n-k+j\atop j}\right].

Referencias[editar]

  1. Aigner, Martin (2007). «Section 1.2 - Subsets and Binomial Coefficients». A Course In Enumeration. Springer. p. 561. ISBN 3-540-39032-4. 

Bibliografía[editar]