#2 Inclusion-Exclusion

By inclusion-exclusion, the answer is \(18+14-6=26\). The six students studying both languages were counted twice, so subtract them once.

There are \(\left\lfloor\frac{200}{3}\right\rfloor=66\) multiples of \(3\), and \(40\) multiples of \(5\). Multiples of both, i.e. of \(15\), number \(13\). The answer is \(66+40-13=93\).

There are \(4^6\) words in total. Without \(A\), each position has \(3\) choices, so \(3^6\) words. The answer is \(4^6-3^6=4096-729=3367\).

There are \(3^5\) words. If a chosen letter is missing, there are \(2^5\) words, and \(3\) choices of the missing letter. If two chosen letters are missing, there is \(1^5\) word, with \(3\) choices; add these back. The answer is \(3^5-3\cdot2^5+3=150\).

By inclusion-exclusion, \(4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!=24-24+12-4+1=9\).

The number divisible by at least one of \(2,3,5\) is \(500+333+200-166-100-66+33=734\). Therefore the number divisible by none of them is \(1000-734=266\).

There are \(3^6\) functions in total. Subtract functions missing a chosen value: \(3\cdot2^6\). Add back functions missing two chosen values: \(\binom32\cdot1^6\). The answer is \(3^6-3\cdot2^6+3=540\).

Without restrictions, \(8!\). If chosen \(i\) among \(1,2,3\) are fixed, the remaining \(8-i\) elements are permuted freely. The answer is \(8!-\binom31 7!+\binom32 6!-\binom33 5!=27240\).

If \(i\) elements are chosen to be fixed, the remaining \(n-i\) elements can be permuted in \((n-i)!\) ways. By inclusion-exclusion,

\[D_n=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.\]

First choose the \(2\) fixed points: \(\binom72=21\). The remaining \(5\) elements must have no fixed points, so they can be permuted in \(D_5=44\) ways. The answer is \(21\cdot44=924\).

There are \(10^8\) strings. If one of the three digits is missing, there are \(9^8\) strings; \(3\) choices. If two are missing, there are \(8^8\) strings; \(3\) choices. If all three are missing, \(7^8\). The answer is \(10^8-3\cdot9^8+3\cdot8^8-7^8\).

By inclusion-exclusion:

\[6!-\binom41 5!+\binom42 4!-\binom43 3!+\binom44 2!=720-480+144-24+2=362.\]

There are \(m^n\) functions in total. If \(i\) values are chosen to be unused, then all \(n\) domain elements must map to the remaining \(m-i\) values: \((m-i)^n\) functions. The \(i\) unused values can be chosen in \(\binom mi\) ways. Alternating signs by inclusion-exclusion gives the formula.

Choose the \(k\) elements that will be fixed: \(\binom nk\) ways. The remaining \(n-k\) elements must have no fixed points among their positions; otherwise there would be more than \(k\) fixed points. This can be done in \(D_{n-k}\) ways. The result is \(\binom nkD_{n-k}\).

In a derangement, element \(1\) goes to position \(j\ne1\), giving \(n-1\) choices. Consider element \(j\). If \(j\) goes to position \(1\), the remaining \(n-2\) elements form a derangement: \(D_{n-2}\) ways. If \(j\) does not go to position \(1\), after merging the roles of positions \(1\) and \(j\), the problem reduces to a derangement of \(n-1\) elements: \(D_{n-1}\) ways. Hence \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

There are \(5!=120\) permutations. One violation fixes one cell and gives \(4!\) permutations; there are \(3\) such violations, so subtract \(72\). Two violations are compatible only for the pair \((1,2)\) and \((2,1)\). The pair \((1,1),(1,2)\) is impossible because \(\pi(1)\) cannot be both \(1\) and \(2\). The pair \((1,1),(2,1)\) is impossible because two values cannot both land in \(1\). The compatible pair gives \(3!\) permutations. A triple violation is impossible. The answer is \(120-3\cdot24+6=54\).

In the formula for \(|A_1\cup\cdots\cup A_m|\), an object lying in exactly \(r\) sets is counted \(\binom r1\) times in the single sums, \(\binom r2\) times in pairwise intersections, and so on. Its total contribution is \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). This equals \(1-(1-1)^r=1\). Hence every object in the union is counted exactly once.

Let \(A_j\) be the event that element \(j\) is fixed, for \(j=1,\ldots,r\). If \(i\) such events are chosen, then \(i\) elements are fixed and the remaining \(n-i\) can be permuted in \((n-i)!\) ways. By inclusion-exclusion, the number of permutations avoiding these \(r\) events is \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).

Each distribution is a function from the set of balls to the set of boxes. Requiring every box to be nonempty means the function is onto. By inclusion-exclusion, the number is

\[\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n.\]

Here \(i\) is the number of chosen boxes declared empty.

Apply inclusion-exclusion to the forbidden events: “an element is fixed” and “a pair forms a transposition”. If \(i\) fixed elements and \(j\) disjoint transpositions are chosen, the forbidden structure can be chosen in \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) ways. The remaining \(n-i-2j\) elements are permuted freely in \((n-i-2j)!\) ways. The sign is \((-1)^{i+j}\). Hence the number is

\[\sum_{\substack{i,j\ge0\\ i+2j\le n}}(-1)^{i+j}\frac{n!}{i!\,j!\,2^j}.\]