There are 8 Broadway musicals and they offer a special three-night package (Friday, Saturday, Sunday nights) where one can order one ticket that is good for 3 different musicals on successive nights (a sequence of three different musicals). A travel agent plans to order $30$ of these tickets for a tour group of $30$ people. How many ways are there to order a subset of $30$ such tickets with the constraint that each of the eight musicals appears on at least one ticket?
My work: I have no idea how to even approach this problem. I know I should use Pascals formula but I'm not sure how. $P(C(8,3),30)$?
$\underline{Summary:}$
Count the number of ways for the agent to order the tickets without restrictions, then count the number of those ways that break the rule and subtract. To count the number of ways that break the rule, apply the principle of inclusion-exclusion to change it to a sum where all of the terms are easily computable.
$\underline{More \ Detail:}$
Use Complimentary counting:
The number of ways for the travel agent to order the tickets according to the condition is the number of ways for the travel agent to order them without the condition minus the number of ways for the travel agent to order them so that the condition is false.
To find the number of ways to order the tickets without a restriction:
There are $\binom{8}{3}=56$ possible tickets (because the order of the musicals on the tickets don't matter).
The number of ways of choosing 30 of these where order doesn't matter is the number of ways of partitioning 30 into 56 parts, any of which can be 0 (each part corresponds to the number of tickets of that type bought). Using stars-and-bars, this is $\binom{30+55}{55}=\binom{85}{55}$.
To find the number of ways of ordering tickets that break the restriction:
For musical number $i$, let $S(i)$ be the set of ways for the travel agent to order the $30$ tickets such that musical $i$ is not on any ticket.
We want the cardinality of $S(1)\cap S(2)\cup S(3)\cup\dots\cup S(8)$.
By the principle of inclusion-exclusion, we have
\begin{align*} |S(1)\cup S(2)\cup S(3)\cup\dots\cup S(8)|&=|S(1)|+|S(2)|+\dots+|S(8)|\\ &-|S(1)\cap S(2)|-|S(1)\cap S(3)|-\dots\\ &\vdots\\ &-|S(1)\cap S(2)\cap S(3)\cap\dots\cap S(8)|. \end{align*}
For sake of writing less, for each $i$, let $R(i):=S(1)\cap S(2)\cap\dots\cap S(i)$. Then by symmetry (the cardinality of the intersection if $k$ of the $S$ sets does not depend on which sets we choose), we can condense this equation to
$$|S(1)\cup S(2)\cup S(3)\cup\dots\cup S(8)|=\binom{8}{1}|R(1)|-\binom{8}{2}|R(2)|+\binom{8}{3}|R(3)|-\binom{8}{4}|R(4)|+\binom{8}{5}|R(5)|-\binom{8}{6}|R(6)|+\binom{8}{7}|R(7)|-\binom{8}{8}|R(8)|.$$
$\underline{|R(1)|}$
$|R(1)|$ is the number of ways to choose the 30 tickets so that the first musical is not on any of them. This is the same as the number of ways to choose the tickets as if there were only 7 musicals and no restrictions. Using the same method as earlier, we have:
$\binom{7}{3}=35$ possible tickets
$\binom{30+34}{34}=\binom{64}{34}$ ways of ordering the tickets.
We can use a similar method for the rest.
$\underline{|R(2)|}$
$\binom{6}{3}=20$ possible tickets
$\binom{30+19}{19}=\binom{49}{19}$ ways of ordering the tickets.
$\underline{|R(3)|}$
$\binom{5}{3}=10$ possible tickets
$\binom{30+9}{9}=\binom{39}{9}$ ways of ordering the tickets.
$\underline{|R(4)|}$
$\binom{4}{3}=4$ possible tickets
$\binom{30+3}{3}=\binom{33}{3}$ ways of ordering the tickets.
$\underline{|R(5)|}$
$\binom{3}{3}=1$ possible ticket
$\binom{30+0}{0}=\binom{30}{0}$ ways of ordering the tickets. This also equals 1, but for consistency I'll leave it as $\binom{30}{0}$.
The rest will be 0; you can see this either by noting that you can't create any tickets where 6 musicals never show up on any ticket because that leaves only 2 musicals left, or you can see this by doing the computation.
So the number of tickets that break the restriction is
$$\binom{8}{1}\binom{64}{34}-\binom{8}{2}\binom{49}{19}+\binom{8}{3}\binom{39}{9}-\binom{8}{4}\binom{33}{3}+\binom{8}{5}\binom{30}{0}-\binom{8}{6}0+\binom{8}{7}0-\binom{8}{8}0=12,961,776,248,932,512,568.$$
Then our final answer is
$$\binom{85}{55}-12,961,776,248,932,512,568=83,636,299,864,772,749,216,808.$$
For comparison, $\binom{85}{55}=83,649,261,641,021,681,729,376$ which is pretty close, which makes sense because almost all ways of ordering the tickets should satisfy the condition.