Suponha que
carros estão em fila para entrar em um estacionamento que possui
vagas, lado a lado. Se o
carro pode escolher qualquer vaga e cada um dos outros carros ao estacionar deve justapor-se a um carro já estacionado, quantos são os modos possíveis dos carros ocuparem as
vagas?
Passo 1
O enunciado pede o número de modos de estacionar
carros numerados pela ordem de chegada em
vagas alinhadas, de modo que o primeiro carro vai em qualquer vaga e cada carro seguinte ocupa uma vaga livre que seja adjacente a alguma já ocupada. O conteúdo principal é contagem de configurações sujeitas a uma regra de “adjacência” que pode ser traduzida em uma sequência de movimentos à esquerda ou à direita.
Passo 2
Suponha que o primeiro carro estacione na vaga
, com
. A partir daí as vagas ocupadas formam um bloco contínuo que tem extremidades nos índices
e
. Inicialmente
. Cada carro seguinte amplia esse bloco ou para a esquerda (movimento
) ou para a direita (movimento
), desde que não ultrapasse os limites
e
. Para preencher todas as vagas, é preciso fazer exatamente
movimentos
(para ocupar as vagas à esquerda de
) e
movimentos
. Qualquer permutação desses
movimentos leva a uma sequência de estacionamento válida, logo, dado
, o número de modos é
Passo 3
Agora somamos sobre todas as escolhas possíveis de
para o primeiro carro: