Формула включений и исключений
Раздел 2. КОМБИНАТОРИКА
Вступление
Задачи, в которых из элементов счетного множества по некоторым правилам составляются различные комбинации этих элементов, и подсчитывается число таких комбинаций, называют комбинаторными, а раздел дискретной математики, в которой изучают комбинаторные задачи, – комбинаторикой.
При решении комбинаторных задач различают несколько уровней. Начальным уровнем является поиск хотя бы одной комбинации объектов, которая имеет заданные свойства. Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений и моделирования всех решений данной задачи.
Третий, более сложный, уровень комбинаторных задач заключается в том, что среди всех возможных решений нужно найти одно или несколько так называемых оптимальных решений, которые превосходят другие решения теми или иными характеристиками. Как правило, такие ситуации встречаются в программировании, в экономическом моделировании, при оптимальном планировании той или иной народнохозяйственной деятельности. После изучения этого раздела студент должен продемонстрировать умение использовать математические методы для решения определенного класса прикладных задач, а прежде всего, овладение УМЕНИЯМИ:
Þ рассчитывать перестановки, размещения, сочетания с повторениями и без повторений и использовать их в конкретных задачах;
Þ применять элементы комбинаторного анализа комбинаторных систем с оптимальным распределением элементов;
Þ моделировать рекуррентные соотношения и находить их решения;
Þ решать комбинаторные задачи, используя аппарат производящих функций.
и ЗНАНИЯМИ:
Þ основных типов задач комбинаторного анализа и методов их решения;
Þ понятий: перестановок, размещений, сочетаний элементов (с повторениями и без повторений);
Þ алгоритмов распределения объектов по ячейкам;
Þ аппарата производящих функций;
Þ методов решения рекуррентных соотношений второго и высших порядков.
Итак, как раздел дискретной математики, комбинаторика играет важную роль в решении ряда проблем статистики, теории вероятностей, вычислительной техники и многих других отраслей математики. Она находит применение и в других областях науки: в биологии (комбинаторные методы полезны при изучении состава белков и ДНК), в химии, механике сложных сооружений и т.д.
Соединения без повторений
Основные правила комбинаторики
1) Правило суммы
Пусть первый объект может быть выбран способами, второй объект – способами, ... -й объект – способами и все способы несовместимы. Тогда выбор первого или второго ... или -го объекта может быть осуществлен способами.
Или: если множество X представимо в виде разбиения X=B1ÈB2…ÈBn, то |X| = |B1|+|B2|+…+|Bn|.
2) Правило произведения
Пусть объект может быть выбран способами, объект – способами, ... объект – способами, тогда выбор совокупности объектов можно осуществить способами.
Или: если множество X представимо в виде декартова произведения X=X1´X2´…´Xn, то .
Пусть – фиксированное конечное множество.
Определение 1. Упорядоченные множества, состоящие из k элементов множества , называются размещениями без повторений из n элементов по k.
Два размещения из по считаются различными, если они состоят из различных элементов множества или они состоят из одинаковых элементов , но эти элементы расположены в данных размещениях по-разному.
Определение 2. Размещение из n элементов по n будем называть перестановками из n элеменов.
Количество всевозможных размещений из элементов по обозначается .
.
Количество всевозможных перестановок из элементов обозначается .
.
Для размещений из элементов по справедливо рекуррентное соотношение:
.
Определение 3. Неупорядоченые подмножества множества Х, состоящие из элементов множества X, называются сочетаниями без повторений из n элементов множества Х по .
Два сочетания из элементов по считаются различными, если они отличаются хотя бы одним элементом. Количество всевозможных сочетаний из элементов по будем обозначать .
.
Некоторые свойства сочетаний:
1) ;
2) ;
3) ;
4) .
Пример 1.Сколькими способами из группы в 25 человек можно выбрать:
а) троих для участия в субботнике;
б) старосту, профорга и спортивного организатора.
Решение
а) выбор можно осуществить способами, ,
б) выбор можно осуществить способами .
Бином Ньютона
Справедливой является формула (1)
Доказательство (методом математической индукции).
1) Проверим верность формулы (1) при n=1. = C a0b1 + C a1b0 = b + a
2) Предположим, что формула (1) верна для n=k–1. (2)
3) Проверим справедливость формулы (1) для n=k. Умножим обе части (2) на (a+b):
(3)
Сведем подобные слагаемые в правой части соотношения (3), воспользовавшись свойством 4). для сочетаний: . ■
Полиномиальная формула
, (4)
здесь суммирование производится по всем целым неотрицательным , таким, что их сумма равна n. Формула (4) может быть записана также в виде :
Доказательство (методом математической индукции).
Верность формулы (4) для двух слагаемых очевидна: (5)
(вытекает из бинома Ньютона).
Пусть формула (4) справедлива для k-1 слагаемых, то есть выполняется равенство: . (6)
Обозначим +...+ = a в левой части соотношения (6).
Используя после этого формулу бинома Ньютона и соотношение (6), получим:
= = = = ■
Вопросы для самоконтроля
1. В урне содержатся 3 различных белых и 7 черных шаров. Сколькими способами можно извлечь из этой урны:
а) 5 шаров так, чтобы среди них оказалось 2 белых и 3 черных шара;
б) 4 шара так, чтобы среди них белых оказалось больше, чем черных?
2. Сколькими способами из полной колоды карт (52 карты) можно вытащить четыре карты так, чтобы:
а) все они были картинками;
б) среди них были тройка, семерка, туз?
3. Сколько можно составить шестизначных шифров для банковского сейфа, в которых все цифры разные?
4. Сколькими способами можно рассадить за круглым столом 5 мужчин и 5 женщин так, чтобы лица одного пола не сидели рядом?
5. Сколькими способами из 28 костей домино следует выбрать две кости так, чтобы их можно было приложить друг к другу (то есть некоторое число очков встретилось на обеих костях).
6. Из чисел 12, ..., 19 выбирают пять без повторений.
а) Сколькими способами это можно сделать?
б) Сколькими способами это можно сделать так, чтобы среди выбранных чисел было число 13?
в) Сколькими способами это можно сделать так, чтобы среди выбранных чисел были числа 13 и 18?
г) Сколькими способами это можно сделать так, чтобы среди выбранных чисел число 13 было наименьшим?
д) Сколькими способами это можно сделать так, чтобы среди выбранных чисел число 18 было наибольшим?
е) Сколькими способами это можно сделать так, чтобы среди выбранных чисел число 13 было наименьшим, а число 18 было наибольшим?
Соединения с повторениями
Пусть дано множество , состоящее из элементов .
Определение 1. Размещениями из n элементов по с повторениями называются упорядоченные множества, состоящие из элементов, каждый из которых является каким-нибудь элементом множества .
Например, некоторые размещения из n элементов множества по 4 имеют вид:
Два размещения из элементов по с повторениями считаются равными, если они совпадают как своими элементами, так и порядком их расположения.
Количество всевозможных различных размещений из элементов по с повторениями будем обозначать : .
Пример 1.Сколько можно составить различных четырехзначных шифров для банковского сейфа?
, ; .
Определение 2. Неупорядоченые множества из элементов, каждый из которых является каким-нибудь элементом множества A, называются сочетаниями из по с повторениями.
Например, сочетанием из по 5 с повторениями является .
Число элементов в сочетании с повторениями называется кратностью элемента .
Два сочетания с повторениями считаются одинаковыми, если кратности элементов, входящих в них, совпадают.
Будем обозначать число всех сочетаний с повторениями из элементов по символом : .
Пусть множество состоит из элементов ; элементов ;… элементов . Любое упорядочивание множества называется перестановкой из элементов с повторениями.
Количество всех перестановок из элементов с повторениями будем обозначать .
Пример 2.Найти количество всех перестановок множества
, .
Вопросы для самоконтроля
1. На железнодорожной станции m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния: красный, желтый и зеленый?
2. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность государства (наибольшее число зубов у человека равно 32)?
3. Сколько перестановок можно составить из букв слова «Миссисипи»?
4. Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
5. В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно отправить 12 открыток 12 различным адресатам? Сколькими способами можно купить 8 различных открыток? Сколькими способами можно отправить 8 различных открыток 8 различным адресатам?
6. Из чисел 4,... 16 выбирают восемь с повторениями.
а) сколькими способами это можно сделать?
б) сколькими способами это можно сделать так, чтобы выбранные числа содержали число 5?
в) сколькими способами это можно сделать так, чтобы выбранные числа содержали числа 5 и 12?
г) сколькими способами это можно сделать так, чтобы среди выбранных чисел число 5 было наименьшим?
д) сколькими способами это можно сделать так, чтобы среди выбранных чисел число 12 было наибольшим?
е) сколькими способами это можно сделать так, чтобы среди выбранных чисел число 5 было наименьшим, а число 12 было наибольшим?
Формула включений и исключений
Пусть дано множество , состоящее из объектов, каждый из которых может иметь или не иметь одно из свойств .
Обозначим имеет свойство . Формула включений и исключений имеет вид:
( – мощность множества )
При решении задач часто пользуются следствиями из формулы включений и исключений.
Следствие 1
Следствие 1 предоставляет формулу для подсчета тех элементов множества A, которые не имеют ни одного из свойств .
Следствие 2.
Если все множества попарно не пересекаются, то есть , , то формула включений и исключений имеет вид:
.
Следствие 3
Если есть все множества вида: равномощны между собой независимо от набора свойств , то:
Пример 1. Староста группы подал в деканат сведения о студентах: «В группе учатся 45 человек, в том числе 25 юношей. 30 студентов группы учатся на «хорошо» и «отлично», в том числе 16 юношей. Спортом занимаются 28 студентов, в том числе 18 юношей и 17 студентов, учащихся на «хорошо» и «отлично». 15 юношей учатся на «хорошо» и «отлично» и в то же время успевают заниматься спортом.
К сожалению, староста не очень добросовестно собрал сведения, а декан прекрасно пользовался формулой включений и исключений. Поэтому через несколько дней декан указал старости на его ошибку и заставил переделать отчет. В чем ошибка старосты?
Решение
Обозначим через свойство «быть юношей», – учиться на «хорошо» и «отлично», – «заниматься спортом».
По условию задачи ; ; ; ; ; ; .
Итак, за следствием 1 из формулы включений и исключений, получим:
Но отрицательным ответ быть не может, поэтому предоставленные сведения не правильные.
Вопросы для самоконтроля
1)На кафедре теоретической механики работают несколько человек, причем каждый из них знает хотя бы один иностранный язык. Шестеро знают английский, шестеро – немецкий, семеро - французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек работает на кафедре? Сколько из них знают только английский язык? Только французский?
Ответ: 11; 1; 3.
2) На загородную прогулку поехали 92 человека. Бутерброды с колбасой взяли 47 человек, с сыром – 38 человек, с ветчиной – 42 человека, с сыром и с колбасой – 28 человек, с сыром и ветчиной – 31 человек, с колбасой и ветчиной – 25 человек. Все три вида бутербродов взяли 25 человек, а несколько человек вместо бутербродов взяли с собой пирожки. Сколько человек взяли с собой пирожки?
Ответ: 25.
3) Сколько неотрицательных целых чисел, меньших миллиона, содержат все цифры 1; 2; 3; 4? Сколько чисел состоит только из этих цифр?
Ответ: 23160 чисел; 5460 чисел.
4) Сколькими способами можно посадить рядом 3 англичан, 3 французов и 3 итальянцев так, чтобы никакие три соотечественника не сидели рядом?
Ответ: 233824.
5) Решить предыдущую задачу при условии, что рядом не могут сидеть два соотечественника.
6) Сколько существует целых чисел от 1 до 1000, которые не делятся без остатка ни на 5, ни на 7, ни на 9?
Ответ: 686.
7) Доказать, что разные r предметов можно распределить между n+p людьми так, чтобы данные n человек получили по крайней мере по одному предмету, способами?
8) Сколькими способами можно переставить цифры числа так, чтобы никакие две одинаковые цифры не стояли рядом?
Рекуррентные соотношения
Определение 1. Соотношение называется линейным рекуррентным соотношением -го порядка, если оно позволяет выразить один из членов последовательности через предыдущих членов в виде: .
Определение 2. Некоторая последовательность называется решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.
Определение 3. Последовательность , которая удовлетворяет линейному рекуррентному соотношению -го порядка, называется линейной рекуррентной последовательностью -го порядка.
Пример 1. Является ли линейной рекуррентной последовательностью и, если – да, то какого порядка арифметическая прогрессия?
Решение
Последовательность задается таким образом:
Поскольку (1)
то рассмотрим еще одно соотношение для членов арифметической прогрессии: . (2)
Вычтем (1) из (2): ,
получим: .
Итак, арифметическая прогрессия является линейной рекуррентной последовательностью второго порядка.
Рассмотрим теперь метод решения линейного рекуррентного соотношения второго порядка. Этот метод основывается на следующих леммах.
Лемма 1. Если последовательности и являются решениями линейного рекуррентного соотношения второго порядка: , (3)
то для любых чисел и последовательность тоже является решением соотношения (3).
Лемма 2. Если число является корнем уравнения , которое называется характеристическим уравнением соотношения (3), то последовательность: является решением соотношения (3).
Определение 4. Решение линейного рекуррентного соотношения -го порядка называется общим, если оно зависит от произвольных констант и путем подбора этих констант можно получить любое решение данного соотношения.
Правило решения линейного рекуррентного соотношения второго порядка с постоянными коэффициентами.
1) Если характеристическое уравнение исходного соотношения имеет два различных корня и , то общее решение данного соотношения имеет вид:
2) Если оба корня характеристического уравнения совпадают , то общее решение имеет вид:
Пример 2. Итальянский математик Фибоначчи рассматривал такую задачу:
«Пара кроликов приносит раз в месяц приплод из 2 крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят такой же приплод. Сколько пар кроликов будет через год, если в начале года была одна пара?»
Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов, появившаяся два месяца назад. Таким образом, всего будет 5 пар.
Обозначим через количество пар кроликов по истечении n месяцев с начала года. Мы видим, что через месяцев будут эти пар и еще столько новорожденных пар, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение
. (4)
Поскольку, по условию и , то последовательно находим: , , и т.д. В частности, .
Числа называют числами Фибоначчи, а соотношение (4) соотношением Фибоначчи. Это рекуррентное соотношение имеет следующее характеристическое уравнение: .
Корнями этого квадратного уравнения являются числа
,
Поэтому общее решение соотношения Фибоначчи имеет вид:
(5)
Мы назвали числами Фибоначчи решение соответствующего рекуррентного соотношения, которое удовлетворяет начальным условиям и , то есть последовательность 1,2,5,8,13,...
Часто бывает удобнее добавить к этой последовательности вначале числа 0 и 1, т. е. рассматривать последовательность 0, 1, 1, 2, 3, 5, 8, 13... Очевидно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению и начальным условиям: , . Полагая в формуле (5): и , получаем для и систему уравнений:
.
Отсюда находим, что и потому, получаем:
(На первый взгляд кажется странным, что это выражение при всех натуральных значениях принимает целые значения. Достаточно легко проверить, что так оно и есть).
Линейные рекуррентные соотношения с постоянными коэффициентами, порядок которых выше второго, решаются аналогичным образом.
Пусть рекуррентное соотношение имеет вид:
.
Составляется характеристическое уравнение:
(6)
Если все корни уравнения (6) различны, то общее решение исходного рекуррентного соотношения имеет вид:
,
если какой-нибудь, скажем, -й корень имеет кратность , то в выражении общего решения этому корню будут соответствовать слагаемых:
Составляя такие выражения для всех корней и складывая их, получим общее решение.
Пример 3. Найти общее решение рекуррентного соотношения: .
Решение
Характеристическое уравнение исходного соотношения:
имеет корни: , то есть общее решение имеет вид: .
Пример 4. Решить рекуррентное соотношение второго порядка: , с начальными условиями .
Решение
Корнями характеристического уравнения исходного соотношения есть . То есть, общее решение имеет вид:
Константы и найдем из начальных условий:
,
итак .
Ответ: .
Вопросы для самоконтроля
1. Найти общие решения рекуррентных соотношений.
а)
б)
в)
г)
д)
е)
2. Найти решения рекуррентных соотношений, удовлетворяющих начальным условия:
а)
б)
в)
г) ..
Ответ:
а)
б)
в) , где
; .
3. Найти решения рекуррентных соотношений, удовлетворяющих начальным условиям
а) и ,
б) .
Распределение по ячейкам
Предпложим, что дано объектов и k ячеек и ставится вопрос о количестве способов, которыми можно распределить объекты по ячейкам. При этом в зависимости от условий задачи, объекты могут быть различными или одинаковыми. При решении конкретных задач необходимо тщательно анализировать условия задачи, чтобы правильно решить вопрос о том, стоит ли считать объекты, которые распределяются, одинаковыми или нет.
Распределение различных шаров по ячейкам:
а) Произвольным образом.
Обозначим количество таких распределений , по правилу произведения получим, что .
б) С условием, чтобы в каждой ячейке оказался хотя бы один объект .
Обозначим количество таких распределений .
Используем следствие 3) из принципа включений и исключений. В качестве объектов будем изучать различные распределения по ячейкам; а через обозначим свойство объекта – « –я ячейка пуста», так, например, – количество распределений, в которых первая пустая ячейка ; очевидно, что: .
Поскольку ; ; ;
А , то
в) С условием, чтобы в первой ячейке оказались шаров, во второй шаров; ; в -й – шаров: .
Обозначим количество таких распределений .
Объекты для первой ячейки можно выбрать способами, для второй ячейки способами; … для -й ячейки: способами.
По правилу произведения: .
Пример 1. Найдем количество способов распределения 5 различных шаров по 2 ячейкам.
a) Произвольным образом: способов.
б) Чтобы не было пустой ячейки:
способов.
в) С условием, чтобы оказалось в первой – 3 шара, во второй – 2 шара:
способов.