Reveja a definição de Números de Bell no Corolário 3.1.8. Mostre a seguinte recorrência:
Dica: note que o número de Bell é o número de possíveis relações de equivalência um conjunto , sendo . Fixe então um elemento de e denote por 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 representa o número de maneiras de particionar um conjunto com elementos em classes de equivalência. Ou seja, quantas formas diferentes podemos dividir um conjunto de 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 . Vamos decidir quantos elementos vão estar na mesma classe de equivalência que o . Chamaremos esse número de . Assim, pode variar de 1 até , porque a classe de pode ter no mínimo só o próprio ou incluir todos os elementos.

Passo 4

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

Passo 5

Depois de escolher quais elementos estão na classe de , os 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 .

Passo 6

Para obter o total de maneiras de particionar o conjunto original, somamos todas as possíveis contribuições para cada valor de . Portanto, a recorrência fica:

Resposta

A recorrência para os Números de Bell é:

Exercícios relacionados

Obtenha uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20.
Seja o número de maneiras de se cobrir uma caixa com retângulos (você pode colocar cada dominó na horizontal ou vertical). Obtenha uma relação de recorrência para .
Um esporte pouco conhecido é o de subir escadas. Encontre uma relação de recorrência para o número de maneiras de se subir degraus de uma escada, se a cada passo pode-se escolher subir um ou dois degraus. Se considerarmos a questão de iniciar com o pé direito ou esquerdo, como ficará a recorrência?
Considere o conjunto das sequências de tamanho tais que cada entrada pertence a e entradas vizinhas sempre diferem por 1 em módulo. Descreva um sistema de equações de recorrência para resolver este problema.