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

Exercícios relacionados