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.