Олимпиадные задачи по комбинаторике. Задача о беспорядках
 Скачать 0.5 Mb.
|
|
раскрыли все скобки и привели подобные слагаемые. Сколько слагаемых получилось? 500501 20. («Высшая проба», 2014, 11 ) В выражении (1 + x)(1 + x 2 )(1 + x 3 ) . . . (1 + x 13 )(1 + x 14 )(1 + x 1000 ) 18 раскрыли все скобки и привели подобные слагаемые. Сколько слагаемых получилось? 2014 21. («Высшая проба», 2014, 9 ) Сколько слагаемых получится после раскрытия скобок и при- ведения подобных слагаемых в выражении (1 + x 2 ) 100 (1 + x 3 ) 100 ? 499 22. («Высшая проба», 2014, 11 ) Сколько слагаемых получится после раскрытия скобок и при- ведения подобных слагаемых в выражении (1 + x 3 ) 100 (1 + x 4 ) 100 ? 695 23. («Физтех», 2014, 9–10 ) Дан выпуклый 15-угольник, никакие три диагонали которого не имеют общих точек, отличных от вершин. Найдите число точек пересечения диагоналей (не считая вершин). 1365 24. («Физтех», 2014, 9, 11 ) Отметили все вершины правильного 12-угольника. Сколько суще- ствует незамкнутых несамопересекающихся семизвенных ломаных с вершинами в отмеченных точках? 33792 25. («Высшая проба», 2013, 9 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , 9 (можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 4? 120 26. («Высшая проба», 2013, 10 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , 9 (можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 5? 231 27. («Высшая проба», 2013, 11 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , 9 (можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 6? 406 33 28. («Физтех», 2014, 9–10 ) На плоскости нарисован круг и три семейства прямых: в одном — 19 параллельных между собой прямых, в другом — 23 параллельных между собой прямых, в третьем — 36 параллельных между собой прямых. На какое наибольшее число частей прямые могут разбить круг? 2028 29. («Физтех», 2013, 10–11 ) Тест по английскому языку сдавали 10 школьников. Известно, что любые пять школьников ответили вместе на все вопросы, а любые четыре школьника отве- тили вместе не на все вопросы. При каком наименьшем количестве вопросов теста такое могло случиться? 210 30. («Высшая проба», 2011, 11 ) Сколькими способами можно раскрасить грани куба в чёрный и белый цвета (каждую грань в один цвет, и оба цвета должны быть использованы)? Раскраски считаются одинаковыми, если одну можно получить из другой, повертев куб в руках. 8 31. («Физтех», 2013, 11 ) Число 84605 написали семь раз подряд, при этом получилось 35- значное число 84605846058460584605846058460584605. Из этого 35-значного числа требуется вычеркнуть две цифры так, чтобы полученное после вычёркивания 33-значное число делилось на 15. Сколькими способами это можно сделать? 216 32. («Физтех», 2013, 11 ) Дан правильный 24-угольник. Найдите количество троек его вершин, являющихся вершинами треугольника, в котором хотя бы один угол равен 45 ◦ . (Две тройки вершин, отличающиеся порядком вершин, считаются одинаковыми.) 384 33. («Физтех», 2013, 11 ) Дан правильный 20-угольник. Найдите количество четвёрок его вер- шин, являющихся вершинами выпуклого четырёхугольника, в котором хотя бы один угол равен 90 ◦ . (Две четвёрки вершин, отличающиеся порядком вершин, считаются одинаковыми.) 765 34. («Физтех», 2014, 11 ) Есть семь карточек с цифрами 0, 1, 2, 2, 3, 4, 5. Сколько существует различных шестизначных чисел, делящихся на 15, которые можно сложить из этих карточек? 276 35. («Физтех», 2014, 11 ) В выпуклом 17-угольнике проводят все его диагонали. На какое наибольшее число частей они могут его разбить? 2500 36. («Физтех», 2011, 10 ) 26 солдат выстроены в одну шеренгу. Сколько существует различных способов выбрать 11 из них так, что никакие двое из них не стоят рядом? 4368 34 37. («Физтех», 2011, 11 ) В Городском Собрании 24 депутата. Любые двое из них либо дружат, либо враждуют, причём известно, что каждый дружит ровно с 7 другими. Каждые три депутата образуют комиссию. Найдите общее число комиссий, в которых все три члена попарно дружат или все трое попарно враждуют. 680 38. («Высшая проба», 2011, 9 ) В классе 20 учеников, каждый из которых дружит ровно с шестью одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся. 360 39. («Высшая проба», 2011, 9 ) Класс из 20 учеников разделён на две половины так, что каждый школьник из первой половины дружит ровно с шестью одноклассниками, а каждый школьник из второй половины дружит ровно с четырьмя одноклассниками. Найдите число таких различ- ных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся. 450 40. («Физтех», 2012, 9–11 ) Прямоугольник, составленный из одинаковых квадратных клеток, назовём чётным, если он содержит чётное число клеток. Из одинаковых квадратных клеток составлен прямоугольник длиной 9 клеток и шириной 4 клетки. Сколько в нём содержится чётных прямоугольников? 300 41. («Физтех», 2012, 9–11 ) Сколькими способами можно выложить в ряд три красных, четыре синих и пять зелёных шаров так, чтобы никакие два синих шара не лежали рядом? 7056 42. («Физтех», 2012, 10 ) Сколько существует способов раскрасить вершины правильного пя- тиугольника в восемь цветов, если раскраски, которые можно совместить поворотом, считаются одинаковыми? 6560 43. («Высшая проба», 2012, 9 ) На плоскости отмечены восемь точек, никакие три из кото- рых не лежат на одной прямой. Может ли быть так, что более одной пятой всех выпуклых четырёхугольников с вершинами в этих точках — параллелограммы? Да 44. («Высшая проба», 2014, 10 ) На плосокости даны восемь различных точек. Нумерацию этих точек числами от 1 до 8 назовём хорошей, если выполнено следующее условие: существует такая прямая, что все точки лежат по одну сторону и на разных расстояниях от неё, и при этом расстояния от точек до этой прямой возрастают с возрастанием номера (т. е. ближайшая точка — номер 1, следующая по удалённости — номер 2 и т. д.). Какое максимальное количество различных хороших нумераций может быть у заданной восьмёрки точек? 56 35 45. («Высшая проба», 2012, 11 ) В одной из вершин правильного 2n-угольника (n > 2) постав- лено число 1. Для данной расстановки чисел 2, 3, . . . , 2n в остальные вершины 2n-угольника поставим на каждой его стороне знак +, если число на конце стороны (при движении по ча- совой стрелке) больше числа на её начале, и знак −, если оно меньше. Докажите, что модуль разности между числом расстановок чисел 2, 3, . . . , 2n с чётным количеством плюсов на сторо- нах и числом расстановок с нечётным количеством плюсов равен числу расстановок, в которых плюсы и минусы чередуются, при (а) n = 3; (б) n = 4; (в) произвольном n. 36 5 Формула включений и исключений Не всякая задача комбинаторики решается непосредственным применением основных комби- наторных принципов — правила суммы или произведения, подсчётом числа размещений или сочетаний. В некоторых случаях приходится идти окольным путем и действовать своеобразным «методом решета», который состоит в следующем: для нахождения числа элементов интересу- ющего нас множества мы сначала находим число элементов некоторого большего множества, а потом «просеиваем» нужные элементы, постепенно отбрасывая лишние. 5.1 Переход к дополнению Простейшим примером «метода решета» является переход к дополнению: число «хороших» элементов равно общему числу элементов минус число «плохих» элементов. Задача. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна цифра 7? Решение. Найдём сначала, сколько всего имеется четырёхзначных чисел. Первую цифру мы можем выбрать девятью способами, каждую из остальных цифр — десятью. Стало быть, коли- чество четырёхзначных чисел равно 9 · 10 · 10 · 10 = 9000. Теперь найдём, сколько четырёхзначных чисел не содержат ни одной семёрки. Для выбора первой цифры имеется 8 способов, для выбора каждой из остальных цифр — 9 способов. Сле- довательно, всего будет 8 · 9 · 9 · 9 = 5832 четырёхзначных чисел, в записи которых нет ни одной цифры 7. Ну а чисел, в которых хотя бы одна семёрка имеется, будет 9000 − 5832 = 3168. Здесь мы действовали по схеме, которую, выражаясь неформально, можно описать так: «хо- тя бы один» равно общему числу минус «ни одного». В других ситуациях можно действовать наоборот: «ни одного» равно общему числу минус «хотя бы один». Задача. Дан выпуклый n-угольник (n > 5). Сколькими способами можно выбрать в нём две непересекающиеся диагонали? Порядок выбора не важен. Решение. Идея подсчёта такова: искомое число пар непересекающихся диагоналей равно об- щему числу пар диагоналей минус число пар пересекающихся (внутри n-угольника) диагоналей минус число пар смежных (выходящих из одной вершины) диагоналей. Из каждой вершины n-угольника исходят n − 3 диагоналей, поэтому всего диагоналей име- ется n(n − 3)/2. Значит, число неупорядоченных пар диагоналей равно: N 0 = C 2 n(n−3)/2 = 1 2 · n(n − 3) 2 n(n − 3) 2 − 1 = n(n − 3)(n 2 − 3n − 2) 8 Теперь найдём число пар пересекающихся диагоналей. Каждой такой паре отвечает чет- вёрка вершин n-угольника — концов этих диагоналей. Наоборот, каждым четырём вершинам n-угольника соответствует единственная пара пересекающихся диагоналей. Поэтому число пар пересекающихся диагоналей есть число неупорядоченных четвёрок вершин n-угольника: N 1 = C 4 n = n(n − 1)(n − 2)(n − 3) 24 Осталось найти число N 2 пар смежных диагоналей. Из каждой вершины выходят C 2 n−3 пар диагоналей, поэтому N 2 = nC 2 n−3 = n(n − 3)(n − 4) 2 37 Искомое число пар непересекающихся диагоналей: N = N 0 − N 1 − N 2 , и после несложных преобразований получим: N = n(n − 3)(n − 4)(n − 5) 12 Бывает так, что в условии задачи ничто не намекает на «хотя бы один» или «ни одного», и тем не менее задача проще всего решается переходом к дополнению. Задача. («Высшая проба», 2013, 10 ) В стране пять городов: А, Б, В, Г и Д. Их хотят связать четырьмя авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать? Решение. Найдём сначала общее количество соединений пяти городов четырьмя авиалиниями. Всего пар городов имеется C 2 5 = 10. Из них нужно выбрать четыре пары для соединения. Это можно сделать C 4 10 = 210 способами. Теперь ищем количество плохих соединений (когда найдутся два города таких, что из одного никак нельзя долететь до другого). Плохие соединения могут быть двух видов: 1) есть изоли- рованный город (из которого не выходит ни одна авиалиния); 2) нет изолированного города (то есть из каждого города выходит авиалиния). Пусть изолированный город есть (его можно выбрать 5 способами). Тогда четыре авиалинии проложены (как угодно) между четырьмя остальными городами. Из C 2 4 = 6 пар городов мы выбираем 4 пары для соединения; это можно сделать C 4 6 = 15 способами. Следовательно, плохих соединений с изолированным городом получается 5 · 15 = 75. Теперь предположим, что в плохом соединении изолированного города нет. Выясним, как устроено такое соединение. Допустим, что из города А нельзя попасть в город Д. Пусть А соединён линией с Б, а Д соединён линией с Г. Имеются лишь две возможности провести остав- шиеся линии: достроить треугольник АБВ (он не будет связан с отрезком ГД) или достроить треугольник ВГД (он не будет связан с отрезком АБ). Итак, плохое соединение без изолированного города — это треугольник плюс не связанный с ним отрезок, и таких соединений столько же, сколько существует способов соединить два го- рода отрезком (тогда оставшиеся три города автоматически замкнутся треугольником). Таким образом, нужно просто выбрать два города из пяти; для этого имеется C 2 5 = 10 способов. Всего плохих соединений получается 75+10 = 85. Следовательно, искомое число соединений равно 210 − 85 = 125. 5.2 Формула включений и исключений Действуя по схеме «ни одного» равно общему числу минус «хотя бы один», мы должны уметь вычислять «хотя бы один», то есть находить число объектов, обладающих хотя бы одним из указанных свойств. С теоретико-множественной точки зрения речь идёт о нахождении числа элементов в объединении нескольких множеств. В такой ситуации часто приходит на помощь формула включений и исключений. В качестве элементарного примера рассмотрим следующую задачу. Задача. Каждый ученик класса побывал в театре или в кино. В театр сходили 22 человека. В кино были 15 человек. И в театре, и в кино были 7 человек. Сколько учеников в классе? Решение. Если мы найдём сумму 22 + 15, то окажется, что каждого, кто побывал и в театре, и в кино, мы посчитали дважды (например, если Вася сходил и в театр, и в кино, то один раз он вошёл в эту сумму в числе 22 «театралов», а второй раз — в числе 15 «киношников»). Поэтому найденная сумма на 7 больше количества учеников в классе. Следовательно, в классе 22 + 15 − 7 = 30 человек. 38 Число элементов конечного множества A называется мощностью этого множества и обо- значается |A|. Формула включений и исключений даёт возможность находить мощность объ- единения любого конечного набора множеств. Формула включений и исключений для двух множеств. Для любых конечных множеств A и B справедливо равенство |A ∪ B| = |A| + |B| − |A ∩ B|. (7) Доказательство формулы ( 7 ) почти дословно повторяет решение последней задачи: сумми- руя мощности множеств A и B, мы дважды учитываем каждый элемент в их пересечении (один раз — со стороны множества A, второй раз — со стороны множества B). Поэтому мощность пересечения надо вычесть. Можно также доказать формулу ( 7 ) с помощью следующего наглядного рисунка. B A x y z Пусть x — число элементов множества A, не входящих в B; y — число элементов B, не входящих в A; z — число элементов в пересечении A и B. Тогда x + z = |A|, y + z = |B|, и мы имеем: |A ∪ B| = x + y + z = (x + z) + (y + z) − z = |A| + |B| − |A ∩ B|. Формула включений и исключений для трёх множеств. Для любых конечных множеств A, B и C справедливо равенство |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C|. (8) Почему так получается? Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности A, B и C, мы дважды учли каждый двукратный элемент и трижды — каждый трёх- кратный. Вычтя три попарных пересечения, мы «восстановили справедливость» в отношении двукратных элементов, но теперь оказались полностью неучтёнными трёхкратные элементы. Поэтому надо добавить мощность тройного пересечения. Приведём также доказательство формулы ( 8 ) с помощью следующего рисунка. B A C x y z p q r s 39 Здесь x, y, z —количества однократных элементов (входящих лишь в одно из данных мно- жеств); p, q, r —количества двукратных элементов; s — число трёхкратных элементов. Имеем: |A ∪ B ∪ C| = x + y + z + p + q + r + s = = (x + p + q + s) + (y + p + r + s) + (z + q + r + s) − (p + s) − (q + s) − (r + s) + s = = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C|. Задача. В группе 40 туристов. Из них 20 человек говорят по-английски, 15 — по-французски, 11 — по-испански. Английский и французский знают семь человек, английский и испанский — пятеро, французский и испанский — трое. Два туриста говорят на всех трёх языках. Сколько человек группы не знают ни одного из этих языков? Решение. Пусть A —множество туристов группы, знающих английский, F — французский, I — испанский. Тогда |A| = 20, |F | = 15, |I| = 11, |A ∩ F | = 7, |A ∩ I| = 5, |F ∩ I| = 3, |A ∩ F ∩ I| = 2. Сколько человек говорят хотя бы на одном из этих языков? По формуле включений и исключений для трёх множеств имеем: |A ∪ F ∪ I| = |A| + |F | + |I| − |A ∩ F | − |A ∩ I| − |F ∩ I| + |A ∩ F ∩ I| = = 20 + 15 + 11 − 7 − 5 − 3 + 2 = 33. Значит, ни одного из данных языков не знают 40 − 33 = 7 человек. Теперь мы готовы привести формулу включений и исключений для любого конечного числа множеств, которая обобщает формулы ( 7 ) и ( 8 ). Формула включений и исключений. Для любых конечных множеств A 1 , A 2 , . . . , A n спра- ведливо равенство |A 1 ∪ A 2 ∪ . . . ∪ A n | = X i |A i | − X i i ∩ A j | + X i i ∩ A j ∩ A k |− − X i i ∩ A j ∩ A k ∩ A l | + . . . + (−1) n+1 |A 1 ∩ A 2 ∩ . . . ∩ A n |. (9) Выглядит формула ( 9 ) громоздко, но суть её проста: сначала суммируем мощности всех множеств (n слагаемых), затем вычитаем мощности всех попарных пересечений (C 2 n слагаемых), затем прибавляем мощности всех тройных пересечений (C 3 n слагаемых) и так далее, чередуя знаки, до последнего слагаемого — мощности пересечения всех n множеств. Для доказательства формулы ( 9 ) нам понадобится вспомогательное тождество. Лемма. Для любого натурального m справедливо равенство C 1 m − C 2 m + C 3 m − . . . + (−1) m+1 C m m = 1. Доказательство леммы. Воспользуемся биномом Ньютона: 0 = (1 − 1) m = m X k=0 C k m · 1 m−k · (−1) k = 1 + m X k=1 (−1) k C k m = 1 − m X k=1 (−1) k+1 C k m , откуда 1 = m X k=1 (−1) k+1 C k m = C 1 m − C 2 m + C 3 m − . . . + (−1) m+1 C m m Лемма доказана. 40 Доказательство формулы включений и исключений. Возьмём произвольный элемент x ∈ A 1 ∪ A 2 ∪ . . . ∪ A n . Покажем, что x учитывается правой частью формулы ( 9 ) в точности один раз. Предположим, что x принадлежит пересечению ровно m наших множеств; не ограничи- вая общности, можно считать, что x принадлежит множествам A 1 , . . . , A m и не принадлежит множествам A m+1 , . . . , A n . Тогда: • в первой сумме P i |A i | элемент x посчитан m = C 1 m раз (в слагаемых |A 1 |, . . . , |A m |); • во второй сумме P i i ∩ A j | элемент x посчитан C 2 m раз (ведь количество попарных пересечений A i ∩ A j , для которых i, j ∈ {1, 2, . . . , m}, равно C 2 m ); • в третьей сумме P i i ∩ A j ∩ A k | элемент x посчитан C 3 m раз (ведь количество пере- сечений A i ∩ A j ∩ A k , для которых i, j, k ∈ {1, 2, . . . , m}, равно C 3 m ); • в m-й сумме P i 1 <...|A i 1 ∩ A i 2 ∩ . . . ∩ A i m | элемент x посчитан 1 = C m m раз (он войдёт только в слагаемое |A 1 ∩ A 2 ∩ . . . ∩ A m |); • суммы, содержащие m + 1 и более пересечений, не учитывают элемент x, поскольку x не входит в пересечение более чем m множеств. Таким образом, элемент x оказывается посчитанным C 1 m − C 2 m + C 3 m − . . . + (−1) m+1 C m m раз. Согласно лемме это выражение равно единице, что и требовалось. Формула ( 9 ) тем самым доказана. Перейдём к рассмотрению задач, которые можно решить с помощью формулы включений и исключений. 5.3 Задача о беспорядках Ранее мы привели частный случай задачи о шляпах (для четырёх гостей) и решили её непо- средственным перебором. Теперь рассмотрим данную задачу в общем виде. Задача. (Леонард Эйлер) Войдя в ресторан, n гостей оставили швейцару свои шляпы, а на выходе получили их обратно. Швейцар раздал шляпы случайным образом. Сколько существует вариантов, при которых каждый гость получит чужую шляпу? Решение. Занумеруем гостей числами 1, 2, . . . , n и так же занумеруем шляпы (при этом i-я шляпа принадлежит i-му гостю). Тогда любая перестановка k 1 k 2 . . . k n чисел 1, 2, . . . , n обозначает вариант разбора шляп, при котором i-й гость получил k i -ю шляпу. Например, в случае четырёх человек перестановка 4132 означает, что первый получил четвёртую шляпу (k 1 = 4), второй — первую (k 2 = 1), третий — третью (свою, k 3 = 3) и четвёртый — вторую (k 4 = 2). Наоборот, каждый вариант разбора шляп обозначается единственной перестановкой чисел 1, 2, . . . , n. Будем говорить, что в перестановке k 1 k 2 . . . k n чисел 1, 2, . . . , n число i стоит на своём месте, если k i = i (например, в перестановке 4132 тройка стоит на своём месте). Нас интересует количество беспорядков, то есть таких перестановок, в которых ни одно из чисел не стоит на своём месте. Число беспорядков можно найти, вычитая из общего количества перестановок, равного n!, количество тех перестановок, в которых хотя бы одно из чисел стоит на своём месте. 41 Пусть A i — множество перестановок, в которых число i стоит на своём месте (i = 1, 2, . . . , n). Искомое число N беспорядков, таким образом, равно N = n! − |A 1 ∪ A 2 ∪ . . . ∪ A n | = = n! − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) n |A 1 ∩ A 2 ∩ . . . ∩ A n |. Ясно, что |A i | = (n − 1)!, поэтому X i |A i | = n · (n − 1)! = n!. Точно так же |A i ∩ A j | = (n − 2)! и X i i ∩ A j | = C 2 n · (n − 2)! = n(n − 1) 2! · (n − 2)! = n! 2! Аналогично |A i ∩ A j ∩ A k | = (n − 3)! и X i i ∩ A j ∩ A k | = C 3 n · (n − 3)! = n(n − 1)(n − 2) 3! · (n − 3)! = n! 3! Теперь мы приходим к нужной формуле: N = n! − n! + n! 2! − n! 3! + . . . + (−1) n = n! · n X k=0 (−1) k k! При n = 4 найденная формула даёт: N = 4! 2! − 4! 3! + 4! 4! = 12 − 4 + 1 = 9. Этот результат мы получили ранее прямым перебором. Заметим, что если шляпы разбираются случайным образом, то вероятность беспорядка ока- зывается равной: N n! = n X k=0 (−1) k k! При n → ∞ данная сумма стремится к пределу, равному 1/e, где e = 2,718 . . . — одна из самых распространённых математических констант (наряду с числом π), получившая обозначение также в честь Эйлера. Таким образом, если гостей много, то вероятность, что каждый уйдёт в чужой шляпе, приблизительно равна 1/e ≈ 0,37. 5.4 Функция Эйлера Напомним, что два натуральных числа называются взаимно простыми, если у них нет общих делителей (кроме 1). Функция Эйлера — это функция ϕ(n) натурального аргумента n, равная количеству на- туральных чисел, меньших n и взаимно простых с n (при этом ϕ(1) = 1 по определению). Например, ϕ(15) = 8, поскольку имеется 8 натуральных чисел, меньших 15 и взаимно про- стых с ним: 1, 2, 4, 7, 8, 11, 13, 14. Функция Эйлера играет важную роль в теории чисел и криптографии. 42 Пусть n > 2. Значение функции Эйлера числа n можно найти из разложения этого числа на простые множители: n = p a 1 1 p a 2 2 . . . p a r r (p 1 , p 2 , . . . , p r — все различные простые делители числа n). Покажем, что ϕ(n) = n 1 − 1 p 1 1 − 1 p 2 1 − 1 p r Если число k взаимно просто с n, то k не делится ни на одно из чисел p 1 , p 2 , . . . , p r . Мы найдём величину ϕ(n), вычитая из n количество чисел, меньших n и делящихся хотя бы на одно из чисел p 1 , p 2 , . . . , p r Пусть A i — множество чисел, меньших n и делящихся на p i (i = 1, 2, . . . , r). Имеем: N = n − |A 1 ∪ A 2 ∪ . . . ∪ A r | = = n − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) r |A 1 ∩ A 2 ∩ . . . ∩ A r |. Ясно, что |A i | = n p i , |A i ∩ A j | = n p i p j , |A i ∩ A j ∩ A k | = n p i p j p k , и так далее. Получаем: ϕ(n) = n − X i n p i + X i p j − X i p j p k + . . . + (−1) r n p 1 p 2 . . . p r = = n 1 − 1 p 1 1 − 1 p 2 1 − 1 p r , что и требовалось. 5.5 Числа Стирлинга второго рода В качестве ещё одного примера применения формулы включений и исключений рассмотрим следующую комбинаторную задачу (далее предполагается, что k > n). Задача. Сколькими способами можно разложить m различных шаров по n различным ящикам так, чтобы ни один из ящиков не оказался пустым? Решение. Если ящики могут быть пустыми, то число способов разложить m различных шаров по n различным ящикам равно n m — это просто число размещений с повторениями Пусть A i — множество разложений шаров, при которых i-й ящик пуст (i = 1, 2, . . . , n). Тогда искомое число D(m, n) разложений шаров, при которых все ящики непусты, равно: D(m, n) = n m − |A 1 ∪ A 2 ∪ . . . ∪ A n | = = n m − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) n |A 1 ∩ A 2 ∩ . . . ∩ A n |. Ясно, что |A i | = (n − 1) m , |A i ∩ A j | = (n − 2) m , |A i ∩ A j ∩ A k | = (n − 3) m и так далее. Получаем: D(m, n) = n m − C 1 n (n − 1) m + C 2 n (n − 2) m − C 3 n (n − 3) m + . . . + (−1) n · 0 = n X k=0 (−1) k C k n (n − k) m 43 Задача решена. Данная задача известна также и в другой формулировке. Прежде всего, дадим определе- ние: функция f : A → B называется сюръекцией, если каждый элемент множества B имеет прообраз (то есть для любого y ∈ B найдётся такой элемент x ∈ A, что f (x) = y). Например, функция f : R → [−1; 1], задаваемая формулой f (x) = sin x, является сюръекцией, а функция f : R → R, задаваемая той же формулой f (x) = sin x, сюръекцией уже не будет, так как число 2 не имеет прообраза. Задача. Найти число сюръекций из m-элементного множества в n-элементное. Решение. Рассмотрим функцию f : A → B, где |A| = m и |B| = n. Представим себе, что элементы множества A — это шары, а элементы множества B — это ящики. Тогда функция f есть некоторый способ разложить m различных шаров в n различных ящиков; при этом f будет сюръекцией в том и только в том случае, если при соответствующем разложении ни один ящик не окажется пустым. Следовательно, число сюръекций из A в B равно D(m, n), Интересна также ситуация, когда ящики неразличимы. Она приводит к отдельной комби- наторной задаче о числе разбиений множества. Задача. Сколькими способами можно разложить m различных шаров по n неразличимым ящикам так, чтобы ни один из ящиков не оказался пустым? Иными словами, сколькими спо- собами можно представить m-элементное множество в виде объединения n непустых непересе- кающихся подмножеств? Решение. Если ящики неразличимы, то любая перестановка n ящиков ничего не меняет, и поэтому число D(m, n) разложений m различных шаров по n различным ящикам нужно раз- делить на n!: S(m, n) = D(m, n) n! = 1 n! n X k=0 (−1) k C k n (n − k) m Получилось число способов разложить m шаров по n неразличимым ящикам, или число способов представления m-элементного множества в виде объединения n непересекающихся непустых подмножеств. Числа S(m, n) называются числами Стирлинга второго рода. Теперь допустим, что ящики могут быть пустыми. Задача. Сколькими способами можно разложить m различных шаров по n неразличимым ящикам? На число шаров в ящике ограничений нет. Решение. При произвольной раскладке наши m шаров окажутся лежащими в каких-то k ящиках (1 6 k 6 n), а остальные n − k ящиков будут пустовать. Такое разложение можно осуществить S(m, k) способами. Суммируя по k, получим искомое число способов: n X k=1 S(m, k). 5.6 Задачи |