Inclusion-Exclusion and Generating Function with Coefficient (and Integer Equation)

Problem 1:

First we choose $5$ distinct special characters out of the $9$ available, taking the order into account: there are $9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 9!/4!$ ways to do so. Then we choose the remaining characters, taking the order into accout: for each character we have $26+26+10 = 62$ choices, so the total is $62^{15}$. But, among these, there are $52^{15}$ passwords with no numbers which we should get rid of. By the inclusion-exclusion principle (actually, just exclusion here), there are $62^{15} - 52^{15}$ ways to do so.

Now let's count the possible ways to choose the positions of the special characters so that no special character is in the first position and there are at least two consecutive special characters. Here we will use inclusion-exclusion.

The total number of possible choices, no restriction, is $\binom{20}{5}$. The ones that start with a special character are $\binom{19}{4}$, as we fix that the first character is special. Fixed the first character, the number of choices for the remaining $19$ such that the second character is not a special character, and no two special characters are consecutive, is $\binom{14}{4}$: think of it as each special character "reserving" the position immediately before it for a non-special character, so that we are equivalently choosing how to insert $4$ pairs of characters (the first non-special, the second special) in a string composed of the remaining $10$ characters. If we subtract the set of these strings from the ones we had before, the remaining strings are the ones that start with a special character, and for which either the second character is special (so they do have two consecutive special characters), or they have at least two consecutive special characters somewhere else.

The total number of choices is then \[ \frac{9!}{5!} (62^{15} - 52^{15}) \left( \binom{19}{4} - \binom{14}{4} \right) \]

If you want to make inclusion-exclusion more explicit, just expand the parentheses: you will get four sets, $S_1$ given by the factors $62^{15}$ and $\binom{19}{4}$, counting all the strings that have $5$ special characters, one in first position; $S_2$ given by the factors $52^{15}$ and $\binom{19}{4}$, counting all the strings that have $5$ special characters, one in first position, and at least one number; $S_3$ given by the factors $62^{15}$ and $\binom{14}{4}$, counting all the strings that have $5$ special characters, one in first position, and of which at least two are consecutive; $S_4$ given by the factors $52^{15}$ and $\binom{49}{4}$, counting all the strings that have $5$ special characters, one in first position, of which at least two are consecutive, and at least one number. By inclusion-exclusion the answer will be $\# S_1 - \# S_2 - \# S_3 + \# S_4$, exactly the same as before.

Problem 2:

For each project, we compute a generating function (it will actually be a polynomial) giving the number of possible choices: the product of these polynomials will give the generating function we want.

Project teams 3 and 7 have exactly 8 students, so the polynomial is $x^8$.

Project teams 1, 2, and 12 have no more than 5 students, so the polynomial is $1+ x+x^2+x^3+x^4+x^5 = \frac{x^6-1}{x-1}$.

Project teams 4, 9, 10, and 11 have at least 3 students, but strictly less than 9 students, so the polynomial is $x^3+x^4+x^5+x^6+x^7+x^8 = x^3 \frac{x^6-1}{x-1}$.

Project teams 5, 6, and 8 have at least 4 students but strictly less than 16 students, so the polynomial is $x^4+x^5+\dots+x^{16} = x^4 \frac{x^{13}-1}{x-1}$.

Our generating function is \[ (x^8)^2 \left( \frac{x^6-1}{x-1} \right)^3 \left( x^3 \frac{x^6-1}{x-1} \right)^4 \left( x^4 \frac{x^{13}-1}{x-1} \right)^3 = x^{40} \left( \frac{x^6-1}{x-1} \right)^7 \left( \frac{x^{13}-1}{x-1} \right)^3 \] of which we want to compute the coefficient of $x^{46}$.

Equivalently, we want the coefficient of $x^6$ in \[ (x^6 - 1)^7(x^{13} - 1)^3(1+x+x^2+\dots)^{10} \] and we can extract it from either $(x^6 - 1)^7$ (in $7$ ways, with a minus sign coming from $(x^{13} - 1)^3$), or from (1+x+x^2+\dots)^{10} (in $\binom{10+5}{6}$ ways, with a plus sign).

To be more precise, the function expands as \[ (-1 + 7x^6 + o(x^6)) (-1 + o(x^6)) (1 + \dots + \binom{15}{6}x^6 + o(x^6)) \] the omitted part not counting as it is multiplied either by $1$ or by $x^6$ at least. Since $o(x^6)$ can be ignored, we obtain the same result as above, namely \[ \binom{15}{6} - 7 = 5005-7 = 4998. \]