Números de Stirling de segunda especie

Números de Stirling de segunda especie

En matemáticas, los Números de Stirling de segunda especie, junto con los Números de Stirling de primera especie, son uno de los dos tipos de Números de Stirling. Comúnmente aparecen en el estudio de la combinatoria, en la que se cuenta el número de permutaciones posibles.

Contenido

Definición

Los Números de Stirling de segunda especie S(n,k) se definen como la cantidad de maneras que existen de hacer una partición de un conjunto de n elementos en k subconjuntos. La suma

B_n=\sum_{k=1}^n S(n,k)

es el n-ésimo Número de Bell. Si tomamos la fórmula

(x)_n=x(x-1)(x-2)\cdots(x-n+1)

(en particular, (x)0 = 1 porque se trata de un producto vacío), podemos caracterizar los números de Stirling de segundo tipo mediante

\sum_{k=0}^n S(n,k)(x)_k=x^n.

Tabla de valores

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

Relación de recurrencia

Los Números de Stirling de segunda especie obedecen la siguiente relación de recurrencia

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} +k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}

con

\left\{\begin{matrix} n \\ 1 \end{matrix}\right\}=1 \quad \mbox { y } \quad \left\{\begin{matrix} n \\ n \end{matrix}\right\} = 1.

Por ejemplo, el número 25 en la columna k=3 y la fila n=5 viene dado por 25=7+(3×6), donde 7 es el número de arriba a la izquierda del 25, 6 es el número que hay encima del 25 y 3 es la columna conteniendo el 6.

Paridad

Usando un Triángulo de Sierpinski, es fácil mostrar que la paridad de un número de Stirling de segunda especie es igual a la paridad del coeficiente binomial:

\begin{Bmatrix}n\\k\end{Bmatrix}\equiv\binom{z}{w}\pmod{2},\quad z = n - \left\lceil\dfrac{k + 1}{2}\right\rceil,\ w = \left\lfloor\dfrac{k - 1}{2}\right\rfloor.

O directamente, construimos dos conjuntos tales que contengan posiciones de 1's en representaciones binarias de los resultados de las respectivas expresiones:

\begin{align} \mathbb{A}:\ \sum_{i\in\mathbb{A}} 2^i &= n-k,\\ \mathbb{B}:\ \sum_{j\in\mathbb{B}} 2^j &= \left\lfloor\dfrac{k - 1}{2}\right\rfloor,\\ \end{align}

claramente aparecen semejanzas entre la operación AND y la intersección de estos dos conjuntos:

\begin{Bmatrix}n\\k\end{Bmatrix}\bmod 2 = \begin{cases} 0, & \mathbb{A}\cap\mathbb{B}\ne\empty\\ 1, & \mathbb{A}\cap\mathbb{B}=\empty \end{cases}

nos permitirá obtener la paridad de un número de Stirling de segunda especie en una cantidad constante de tiempo.

Identidades simples

Primera identidad

\left\{\begin{matrix} n \\ n-1 \end{matrix}\right\} = {n \choose 2}.

Esto es así porque dividir n elementos en n − 1 subconjuntos implica dividirlo en un conjunto de cardinal 2 y n − 2 conjuntos de cardinal 1, con lo que sólo tenemos que escoger los dos elementos que formarán el primer subconjunto de entre los n elementos que tenemos.

Segunda identidad

\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = 2^{n-1}-1.

Sea \mathcal{A} un conjunto de n elementos, el conjunto de las partes \mathcal{P(A)} tiene 2n elementos, cada uno de ellos es un subconjunto de \mathcal{A} por lo que para cada a \in \mathcal{P(A)} existe su conjunto complementario a^c : a^c \cup a = \mathcal{A}. Por tanto tenemos 2n / 2 = 2n − 1 pares de subconjuntos tales que su unión forma el conjunto \mathcal{A}, pero tenemos que descartar la pareja que contiene el conjunto nulo, ya que dicha pareja no forma una partición de \mathcal{A} (por definición).

Tercera identidad

Otra forma de expandir recursivamente los números de Stirling de segunda especie.

\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = \frac{ \frac11 (2^{n-1}-1^{n-1}) }{0!}
\left\{\begin{matrix} n \\ 3 \end{matrix}\right\} = \frac{ \frac11 (3^{n-1}-2^{n-1})- \frac12 (3^{n-1}-1^{n-1}) }{1!}
\left\{\begin{matrix} n \\ 4 \end{matrix}\right\} = \frac{ \frac11 (4^{n-1}-3^{n-1})- \frac22 (4^{n-1}-2^{n-1}) + \frac13 (4^{n-1}-1^{n-1})}{2!}
\left\{\begin{matrix} n \\ 5 \end{matrix}\right\} = \frac{ \frac11 (5^{n-1}-4^{n-1})- \frac32 (5^{n-1}-3^{n-1}) + \frac33 (5^{n-1}-2^{n-1}) - \frac14 (5^{n-1}-1^{n-1}) }{3!}
\vdots

Fórmula explícita

Los Números de Stirling de segunda especie vienen dados por la siguiente fórmula explícita:

\left\{\begin{matrix} n \\ k \end{matrix}\right\} =\sum_{j=1}^k (-1)^{k-j} \frac{j^{n-1}}{(j-1)!(k-j)!} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n .

Esta fórmula es un caso especial de la k-ésima diferencia hacia delante (en inglés, forward difference) del monomio xn evaluado en x = 0:

\Delta^k x^n = \sum_{j=0}^{k}(-1)^{k-j}{k \choose j} (x+j)^n.

Debido a que los polinomios de Bernoulli pueden expresarse en términos de estas diferencias hacia delante, obtenemos una relación inmediata con los números de Bernoulli:

B_m(0)=\sum_{k=0}^m \frac {(-1)^k k!}{k+1} \left\{\begin{matrix} m \\ k \end{matrix}\right\}.

Funciones generatrices

Una función generatriz para los números de Stirling de segunda especie viene dada por:

\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} (x)_k = x^n.

Momentos de la distribución de Poisson

Si X es una variable aleatoria de una distribución de Poisson con valor esperado λ, entonces, su momento n-ésimo es

E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.

En particular, el momento n-ésimo de la distribución de Poisson con valor esperado 1 es precisamente el número de particiones de un conjunto de tamaño n, i.e., es el n-ésimo número de Bell (este hecho es la fórmula de Dobinski).

Momentos de puntos fijos de permutaciones aleatorias

Sea la variable aleatoria X el número de puntos fijos de una permutación aleatoria uniformemente distribuida de un conjunto finito de tamaño m. Entonces el n-ésimo momento de X es

E(X^n) = \sum_{k=1}^m S(n,k).

Nota: el límite superior de la sumatoria es m, no n.

En otras palabras, el n-ésimo momento de esta distribución de probabilidad es el número de particiones de un conjunto de tamaño n dentro de no más de m partes. Esto esta probado en la página de random permutation statistics, aunque la notación es un poco diferente.

Problema de la Caja de Cereal

Los números de Stirling de segunda especie pueden representar el número total de formas que una persona puede coleccionar todos los premios después de abrir un número dado de cajas de cereal. Por ejemplo, si hay 3 premios, y uno abre tres cajas, hay S(3,3), o 1 manera de ganar, {1,2,3}. Si se abren 4 cajas, hay 6 maneras de ganar S(4,3); {1,1,2,3}, {1,2,1,3}, {1,2,3,1}, {1,2,2,3}, {1,2,3,2}, {1,2,3,3}.

Rhyming Schemes

The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of n lines. S(n,k) gives the number of possible rhyming schemes for n lines using k unique rhyming syllables. As an example, for a poem of 3 lines, there is 1 rhyme scheme using just 1 rhyme (aaa), 3 rhyme schemes using two rhymes (aab, aba, abb), and one rhyme scheme using 3 rhymes (abc).


Véase también

  • Números de Bell - el número de particiones de un conjunto con n elementos.
  • Falling Factorial


Referencias


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Números de Stirling — Esta página está siendo editada activamente por un corto período de tiempo por un wikipedista. Si esta página no ha sido editada durante varias horas, elimina este mensaje o reemplázalo por {{en desarrollo}}. La finalidad de este mensaje es… …   Wikipedia Español

  • Número de Bell — En combinatoria, el n ésimo número de Bell, llamado así por Eric Temple Bell, es el número de particiones de un conjunto de n elementos, o equivalentemente, el número de relaciones de equivalencia en el mismo. Comenzando con B0 = B1 = 1, los… …   Wikipedia Español

  • Función polilogarítmica — El polilogaritmo (también conocido como función de Jonquière) es una función especial definida por la siguiente serie: Esta no es, en general, una función elemental, aunque esté relacionada con la función logarítmica. La definición dada arriba es …   Wikipedia Español

  • Anarquismo individualista — El anarquismo individualista o anarcoindividualismo es una tradición filosófica del anarquismo con un particular énfasis en la autonomía del individuo,[1] sosteniendo que cada uno es su propio dueño, interactuando con los otros a través de la… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”