Combinatorics: How many distinct ways can a Ford, Chevy, Toyota, and VW go thru three distinct toll booths? NB: Order of going thru matters I am trying to solve this problem of Combinatorics. Can you help me?
Here is the problem:
How many distinct ways can a Ford, Chevy, Toyota, and VW go thru three distinct toll booths? NB: Order of going thru matters
Here is my solution:
I will call F. C, T and V, the four cars.
Also, I will call X, Y, and Z the three tolls.
Finally, I will call 1, 2, 3 and 4 the first, second, third, and fourth position.
Important: I am assuming position as the first car that arrives to the tolls, second car that arrives to the tolls, etc.
For the first position, there are (4 cars * 3 tolls)= 12 options:
FX1, FY1, FZ1, CX1, CY1, CZ1, TX1, TY1, TZ1, VX1, VY1, VZ1.
For the second position, (3 cars * 3 tolls)= 9 options.
For the third position, (2 cars * 3 tolls)= 6 options.
For the last position, (1 car  *3 tolls)= 3 options.
Finally, by the multiplication principle, 12*9*6*3 = 1944 options.
A friend adviced me to see it as a list-problem.
Would be correct to think in this way?
We would have P(4,4)= 4! lists of cars WITHOUT repetions.
We would also have 3^4 lists of tolls WITH repetions.
Finally, by the multiplication principle, (4! * 3^4) = 1944
My professor told me that I am wrong...
May you explain me why? Or am I right?
Thank you so much for your help!
 A: Your idea of "positions" would only work if only 1 car could got through any one of the booths at a time.  But that's not the case.  FX1 & CY2 is the same event as FX2 & CY1 (for example).  
Break up the problem into 7 problems:


*

*some car will go through each one of the booths X,Y,Z

*some car will go through 2 booths, but no car will go through 1 of the booths.  This can be split into 3 problems (no car goes through X, no car goes through Y, no car goes through Z).

*Some car will go through 1 booth and no car will go through 2 of the booths.  This can be split into 3 problems in the same way as (2).


Without loss of generality you can solve (2) and (3) for only 1 of the subproblems and then multiply the result by 3 (because the result for the other 3 situations will yield the same number of scenarios).
In case of (1), there is 4*3*2 possibilities for the 1st wave of cars going through the booths (4 choices for 1st car going through X; for each choice of X, 3 remaining choices for 1st car going through Y; for each choice of X,Y, 2 remaining choices for 1st car going through Z).  And then the remaining car (for each choice of 1st cars going through X,Y,Z) will have 3 booths where it can be the 2nd car.  So the total number of events for problem (1) is 4*3*2*3 = 72.
For the 2nd problem, assume (without loss of generality) that only X,Y booths will be used.  Then 1st cars have to go through them have 4*3 possibilities.  The 2 remaining cars can go through X,Y or they can both go only through X or only through Y.  The order of the cars matters.  Because CX3 & FX4 is not the same even as CX4 & FX3.  This means the total number of possibilities is 4*3*(2*1 + 2*1 + 2*1): (for example) CX3 & FY3, CY3 & FX3, CX3 & FX4, CX4 & FX3, CY3 & FY4, CY4 & FY3.  4*3*(2*1 + 2*1 + 2*1) = 72.  
But remember that this is only 1/3 of all possible problem (2) solutions because we could have excluded booth X or Y instead of Z.  So the total number of solutions for (2) is 72*3=216.
For problem (3), it's just a permutation of the orders in which the cars will go through 1 booth: 4*3*2*1.  But (since we can pick any one of the 3 booths to be the booth to use), it's 4*3*2*1 * 3 = 72.
And since all of these orders are distinct, their total number is 72 + 216 + 72 = 360.
A: Your professor is saying you are double counting many cases.  In your second approach, the Ford could arrive first and go through booth 1, then the Chevy arrives second and goes through booth 2, the Toyota arrives third and goes through booth 3, and finally the VW arrives fourth and goes through booth 1.  Your professor is counting all six orders of arrival of the first three cars as equivalent as long as they go through the designated booths.  The VW can also arrive earlier as long as it arrives after the Ford.  You can think of each booth making a list of the cars it saw in order but there is no time reference between the lists.  We are asked how many sets of lists there are.
We have to break it into cases.
If they all go through the same booth, there are $3$ ways to choose the booth and $4!$ orders for a total of $72$.
If they go three through one booth and one through another, there are $6$ ways to choose the booths, $4$ ways to choose the odd car, and $6$ ways to order the three cars for $144$.
If they go two through each of two booths, there are $3$ ways to choose the booth used by the Ford, $2$ ways to choose the other booth, $3$ ways to choose the car that uses the same booth as the Ford, and $4$ orders for the cars through the booths, total $72$.
If the go through two, one, and one there are $3$ ways to choose the booth that gets two cars, $12$ ways to put cars in order through that booth, and $2$ ways to assign the other cars to the other booths, total $72$.
This gives $360$ total ways.
A: What counts for right or wrong here depends on your interpretation of the problem.  The OP views the four cars approaching a toll plaza one after another, with each car choosing one of three booths, with the result being an ordered list of which car goes through which booth -- think of it as an outside observer recording what she sees.  Ross Millikan, on the other hand, has each toll booth record its own, separate, list of what passes through it, with, say a supervisor then collecting the three lists.  There is no way to tell which (if either!) of these is the intended interpretation without some additional context.
Just to show how ambiguous things are, I'll argue that the "right" answer is $(4!)^3=13{,}824$.  In my interpretation, the toll booths are not at a single toll plaza, with cars fanning out to pass through them, but each one at its own single-booth plaza dotted along the highway.  The four cars arrive in any order at the first, then race one another to the second, and race one another again to the third.  After all, the statement of the problem suggests that each car goes through each toll booth; it doesn't say anything about each car choosing a booth to go through.
A: I present a verification of the argument by @RossMillikan for future reference. We have the labeled combinatorial species
$$\mathfrak{S}(\mathcal{Z})\mathfrak{S}(\mathcal{Z})\mathfrak{S}(\mathcal{Z}).$$
which represents a sequence of distinct cars at each of the three distinct toll booths. This yields the EGF
$$\frac{1}{(1-z)^3}.$$
Extracting the coefficient on $[z^4]$ we find
$$4! [z^4] \frac{1}{(1-z)^3} = 4! \times {4+2\choose 2}
= 360.$$
A: There a few different ways to interpret the question.
1) Probable intended meaning: the order only matters relative to each tollbooth.
In that case, each possible situation can be represented as a permutation of $FCTV//$ where the slash $/$ represents the boundary between lists. For example, $FC/T/V$ means that the Ford and Chevy went through Tollbooth 1, in that order, the Toyota went through Tollbooth 2, and the Volkswagen went through Tollbooth 3.
The answer is then $\frac{6!}{2!}=360$.
2) Your interpretation: the universal order matters; no two cars pass through different booths simultaneously.
Determine the universal order, then independently decide which car goes through which booth. The answer is then $4!\cdot 3^4=1944$.
3) More interesting interpretation: the universal order matters; different cars can pass through different booths simultaneously.
Let $f_k(n)$ be the number of ways that $n$ cars can go through $k$ booths. Then $f_k(0)=1$ and $$f_k(n)=\sum_{i=1}^{\min(n,k)}i!\tbinom{k}{i}\tbinom{n}{i}f_k(n-i)$$ the idea being that $i$ cars pass at a time.
For $k=3$, we get $1, 3, 24, 276, 4248, ...$ so the answer is $4248$. The exponential generating function for fixed $k$ is $$(2-(x+1)^k)^{-1}$$
