0
$\begingroup$

The question is explicitly: "In how many different orders can $n$ cars line up in a gas station of 4 parallel gas pumps?" No more information is provided. I initially assumed that both the pumps and cars are distinguishable.

In these cases, different orders count towards the total number of possible outcomes, and repetition is not allowed since the same car can't be parked in two locations. Would that mean the solution would take the form $P(n,r)$? But that would reduce to $n!$ which is just the number of different arrangements the cars can take in a single line.

Would I just multiply by $4$ to get the number of arrangements if they're distributed across $4$ gas stations?

Instinctively it should look more like

(n - # of cars @ 2,3,4)! + (n - # of cars @ 1,2,4)! + (n - # of cars at 1,2,4)! + (n-# of cars at 1,2,3)!

How can I express this purely in terms of n?

$\endgroup$
  • 1
    $\begingroup$ Are the cars distinguishable? Are the gas stations distinguishable? $\endgroup$ – Bram28 Feb 28 '18 at 23:50
  • $\begingroup$ The question is explicitly: "In how many different orders can n cars line up in a gas station of 4 parallel gas pumps." No more information is provided. I initially assumed they're both distinguishable. $\endgroup$ – Karim Shoorbajee Feb 28 '18 at 23:58
  • $\begingroup$ If gas pumps/cars are distinguishable you can quickly disprove your conjecture of multiplying by 4. This would be if all 4 cars had to line up in the same line. You miss (at least) the event that 3 cars go to pump 1 and 1 car goes to pump 2. $\endgroup$ – Prince M Feb 28 '18 at 23:58
  • $\begingroup$ Yes. I'm pretty confident in my second conjecture but I'm unsure of how I'd express this in terms of n. $\endgroup$ – Karim Shoorbajee Mar 1 '18 at 0:00
  • $\begingroup$ @Bram28 Given the answer for distinguishable cars and stations, aren't the other 3 interpretations of the question answer by dividing by n!,4!, and n!4!, respectively? $\endgroup$ – JKEG Mar 1 '18 at 0:19
3
$\begingroup$

Method 1: We split the $n$ cars into four possibly empty groups, then multiply by the number of ways of lining them up.

The number of ways the cars can be split into four groups is the number of solutions of the equation $$n_1 + n_2 + n_3 + n_4 = n$$ in the nonnegative integers. A particular solution corresponds to the placement of three addition signs in a row of $n$ ones. For instance, if $n = 10$, then $$1 1 + 1 1 1 + + 1 1 1 1 1$$ corresponds to the solution $n_1 = 2$, $n_2 = 3$, $n_3 = 0$, and $n_4 = 5$. The number of solutions of the equation $n_1 + n_2 + n_3 + n_4 = n$ in the nonnegative integers is $$\binom{n + 3}{3}$$ since we must choose which $3$ of the $n + 3$ locations required for $n$ ones and $3$ addition signs will be filled with addition signs. The cars can be lined up in $n!$ orders. Once an order is chosen, we send the first $n_1$ cars to pump 1, the next $n_2$ cars to pump 2, the next $n_3$ cars to pump 3, and the remaining $n_4$ cars to pump 4. Hence, the number of distinguishable ways the $n$ cars can be distributed to the four pumps is $$\binom{n + 3}{3}n!$$

Method 2: The $n$ cars can be lined up in $n!$ ways. However, we also have to choose $3$ points where we divide the line. Hence, we have to arrange $n$ distinguishable cars and $3$ indistinguishable dividers. Hence, we have $n + 3$ objects to arrange. We choose $3$ of those $n + 3$ positions for the dividers, then arrange the $n$ cars in the remaining $n$ positions in $n!$ orders. Therefore, there are $$\binom{n + 3}{3}n!$$ ways to arrange the $n$ cars at the four gas pumps.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. If we just have n+3 items to arrange could you explain why the solution isn't just (n+3)! ? $\endgroup$ – Karim Shoorbajee Mar 1 '18 at 0:31
  • $\begingroup$ This is like arranging the letters of the word TOTTER. There are three Ts, but they are indistinguishable. We choose three of the six positions for the Ts, then arrange the remaining three distinct letters in the remaining positions in $3!$ orders, giving us $\binom{6}{3}3! = 20 \cdot 6 = 120$ distinct arrangements. Alternatively, we can place the O in six ways, the E in one of the remaining five positions in $5$ ways, and the R in one of the remaining four positions in $4$ ways. The remaining three positions must be filled with Ts. There are $6 \cdot 5 \cdot 4 = 120$ arrangements. $\endgroup$ – N. F. Taussig Mar 1 '18 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.