Quantas árvores de busca binária com nós 1, 2, 3 e 4 existem?
Passo 1
No enunciado, queremos contar quantas árvores de busca binária existem com os nós rotulados por 1, 2, 3 e 4. Esse é um problema de combinatória que usa o conceito de número de Catalan para árvores de busca binária.
Passo 2
O número de árvores de busca binária com n nós distintos é dado pelo n-ésimo número de Catalan. A fórmula fechada é:
Passo 3
A primeira etapa é calcular a combinação
Passo 4
Agora aplicamos o número de Catalan para n = 4
Resposta
14