Consider the following problem:
On a train route of 18 stations, in how many ways can a train stop at 4 stations so that there are at least 2 and at most 6 stations between any two of them?
The above is the problem I have a question about. Meanwhile, consider another similar problem:
A box contains 10 red, 12 yellow and 8 green balls. In how many ways can 14 balls be selected if at least one ball of each colour must be selected?
The above is a sticks-and-stars problem with an upper bound on the number of stars between two sticks. We can reduce the above problem to permuting 2 sticks (3 colours) and 11 stars (taking 1 red, 1 yellow and 1 green ball of the 14 required). The total number of permutations is $13 \choose 2$. From this we subtract the illegal cases like the one below:
$$**********|*|$$
where the space to the left of the first stick represents red balls. Note that there are 10 stars here, but we clearly have only 9 red balls in our budget. There are two ways this particular illegal case could arise, and we can find them by permuting everything to the right of the first stick (there are $2 \choose 1$ permutations). Another illegal case:
$$***********\space |\space |$$
Total number of permutations of this illegal case = $1 \choose 1$
We can repeat the above process for green balls, of which we can take only 7. (Everything to the left of the first stick is green balls now). The total number of permutations where there are more than 7 green balls is ${4 \choose 1} + {3 \choose 1} + {2 \choose1} + {1\choose 1} $.
Finally, we subtract the number of illegal permutations from the number of total permutations to get: $${13 \choose 2} – {2 \choose 1} – {1 \choose 1} – {4 \choose 1} – {3 \choose 1} – {2 \choose 1} – {1 \choose 1} = 65 \text{ legal cases}$$
My teacher uses the binomial expansion to solve most combinatorial problems, including this one (he finds the coefficient of a particular power of $t$ in a specific $p(t)$). I do not like his method as it is not at all intuitive. However, my own approach works only because the order of the sticks wasn't important (we deemed everything to the left of the first stick to be red balls in the first case and green balls in the other). It will not work when counting stations.
To illustrate what I mean, consider the below:
Take away 6 stations from 18, since there must at least be 2 stations between each of the 4 selected stations. Now, our problem simplifies to: let the four stations be represented by sticks and the stations between them be stars; find the number of permutations where there are between zero and four stars between any two sticks. For example, these are allowed:
$$*|**|**|**|*$$ $$*****|*|**||$$
But this is not allowed: $$|******|**||$$
How do I modify my method to solve this problem? Other combinatorial approaches are also appreciated.
Best Answer
If $x_1,\ldots,x_5$ are the numbers of stars before the first bar, between consecutive bars, and after the last bar, we want the number of solutions in non-negative integers to the equation
$$x_1+x_2+x_3+x_4+x_5=8$$
subject to the conditions that $x_2,x_3,x_4\le 4$. This can be solved as an inclusion-exclusion problem. Without the limits on $x_2,x_3$, and $x_4$ there are $\binom{12}4$ solutions. How many solutions exceed the limit on $x_2$?
To count those, we can assume that $x_2\ge 5$, replace it by $y_2=x_2-5$, and count solutions in non-negative integers to
$$x_1+y_2+x_3+x_4+x_5=3\,,$$
of which there are $\binom74$. The same goes for $x_3$ and $x_4$, so a better approximation to the desired result is $\binom{12}4-3\binom74$. And in fact this is the desired result, since it is impossible for more than one of $x_2,x_3$, and $x_4$ to exceed its limit: there are
$$\binom{12}4-3\binom74=495-3\cdot 35=390$$
solutions meeting the stated conditions.