questão sobre número de stirling

(a)  Queremos particionar o conjunto {1,2,3,4,5} em 4 subconjuntos não vazios. Isso implica que exatamente um dos subconjuntos terá 2 elementos, e os 3 demais terão 1 elemento. Assim, basta escolher 2 elementos para formarem o subconjunto com 2 elementos e os demais automaticamente ficam definidos. Logo

\( \displaystyle {5 \brace 4} = \binom 52 = 10\)


(b) Para criar uma partição de {1,2,...,n} com k subconjuntos podemos proceder  da seguinte forma:

Tomar uma partição de {1,2,...,n-1} com k-1 subconjuntos e adicionamos o conjunto {n} nessa partição. Isso dá todas as partições de {1,...,n} com k subconjuntos de forma que {n} é um desses subconjuntos. Ou seja, isso da um total de \( \displaystyle {n-1 \brace k-1}\) possibilidades.

Para as demais situações, tomamos uma partição de {1,2,...,n-1} com k subconjuntos. Depois acrescentamos o elemento n a um desses k subconjuntos. Isso dará todas as partições de {1,...,n} com k subconjuntos de forma que {n} não é um desses subconjuntos. Ou seja, isso da um total de \( \displaystyle k{ n-1 \brace k} \) possibilidades. Portanto concluímos que

\( \displaystyle {n \brace k} = {n-1 \brace k-1} + k { n-1 \brace k}\)