ФОРМУЛА ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ

ФОРМУЛА ВКЛЮЧЕНИЯ­ИСКЛЮЧЕНИЯ   Пусть у множеств А и В общая часть насчитывает k элементов. Тогда всего, в объединении  множеств А и В, число элементов равно   Понятно, что, складывая числа  m  и  n,  мы засчитываем общие элементы дважды. Правило включения – исключения распространяют на объединение произвольного числа  множеств. Для трех множеств соответствующая формула написана ниже.   т. е.   Теорема.  Доказательство. Для доказательства обозначим число элементов в каждой из  7  частей трёх множеств,  находящихся в «общем положении», некоторой переменной, а затем выразим через эти  переменные каждое слагаемое в левой и правой части. Подставив полученные выражения в  утверждение теоремы, убедимся в его правильности. Другой способ рассуждений – убедиться в том, что элементы каждой из  указанных  7  частей множества подсчитаны в правой части, причём, ровно по одному разу.  Рассмотрим, например, элементы пересечения  A  и  B,  не входящие в  C.  В правой части  они учитываются трижды: два раза в слагаемых   Однако последнее в формулу входит со знаком минус, поэтому в результате элементы  указанной части учитываются ровно по одному разу.     один раз в слагаемом     иРазмещения, перестановки, сочетания с повторениями. Формула включения –  исключения Размещения с повторениями Определение. Отображение множества   первых натуральных чисел  множество  данных   в данное  , называется размещением с повторениями, составленным из   элементов по  . Размещения с повторениями называются также конечными последовательностями. вкккккккккккккккккккк Два размещения с повторениями одинаковы тогда и только тогда, когда на одинаковых  местах находятся одни и те же элементы. Если в размещении с повторениями некоторый элемент ставится в соответствие  различным натуральным числам, т.е., иначе говоря, данный элемент занимает  мест, то говорят, что этот элемент повторяется в размещении    кккккккккккккккккккккккккк  раз.  различных  Пример. Всевозможные размещения с повторениями из трех элементов   по 2: Теорема. Число всевозможных размещений с повторениями из   элементов по   равно Доказательство. По индукции. При  элементы  число этих размещений равно  .  теорема верна, так как сами   составляют всевозможные размещения элементов по одному, то  Предположим, что число размещений с повторениями из  Составим из данных  элементу. Во всяком размещении с повторениями по   элементов по   равно   элементов всевозможные размещения с повторениями по   элементу Reset .    первые   элементов образуют некоторое размещение с повторениями из  последнего  выборах  размещения  ­го порядка дают два различные размещения   может быть взят любой из  ­го элемента   получаются различные размещения. Кроме того, два различные  ­го порядка.  по   элементов. В качестве   элементов. При различныхТаким образом, число всех размещений  ­го порядка равно Задача. Имеется  может быть сделан выбор книг из числа данных?  различных книг, каждая в   экземплярах. Сколькими способами  Перестановки с повторениями Всякое размещение с повторениями, в котором элемент  повторяется  называется перестановкой с повторениями порядка  раз и т.д. элемент   повторяется  раз, где   повторяется  ,  ,  ,   раз, элемент     — данные числа,  в которой данные элементы   повторяются соответственно  ,  ,   раз. Теорема. Число различных перестановок с повторениями из элементов  которых элементы   повторяются соответственно   раз, равно , в  Доказательство. Если мы будем считать все  повторениями различными, то всего различных вариантов перестановок  элементов —  самом деле, все элементы  перестановка не изменится. Точно так же, можем переставлять элементы  Таким образом, всякая перестановка может быть записана  Следовательно, число различных перестановок с повторениями равно . Однако среди этих перестановок не все различны. В   мы можем переставлять местами друг с другом, и от этого  .   элементов перестановки с    ,   способами.  ,  ,  Задача. Дано  предметы на 3 группы так, чтобы первая группа содержала  предметов, а третья   предметов?  различных предметов. Сколькими способами можно разбить эти   предметов, вторая    Сочетания с повторениями Определение. Если каждому элементу некоторого конечного множества поставлено в  соответствие целое неотрицательное число — кратность данного элемента, то говорят,что задано сочетание с повторениями. Сумма   кратностей всех элементов называется  порядком сочетания. Всякое сочетание с повторениями  ­го порядка, составленное из множества,  содержащего  по  .  элементов, называется также сочетанием с повторением из   элементов  Если  определению   — кратности элементов  , то по   есть порядок сочетания Теорема. Число сочетаний с повторениями из   элементов по   выражается формулой Пример. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры,  песочные и картошка. Сколькими способами можно купить 7 пирожных? Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их  картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки­ разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1  эклер, 2 песочных и 1 картошка. Итак два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов. Два способа рассуждения: (1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10  объектов. (2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей. В чем особенность: объекты повторяются, причем один эклер на вкус неотличим от  другого. Отсюда название: сочетания с повторениями. Можно представлять себе, что  пирожные непрерывно пекут, так что они не переводятся, сколько ни ешь. Это совсем  другая ситуация, чем в обычных сочетаниях!!! Пусть заданы два числа:   — число выбираемых элементов, и   — число типов элементов, из которых производится выбор. Число     сочетаний с повторениями из элементовтипов равно числу способов выбора мест для собственно выбираемых элементов  различных классов, или, что то же: для разделителей между ними. Итак, основная формула: Задача. Имеется  эти предметы между   лицами?  одинаковых предметов. Сколькими способами можно распределить  Сочетания с повторениями с дополнительными условиями Сколько существует сочетания с повторениями таких, что в них обязательно входят  элементы   фиксированных типов? Сразу возьмем по одному элементу указанного типа, и тогда уже сразу окажутся заняты    мест. Остальные   мест можно заполнять элементами прежних   типов. В частности, пусть число типов  существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?  — числа выбранных элементов. Сколько  Пример.   шаров размещаются по  так, что пустых ящиков нет?  ящикам. Сколько существует способов разместить их Решение. Пусть нолики — шарики, а единички — стенки ящиков (потребуется  единичек). Две единички сразу кладем по краям.   Теперь положим между ними шарики­нолики, а далее нужно заполнить некоторые  промежутки между ними так, чтобы между любыми двумя ноликами находилась не более  одной единички. Значит, из  выбрать места для   промежутков между шариками нужно  единичек. Всего таких способов  . Метод координат. Подсчет числа путей Рассмотрим координатную сетку: двигаясь по ней, помечаем каждый перекресток —  производим суммирование числа возможных путей, ведущих на каждый перекресток.  Получаем известный треугольник Паскаля.  (считая сверху и принимая верхний уровень за  Поскольку на перекресток   на уровне  нулевой) ведет  числа  как  путей (число способов выбрать  движений направо вниз из общего   движений вниз), то свойство суммирования путей на перекрестке можно записатьПо прежнему остается справедливым свойство симметрии  . Формула включения — исключения Определение. Число элементов множества  обозначается  .  называется мощностью множества   и  Теорема. Пусть даны множества  объединении этих множеств можно найти по формуле: . Тогда количество элементов в  Доказательство проводится по индукции. Пусть  . Нужно доказать формулу Действительно, множество  элементов множества  количества элементов во множествах  раза посчитаем количество элементов, общих для множеств  , которые не содержатся в множестве , мы два  и  . Тогда, сложив   и  .  состоит из всех элементов множества   и тех  Предположим, что формула включения — исключения справедлива для  Докажем ее для   множеств. Множество   можно представить в виде  множеств. Тогда получаем (первое равенство по формуле включения — исключения для двух  множеств): Используя формулу и формулу включения — исключения для   множеств, получаемВ эту формулу  подставляем выражение, полученное ранее, и теорема доказана. Задачи. 1. Есть три билета в различные театры. Сколькими способами они могут быть  распределены между 25 школьниками, если каждый школьник может получить только  один билет? 2. Есть три билета на КВН 1 апреля. Сколькими способами они могут быть распределены  между 25 школьниками (более одного билета в руки не давать!!!)? 3. Телефонный номер состоит из 7 цифр. Насколько легче угадать правильный номер,  если знать, что все его цифры различны? 4. В буфете продаются 5 сортов пирожков: с яблоками, с капустой, картошкой, мясом и  грибами (цена всех пирожков одинакова). Скольким числом способов можно сделать  покупку из 10 пирожков? 5. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы  попробовать пирожков всех видов? 6. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы в нее  вошло не менее двух пирожков с мясом и хотя бы один пирожок с яблоками? 7. Скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так, чтобы  никакие два тигра не шли друг за другом (оказавшись рядом, они начинают драться)? 8. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со  своими соседями. Для участия в спецоперации по освобождению заколдованной  принцессы нужно выбрать 5 рыцарей, но при этом нельзя посылать вместе рыцарей,  враждующих друг с другом. Скольким числом способов это можно сделать? 9. Докажите формулу 10. Докажите, что число различных решений уравнения в неотрицательных целых числах равно  .11. Докажите, что число различных решений уравнения в натуральных числах равно  . 12. Сколькими способами можно разложить 15 одинаковых шаров по 5 различным ящикам так, чтобы оказалось не более двух пустых ящиков? 13. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров? 14. Сколькими способами можно разложить 20 одинаковых шаров по 6 различным ящикам так, чтобы в каждом ящике оказалось не более 5 шаров? 15. Докажите, что число таких перестановок  удовлетворяют условию   при всех  , равно  чисел  , которые