Suponha que n carros estão em fila para entrar em um estacionamento que possui n vagas, lado a lado. Se o 1^circ 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 n vagas?

Passo 1

O enunciado pede o número de modos de estacionar n carros numerados pela ordem de chegada em n 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 k, com 1<= k<= n. A partir daí as vagas ocupadas formam um bloco contínuo que tem extremidades nos índices a e b. Inicialmente a=b=k. Cada carro seguinte amplia esse bloco ou para a esquerda (movimento L) ou para a direita (movimento R), desde que não ultrapasse os limites 1 e n. Para preencher todas as vagas, é preciso fazer exatamente k-1 movimentos L (para ocupar as vagas à esquerda de k) e n-k movimentos R. Qualquer permutação desses n-1 movimentos leva a uma sequência de estacionamento válida, logo, dado k, o número de modos é
binom,n-1,,k-1,,

Passo 3

Agora somamos sobre todas as escolhas possíveis de k para o primeiro carro:
sumk=1^nbinomn-1k-1 =sumi=0^n-1binomn-1i =2^,n-1,

Resposta

2^,n-1

Exercícios de Livros Relacionados