Así, para contar una clase de objetos combinatorios que se puede romper en los casos y agregar las cantidades siempre y cuando 1) no hay ningún solapamiento entre casos y 2) cada objeto que se cuenta en al menos uno de los casos. Esto es justo como si usted desea contar el número de estudiantes en un salón de clases usted puede en lugar de contar todas las estudiantes de sexo masculino y sumar el número de estudiantes de sexo femenino o cómo, si usted desea contar el número de cuatro dígitos de números a los que usted puede contar con los cuatro números de dos dígitos y sumar el número de impares cuatro números de dos dígitos.
Los números de Stirling y los objetos con los que cuentan no son la excepción. Recuerde que los números de Stirling de primera especie contar el número de permutaciones de $n$ elementos cuya descomposición cíclica tiene, precisamente, $k$ ciclos. Elegimos recuento $s(n,k)$ por romperlo en casos como el descrito en el párrafo anterior. Estos casos son:
$1$ está en un ciclo en sí mismo.
$1$ no está en un ciclo en sí mismo, es decir, en un ciclo con algo más.
Caso 1: En el caso de que $1$ está en un ciclo por sí mismo, se reconoce que, para no ser $k$ ciclos en total, el restante $n-1$ elementos deben estar dispuestos a $k-1$ ciclos. Los números de Stirling de primera especie contar exactamente este escenario, dándonos $s(n-1,k-1)$ dichos acuerdos en este caso.
Sí, sé que estamos utilizando stirling números para contar los números de stirling... parece rotonda, pero que es exactamente la fuerza de las relaciones de recurrencia. Dado suficiente información inicial y de una recurrencia de la relación, ahora disponemos de suficiente información para calcular cualquier resultado específico que deseamos, y, en particular, el valor de $s(n,k)$ para cualquier valor de $n$$k$.
Caso 2: (enel caso de que usted está interesado en) En el caso de que $1$ es no en un ciclo en sí, lo que implica que debe ser en un ciclo con algo más. Ya que está en un ciclo con otra cosa si quitáramos $1$ a partir de la imagen completamente la configuración resultante todavía tendría $k$ ciclos pesar de que sólo el $n-1$ elementos desde la eliminación de la $1$ no han eliminado un ciclo, sólo acorta.
Reconocemos ahora que podemos trabajar a la inversa. En primer lugar tomar una disposición de los números de $\{2,3,4,\dots,n\}$ en una permutación que tiene, precisamente, $k$ ciclos. Ahora... elija uno de los números en el acuerdo y vamos a insertar $1$ en el lugar justo antes de ese número, pero en el mismo ciclo.
Por ejemplo, si tenemos la permutación en forma cíclica $(2~3~5)(4)(6~7)$ y elegimos insertar el $1$ antes de la $3$, la nueva resultante de permutación sería $(2~\color{red}{1~3}~5)(4)(6~7)$. Alternativamente, si habíamos elegido para insertar el $1$ antes de la $4$ tendríamos $(2~3~5)(\color{red}{1~4})(6~7)$, etc...
Reconocemos ahora que hay un fácil bijection entre el número de permutaciones de $n$ elementos que se descomponen en $k$ ciclos donde $1$ no está en un ciclo en sí mismo (no es un punto fijo) y el producto cartesiano del conjunto de las permutaciones de $n-1$ elementos que se descomponen en $k$ ciclos y el conjunto de los números $\{2,3,\dots,n\}$. El bijection en la dirección inversa es el proceso que hemos descrito en los dos párrafos anteriores, primero tomando una permutación del tipo que nos interesa sin $1$ y, a continuación, insertar $1$ en la posición justo antes de que el número especificado.
Como la cardinalidad del producto cartesiano de dos conjuntos es el producto de las cardinalidades de los dos conjuntos (es decir, el principio de la multiplicación/norma de producto) tenemos un recuento de $s(n-1,k)\cdot (n-1)$ (el plazo $s(n-1,k)$ viene el número de permutaciones de $n-1$ elementos en $k$ ciclos y el factor de $(n-1)$ proviene de elegir qué elemento de nuestro recién introducidos $1$ es para ser colocado en frente).
Como resultado final, tenemos $s(n,k)=|\mathrm{Case1}|+|\mathrm{Case2}|$ lo que implica
$$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k).$$
