How many possible orders can the first Los Santos missions of GTA: San Andreas be completed in?

Question

This is actually a pretty interesting combinatorics problem, as there's several different branches in the mission tree that split off and join together, and of course there are prerequisites for each mission. Essentially what I'm wondering is - how many possible ways are there to get from Nines And AK's to Reuniting The Families? I attached a screenshot of that part of the mission tree for reference. LOS SANTOS MISSION TREE

NOTE: For those who have never played the game, ALL missions in the ENTIRE tree must be completed before Reuniting The Families. Each line coming from the bottom of a box leads to the mission(s) that are unlocked after that one, and each line from the top of a box leads to the mission(s) that must be completed before it.

Answer 1

This is almost an easy problem with a nice solution.

If "Burning Desire" weren't a prerequisite for "Doberman", then the graph of missions would be a series-parallel graph. For these, the problem of counting the number of orders is very easy. Suppose you have series-parallel graphs $G_1, G_2$ with $n_1+2, n_2+2$ vertices and we've computed that there's $\tau_1, \tau_2$ ways to order them respectively. Then:

• If we join $G_1$ and $G_2$ in series, then all vertices of $G_1$ need to come before all vertices of $G_2$, so there are $\tau_1 \cdot \tau_2$ orders.
• If we join $G_1$ and $G_2$ in parallel, then we can interleave the vertices of $G_1$ and $G_2$ in any of $\frac{(n_1+n_2)!}{n_1!\,n_2!}$ ways, for $\frac{(n_1+n_2)!}{n_1!\,n_2!} \cdot \tau_1 \cdot \tau_2$ orders.

Just a few of these steps would have given us the total number of orders of the Los Santos missions, which is a quick process you could almost do by hand (but probably want a calculator to evaluate the final answer): it is $$\binom{19}{9} \binom{4}{2} \binom{9}{3} \binom{3}{1} \binom{8}{3} = 7\,821\,830\,016.$$ Each of these binomials corresponds to joining two graphs in parallel, where we interleave two independent branches. For instance, the $\binom93$ corresponds to the number of ways to interleave the 3 leftmost missions (Running Dog, Wrong Side of the Tracks, and Just Business) with the 6 other missions on the left side of the diagram.

Also, if we just want a quick estimate of the final answer, then the above over-estimates it by about a factor of $2$: roughly (but not exactly) half the time, you'll be counting orders that put Doberman before Burning Desire, which are not valid.

---

Unfortunately, we can't get the exact answer this way, and must resort to brute force. The following Mathematica code implements one such strategy:

• Find the list of missions that can be done without prerequisites: Pick[VertexList[graph], VertexInDegree[graph], 0]
• For each of those missions, s, recursively compute the number of ways to do the rest of the missions if you do s first: topCount[VertexDelete[graph, s]].

Here's the code.

topCount[graph_] := topCount[graph] = 
  Total[Table[
    topCount[VertexDelete[graph, s]],
    {s, Pick[VertexList[graph], VertexInDegree[graph], 0]}
  ]];

Applying this Mathematica function to this graph gives a final answer of $4\,303\,018\,512$.

Answer 2

While it’s true that the calculation would have been easier if “Burning Desire” weren’t a prerequisite for “Doberman”, that doesn’t mean we have to resort to brute force. We can correct for this in a few steps.

As Misha Lavrov noted, the number of orders without this constraint would have been

$$ \binom42\binom96\binom31\binom83\binom{19}9=7821830016\;. $$

From this we have to subtract the number of orders in which “Doberman” precedes “Burning Desire”. We can visualize this in the graph by removing the line from “Burning Desire” to “Doberman” and instead adding a line from “Doberman” to “Burning Desire”. The resulting graph is again almost a series-parallel graph, but again there’s one prerequisite that messes things up – in this case it’s the constraint that “Madd Dogg’s Rhymes” comes before “Burning Desire”.

So we use the same approach again and first count without satisfying that constraint; the result is

$$ \binom74\binom31\binom51\binom{10}3\binom{19}{11}=4761666000\;. $$

So we have to subtract that from the first result; but then we’ve subtracted too much because this includes orders in which “Burning Desire” comes before “Madd Dogg’s Rhymes”. So we have to remove the line from “Madd Dogg’s Rhymes” to “Burning Desire” and instead draw one from “Burning Desire” to “Madd Dogg’s Rhymes”. Now it’s the line from “Life’s a Beach” to “Madd Dogg’s Rhymes” that gets in the way. Removing that would leave “Life’s a Beach” hanging in the air, so we connect it to ”Reuniting the Families” instead. The resulting count is

$$ \binom41\binom41\binom61\binom81\binom{13}3\binom{19}5=2554066944\;. $$

Now we have to draw a line from “Madd Dogg’s Rhymes” to “Life’s a Beach”. Now the line from “OG LOC” to “Life’s a Beach” is the problem, so we remove it, which leads to a count of

$$ \binom31\binom51\binom71\binom91\binom{14}3\binom{19}4=1333266480\;. $$

Now we draw a line from “Life’s a Beach” to “OG LOC”, and this time the resulting graph is series-parallel – it merely has a redunant line from “Lines and AK's” to “OG LOC” that we can remove without having to compensate for it. The resulting contribution is

$$ \binom72\binom91\binom{11}1\binom{13}1\binom{18}3=22054032\;. $$

Thus, altogether we count

$$ 7821830016-(4761666000-(2554066944-(1333266480-22054032)))=4303018512 $$

different orders, in agreement with Misha Lavrov’s count.