Couldn't find a better answer for this problem. May someone help me, please?
A row of $n$ cars is ready to enter a parking lot with only one row with $n$ spaces side by side. The first car can choose any of the $n$ spaces, but the following vehicles can only park side to another car that is already parked. How many ways all the cars can occupy the empty spaces?
I solved choosing arbitrary values for n and calculating the possible combinations.
Supose $n=3$ and A,B,C are ours cars, being A the first to parking, B the second and C the third. Then the combinations are:
Notation: (I use "/" to separate combinations where A chooses different spaces)
ABC / BAC, CAB/ CBA
Supose $n=4$ and A,B,C,D are ours cars:
ABCD/BACD, CABD, DABC/ DBAC, DCAB, CBAD/ DCBA
Lastly, $n=5$ and A,B,C,D,E are ours cars:
ABCDE /BACDE, CABDE, DABCE, EABCD/ DCABE, DBACE, CBADE, EDABC, ECABD, EBACD/ EDCAB,ECBAD,DCBAE,EDBAC/ EDCAB, ECBAD, DCBAE, EDBAC/ EDCBA
Let $C$ be the number of possible combinations counted above for each n, we have these pairs:
When $n=3$, $C=4$
$n=4$, $C=8$
$n=5$, $C=16$
So then I come up by these results that $C = {2}^{(n-1)}$. These formula works when n=2 and n=1 too, but I'm not sure if it's correct and I know there must be a better way than that.
PS: English is not my first language and I'm new to this forum (2nd post), so please let me know if I did something wrong or if the explanation is too confusing so I can edit it.
Best Answer
Place the first car somewhere in an open row
Now each remaining car can go either just to the left or just to the right of those already parked, yielding # of ways $ =\boxed{2^{n-1}}$
We have now obtained the patterns of a successful parking which has an exact correspondence (bijection) with our $n$ parking slots