Análise Combinatória

Uma rua possui um estacionamento em fila com N vagas demarcadas junto ao meio-fio de um dos lados. N automóveis, numerados de 1 a N, devem ser acomodados, sucessivamente, pela ordem numérica no estacionamento. Cada carro deve justapor-se a um carro já estacionado, ou seja, uma vez estacionado o carro 1 em qualquer uma das vagas, os seguintes vão se colocando imediatamente à frente do carro mais avançado ou atrás do carro mais recuado. Quantas configurações distintas podem ser obtidas desta maneira?

Conheço 2 maneiras de resolver esse exercício. Vou te ensinar a que eu mesmo criei por não entender a outra na época hahaha. Suponha que você colocou todos carros de todas formas possíveis e gravou tudo isso com uma câmera. Agora, você vai passar o filme para trás. O que verá? Verá um carro saindo de uma ponta e depois outro de outra (ou da mesma) ponta e assim sucessivamente, sempre saindo das pontas. Ora, o número de modos que esses carros podem ser retirados é o mesmo dos que podem ser colocados, afinal só está se passando o filme para trás. Para o primeiro carro que vais retirar, deve escolher ponta esquerda ou direita: 2 modos, para o segundo a mesma coisa, 2 modos, e assim por diante. Para os n-1 primeiros carros, há 2 modos de escolher: o da ponta à esquerda ou a direita. O último só pode ser tirado de 1 modo, logo, a resposta é 2^(n-1).

SENSACIONAL!!!Muito obrigada

Não concordo plenamente com o raciocínio do Ashitaka, então postarei a minha.

Se temos n carros para se colocar em n posições, é fácil ver que a soma dos carros a direita e a esquerda do primeiro carro é constante e igual a (n-1).
Um exemplo EEEEEECDDDDD....D.
Arranjo com combinação!
Ao fazer o somatório, verifica-se que o mesmo é igual a soma dos binômios (n-1).

Suponha que o primeiro carro estacione na i-ésima posição. A esquerda dele temos (n-1) possibilidades, mais a esquerda (n-2), e assim vai até a primeira posição em que temos n-(i-1)=n-i+1 possibilidades. O produto disso é (n-1)(n-2)...(n-i+1), que se multiplicarmos no numerador e denominador por (n-i)! obtemos (n-1)!/(n-i)!. O que é estranho aqui é que a questão quer eu divida por (i-1)! pra desconsiderar a posição dos carros a esquerda do primeiro carro (é uma questão do capítulo de combinações do Morgado), o que deveria ser informado no enunciado! Continuando, ao desprezar as permutações dos carros a esquerda do primeiro carro temos 
\frac{(n-1)!}{(i-1)!(n-i)!}=\binom{n-1}{i-1}.
Como a questão também não quer considerar a organização dos carros a direita do primeiro, há somente (n-i)!/(n-i)!=1 possibilidade de colocar os carros a direita, então fica \binom{n-1}{i-1} \cdot 1. Mas isso é somente pra i-ésima posição, agora temos que considerar as possibilidades em que o primeiro carro vai pra posição 1,2,...(i-1),i,...(n-1),n. A soma das possibilidades é, portanto
\binom{n-1}{0}+\binom{n-1}{1}+...+\binom{n-1}{i-2}+\binom{n-1}{i-1}+...+\binom{n-1}{n-2}+\binom{n-1}{n-1}=2^{n-1} (a soma é facilmente determinada se olharmos o triângulo de Pascal)
Nota: os binômios acima calculam as combinações dos elementos à esquerda do primeiro carro, por isso vai de 0 até n-1.