Reveja a definição de Números de Bell Bn no Corolário 3.1.8. Mostre a seguinte recorrência:
Bn=sumk=1^nbinomn-1k-1 Bn-k
Dica: note que o número de Bell Bn é o número de possíveis relações de equivalência um conjunto X, sendo |X|=n. Fixe então um elemento de X e denote por k o número de elementos da classe de equivalência que contém esse elemento.

Passo 1

Beleza, vamos lá! O exercício pede para a gente revisar a definição dos Números de Bell, que são usados para contar o número de maneiras de dividir um conjunto em classes de equivalência. A matéria aqui é combinatória, especialmente sobre relações de equivalência. Para resolver, vamos precisar entender como fixar um elemento e contar as possíveis divisões com base nisso.

Passo 2

Primeiro, lembro que o Número de Bell Bn representa o número de maneiras de particionar um conjunto com n elementos em classes de equivalência. Ou seja, quantas formas diferentes podemos dividir um conjunto de n itens onde cada divisão é uma relação de equivalência.

Passo 3

A dica do exercício sugere fixarmos um elemento específico do conjunto, digamos, o elemento x. Vamos decidir quantos elementos vão estar na mesma classe de equivalência que o x. Chamaremos esse número de k. Assim, k pode variar de 1 até n, porque a classe de x pode ter no mínimo só o próprio x ou incluir todos os n elementos.

Passo 4

Agora, para cada valor de k, precisamos contar de quantas maneiras podemos escolher os outros k-1 elementos que vão estar na mesma classe que x. Isso é dado pela combinação binomn-1k-1, que representa o número de maneiras de escolher k-1 elementos dentre os n-1 restantes (já que já fixamos o x).

Passo 5

Depois de escolher quais k elementos estão na classe de x, os n - k elementos restantes precisam ser particionados de todas as maneiras possíveis. O número de maneiras de fazer isso é justamente o Número de Bell Bn-k.

Passo 6

Para obter o total de maneiras de particionar o conjunto original, somamos todas as possíveis contribuições para cada valor de k. Portanto, a recorrência fica:
Bn = sumk=1^n binomn-1k-1 Bn-k

Resposta

A recorrência para os Números de Bell é:
Bn = sumk=1^n binomn-1k-1 Bn-k

Exercícios relacionados