#2 Метод включений-исключений

По формуле включений-исключений получаем \(18+14-6=26\). Шесть учеников, изучающих оба языка, были посчитаны дважды, поэтому их надо вычесть один раз.

Чисел, делящихся на \(3\), ровно \(\left\lfloor\frac{200}{3}\right\rfloor=66\). Делящихся на \(5\) — \(40\). Делящихся на оба, то есть на \(15\), — \(13\). Ответ: \(66+40-13=93\).

Всего слов \(4^6\). Без буквы \(A\) каждую позицию можно заполнить \(3\) способами, всего \(3^6\). Ответ: \(4^6-3^6=4096-729=3367\).

Всего \(3^5\) слов. Если отсутствует выбранная буква, остаётся \(2^5\) слов, таких выборов \(3\). Если отсутствуют две выбранные буквы, остаётся \(1^5\) слово, таких выборов \(3\), и эти слова надо вернуть. Ответ: \(3^5-3\cdot2^5+3=150\).

По включениям-исключениям получаем \(4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!=24-24+12-4+1=9\).

Чисел, делящихся хотя бы на одно из \(2,3,5\), равно \(500+333+200-166-100-66+33=734\). Поэтому не делящихся ни на одно из них \(1000-734=266\).

Всего функций \(3^6\). Вычитаем функции, пропускающие выбранное значение: \(3\cdot2^6\). Возвращаем функции, пропускающие два выбранных значения: \(\binom32\cdot1^6\). Ответ: \(3^6-3\cdot2^6+3=540\).

Без ограничений \(8!\). Если выбранные \(i\) из чисел \(1,2,3\) стоят на своих местах, остальные \(8-i\) элементов переставляются свободно. Ответ: \(8!-\binom31 7!+\binom32 6!-\binom33 5!=27240\).

Если выбраны \(i\) элементов, которые должны быть неподвижны, то остальные \(n-i\) элементов можно переставить \((n-i)!\) способами. По включениям-исключениям

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

Сначала выбираем \(2\) неподвижные точки: \(\binom72=21\). Остальные \(5\) элементов должны не иметь неподвижных точек, их можно переставить \(D_5=44\) способами. Ответ: \(21\cdot44=924\).

Всего строк \(10^8\). Если отсутствует одна из трёх цифр, остаётся \(9^8\) строк; таких запретов \(3\). Если отсутствуют две из них, остаётся \(8^8\) строк; таких пар \(3\). Если отсутствуют все три, \(7^8\). Ответ: \(10^8-3\cdot9^8+3\cdot8^8-7^8\).

По включениям-исключениям:

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

Всего функций \(m^n\). Если выбраны \(i\) значений, которые не используются, то все \(n\) элементов области должны перейти в оставшиеся \(m-i\) значений: \((m-i)^n\) функций. Выбрать такие \(i\) значений можно \(\binom mi\) способами. Чередуя знаки по включениям-исключениям, получаем формулу.

Выбираем \(k\) элементов, которые будут неподвижными: \(\binom nk\) способов. Остальные \(n-k\) элементов должны не иметь неподвижных точек среди своих позиций, иначе неподвижных точек было бы больше \(k\). Это можно сделать \(D_{n-k}\) способами. Получаем \(\binom nkD_{n-k}\).

В беспорядке элемент \(1\) переходит на место \(j\ne1\), \(n-1\) вариантов. Рассмотрим элемент \(j\). Если \(j\) переходит на место \(1\), то остальные \(n-2\) элементов образуют беспорядок: \(D_{n-2}\) способов. Если \(j\) не переходит на место \(1\), то после объединения мест \(1\) и \(j\) задача сводится к беспорядку \(n-1\) элементов: \(D_{n-1}\) способов. Итого \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

Всего \(5!=120\). Одно нарушение фиксирует одну клетку, даёт \(4!\) перестановки; таких нарушений \(3\), вычитаем \(72\). Два нарушения совместимы только для пар \((1,2)\) с \((2,1)\) и \((1,1)\) с? Условия \((1,1)\) и \((1,2)\) несовместимы, потому что \(\pi(1)\) не может быть сразу \(1\) и \(2\). Условия \((1,1)\) и \((2,1)\) тоже несовместимы, потому что два значения не могут попасть в \(1\). Совместима только пара \((1,2),(2,1)\), она даёт \(3!\) перестановок. Тройное нарушение невозможно. Ответ: \(120-3\cdot24+6=54\).

В формуле для \(|A_1\cup\cdots\cup A_m|\) объект, лежащий ровно в \(r\) множествах, учитывается \(\binom r1\) раз в одиночных суммах, \(\binom r2\) раз в попарных пересечениях, и так далее. Его общий вклад равен \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). Это равно \(1-(1-1)^r=1\). Значит, каждый объект объединения учитывается ровно один раз.

Пусть \(A_j\) — событие, что элемент \(j\) стоит на своём месте, для \(j=1,\ldots,r\). Если выбраны \(i\) таких событий, то \(i\) элементов фиксированы, а остальные \(n-i\) можно переставить \((n-i)!\) способами. По включениям-исключениям число перестановок без этих \(r\) событий равно \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).

Каждое распределение — функция из множества шаров в множество коробок. Требование, чтобы каждая коробка была непуста, означает сюръективность. По формуле включений-исключений получаем

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

Здесь \(i\) — число выбранных коробок, которые объявлены пустыми.

Применим включения-исключения к запрещённым событиям: “элемент фиксирован” и “пара образует транспозицию”. Если выбраны \(i\) фиксированных элементов и \(j\) непересекающихся транспозиций, то сначала выбираем эти элементы и пары: \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) способов для структуры запретов. Остальные \(n-i-2j\) элементов переставляются произвольно: \((n-i-2j)!\) способов. Вклад имеет знак \((-1)^{i+j}\). Поэтому число равно

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